Konstruktivní funkce - Constructible function - Wikipedia

v teorie složitosti, a časově konstruovatelná funkce je funkce F z přirozená čísla na přirozená čísla s vlastností, že F(n) lze zkonstruovat z n podle a Turingův stroj v době objednávky F(n). Účelem takové definice je vyloučit funkce, které neposkytují horní mez za běhu nějakého Turingova stroje.[1]

Časově proveditelné definice

Existují dvě různé definice časově konstruovatelné funkce. V první definici funkce F je nazýván časově konstruovatelný pokud existuje kladné celé číslo n0 a Turingův stroj M který, vzhledem k řetězci 1n skládající se z n ty, zastaví se přesně F(n) kroky pro všechny n ≥ n0. Ve druhé definici funkce F je nazýván časově konstruovatelný pokud existuje Turingův stroj M který, vzhledem k řetězci 1n, výstup binární reprezentace F(n) v Ó (F(n)) čas (místo toho lze použít unární vyjádření, protože tyto dva lze převést dovnitř Ó(F(n)) čas).[1]

Existuje také pojem plně časově konstruovatelné funkce. Funkce F je nazýván plně časově proveditelné pokud existuje Turingův stroj M který, vzhledem k řetězci 1n skládající se z n ty, zastaví se přesně F(n) kroky. Tato definice je o něco méně obecná než první dvě, ale pro většinu aplikací lze použít kteroukoli z těchto definic[Citace je zapotřebí ].

Prostorově konstruovatelné definice

Podobně funkce F je vesmírně konstruovatelné pokud existuje kladné celé číslo n0 a Turingův stroj M který, vzhledem k řetězci 1n skládající se z n ty, zastaví se po přesném použití F(n) buňky pro všechny n ≥ n0. Ekvivalentně funkce F je vesmírně konstruovatelné pokud existuje Turingův stroj M který, vzhledem k řetězci 1n skládající se z n ones, vypíše binární (nebo unární) reprezentaci F(n), pouze při použití Ó (F(n)) prostor.[1]

Také funkce F je plně prostorově konstruovatelný pokud existuje Turingův stroj M který, vzhledem k řetězci 1n skládající se z n ty, zastaví se po přesném použití F(n) buňky[Citace je zapotřebí ].

Příklady

Všechny běžně používané funkce F(n) (jako n, nk, 2n) jsou časově a prostorově konstruovatelné, pokud F(n) je minimálně cn pro konstantu C > 0. Žádná funkce, která je Ó (n) může být časově konstruovatelný, pokud není nakonec konstantní, protože na přečtení celého vstupu není dostatek času. Nicméně, je vesmírně konstruovatelná funkce.

Aplikace

Časově konstruovatelné funkce se používají ve výsledcích z teorie složitosti, jako je věta o časové hierarchii. Jsou důležité, protože věta o časové hierarchii se spoléhá na Turingovy stroje, které se musí určit Ó (F(n)) čas, zda algoritmus trval více než F(n) kroky. To je samozřejmě nemožné, aniž bychom byli schopni vypočítat F(n) V té době. Takové výsledky jsou obvykle pravdivé pro všechny přirozené funkce F ale nemusí to nutně platit pro uměle vytvořené F. K jejich přesné formulaci je nutné mít přesnou definici přirozená funkce f pro které je věta pravdivá. K vytvoření takové definice se často používají časově konstruovatelné funkce.

Prostorově konstruovatelné funkce se používají podobně, například v věta o hierarchii prostoru.

Tento článek včlení materiál od konstrukčního dne PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.

Reference

  1. ^ A b C Goldreich, Oded (2008). Výpočetní složitost: koncepční perspektiva. Cambridge University Press. 130, 139. ISBN  978-0-521-88473-0.