Vypočitatelná funkce - Computable function

Počitatelné funkce jsou základními předměty studia v teorii vyčíslitelnosti . Počitatelné funkce jsou formalizovaným analogem intuitivního pojmu algoritmů v tom smyslu, že funkce je vyčíslitelná, pokud existuje algoritmus, který může vykonávat funkci funkce, tj. Vzhledem k vstupu do funkční domény může vrátit odpovídající výstup. Počitatelné funkce se používají k diskusi o vyčíslitelnosti, aniž by odkazovaly na jakýkoli konkrétní model výpočtu, jako jsou Turingovy stroje nebo registrační stroje . Jakákoli definice však musí odkazovat na nějaký konkrétní model výpočtu, ale všechny platné definice poskytují stejnou třídu funkcí. Zvláštními modely vyčíslitelnosti, které vedou k množině vypočítatelných funkcí, jsou Turingově spočítatelné funkce a obecné rekurzivní funkce .

Před přesnou definicí vypočítatelné funkce matematici často používali neformální výraz, který lze efektivně vypočítat . Tento termín se od té doby začal ztotožňovat s vyčíslitelnými funkcemi. Všimněte si, že efektivní vyčíslitelnost těchto funkcí neznamená, že je lze efektivně vypočítat (tj. Vypočítat v rozumném čase). U některých efektivně vypočítatelných funkcí lze ve skutečnosti ukázat, že jakýkoli algoritmus, který je vypočítává, bude velmi neefektivní v tom smyslu, že doba běhu algoritmu se exponenciálně (nebo dokonce superexponenciálně ) zvyšuje s délkou vstupu. Pole proveditelnou vyčíslitelnosti a výpočetních složitosti studijních funkcí, které lze vypočítat efektivní.

Podle teze Church – Turinga jsou spočítatelné funkce přesně ty funkce, které lze vypočítat pomocí mechanického výpočetního zařízení s neomezeným množstvím času a úložného prostoru. Tato práce ekvivalentně uvádí, že funkce je vyčíslitelná, pouze pokud má algoritmus. Všimněte si, že v tomto smyslu je algoritmus chápán jako posloupnost kroků, které by mohl dodržovat člověk s neomezeným časem a neomezenou zásobou pera a papíru.

Tyto Blum axiomy mohou být použity k definování abstraktní teorie výpočetní složitosti na množině vyčíslitelných funkcí. V teorii výpočetní složitosti je problém stanovení složitosti vypočítatelné funkce známý jako problém funkce .

Definice

Vypočitatelnost funkce je neformální pojem. Jedním ze způsobů, jak to popsat, je říci, že funkce je vypočítatelná, pokud lze její hodnotu získat efektivním postupem . S větší přísností je funkce vyčíslitelná pouze tehdy, existuje -li účinný postup, který při jakémkoli $k$ - tuple přirozených čísel vytvoří hodnotu . Ve shodě s touto definicí zbytek tohoto článku předpokládá, že vypočítatelné funkce berou jako argumenty konečně mnoho přirozených čísel a vytvářejí hodnotu, která je jediným přirozeným číslem. ${\ Displaystyle f: \ mathbb {N} ^{k} \ rightarrow \ mathbb {N}}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle f (\ mathbf {x})}$

Jako protějšky tohoto neformálního popisu existuje několik formálních, matematických definic. Třídu vyčíslitelných funkcí lze definovat v mnoha ekvivalentních modelech výpočtu , včetně

Turingovy stroje
μ-rekurzivní funkce
Lambda kalkul
Poštovní stroje ( Post -Turingovy stroje a štítkovací stroje ).
Zaregistrujte stroje

Ačkoli tyto modely používají různé reprezentace funkcí, jejich vstupů a výstupů, existují překlady mezi dvěma dvěma modely, a proto každý model popisuje v podstatě stejnou třídu funkcí, což vede k názoru, že formální vyčíslitelnost je přirozená a není příliš úzká .

Například, jeden může formálně vypočitatelný funkce jako u-rekurzivní funkce , které jsou dílčí funkce, které berou v konečné n-tice z přirozených čísel a vrátit jednotlivé přirozené číslo (stejně jako výše). Jsou to nejmenší třída dílčích funkcí, která zahrnuje konstantní, nástupnické a projekční funkce, a je uzavřena pod složením , primitivní rekurzí a operátorem μ .

Ekvivalentně lze vypočítatelné funkce formalizovat jako funkce, které lze vypočítat pomocí idealizovaného výpočetního agenta, jako je Turingův stroj nebo registrační stroj . Formálně lze částečnou funkci vypočítat pouze tehdy, pokud existuje počítačový program s následujícími vlastnostmi: ${\ Displaystyle f: \ mathbb {N} ^{k} \ rightarrow \ mathbb {N}}$

Pokud je definován, program se na vstupu ukončí s hodnotou uloženou v paměti počítače. ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle f (\ mathbf {x})}$
Pokud je nedefinováno, program na vstupu nikdy nekončí . ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle \ mathbf {x}}$

Charakteristika vyčíslitelných funkcí

Základní charakteristikou vypočítatelné funkce je, že musí existovat konečný postup ( algoritmus ), který říká, jak funkci vypočítat. Výše uvedené modely výpočtu poskytují různé interpretace toho, co je procedura a jak se používá, ale tyto interpretace mají mnoho vlastností. Skutečnost, že tyto modely poskytují ekvivalentní třídy vypočítatelných funkcí, vyplývá ze skutečnosti, že každý model je schopen číst a napodobovat postup pro jakýkoli jiný model, podobně jako kompilátor je schopen číst pokyny v jednom počítačovém jazyce a vydávat pokyny v jiný jazyk.

Enderton [1977] uvádí následující charakteristiky postupu pro výpočet vyčíslitelné funkce; podobná charakteristika byla dána Turingem [1936], Rogersem [1967] a dalšími.

„Pro postup musí existovat přesné pokyny (tj. Program), konečné délky.“ Každá vypočítatelná funkce tedy musí mít konečný program, který zcela popisuje, jak má být funkce vypočítána. Funkci je možné vypočítat pouze podle pokynů; není nutné žádné hádání ani zvláštní vhled.
"Pokud je proceduře dáno k -tuple x v doméně f , pak po konečném počtu diskrétních kroků musí procedura skončit a vytvořit f ( x ) ." Intuitivně postup postupuje krok za krokem, přičemž konkrétní pravidlo pokrývá, co je třeba udělat v každém kroku výpočtu. Před vrácením hodnoty funkce lze provést jen konečný počet kroků.
"Pokud je proceduře dáno k -tuple x, které není v doméně f , pak procedura může pokračovat věčně, nikdy se nezastaví. Nebo se může v určitém okamžiku zaseknout (tj. Jednu z jejích instrukcí nelze provést)" , ale nesmí předstírat, že vytváří hodnotu f v x . “ Pokud je tedy někdy nalezena hodnota pro f ( x ) , musí to být správná hodnota. Není nutné, aby výpočetní agent rozlišoval správné výsledky od těch nesprávných, protože postup je definován jako správný tehdy a jen tehdy, pokud přináší výsledek.

Enderton dále uvádí několik vysvětlení těchto 3 požadavků postupu pro vypočítatelnou funkci:

Postup musí teoreticky fungovat pro libovolně velké argumenty. Nepředpokládá se, že by argumenty byly menší než například počet atomů na Zemi.
Postup je vyžadován k zastavení po konečném počtu kroků, aby se vytvořil výstup, ale před zastavením může trvat libovolně mnoho kroků. Nepředpokládá se žádné časové omezení.
Přestože procedura může během úspěšného výpočtu využívat pouze omezené množství úložného prostoru, množství použitého prostoru není nijak omezeno. Předpokládá se, že proceduře lze poskytnout další úložný prostor, kdykoli to procedura vyžaduje.

Abychom to shrnuli, na základě tohoto pohledu je funkce vypočítatelná, pokud: (a) vzhledem k vstupu ze své domény, případně spoléhajícímu se na neomezený úložný prostor, může poskytnout odpovídající výstup podle postupu (programu, algoritmu), který je tvořen konečný počet přesných jednoznačných pokynů; (b) vrací takový výstup (zastaví) v konečném počtu kroků; a (c) pokud dostane vstup, který není v jeho doméně, buď se nikdy nezastaví, nebo se zasekne.

Pole studií výpočetní složitosti funguje s předepsanými hranicemi času a/nebo prostoru povoleného v úspěšném výpočtu.

Vypočitatelné množiny a vztahy

Sada přirozených čísel, se nazývá vypočitatelný (synonyma: rekurzivní , rozhodnutelný ), v případě, že je vypočitatelný, celková funkce $f$ taková, že pro nějaké přirozené číslo $n$ , $f$ $($ $n$ $) = 1$ , pokud $n$ je v $A$ a $f$ $($ $n$ $) = 0$ , pokud $n$ není v $A$ .

Sada přirozených čísel se nazývá spočitatelně vyčíslitelná (synonyma: rekurzivně vyčíslitelná , semidecidovatelná ), pokud existuje vyčíslitelná funkce $f$ taková, že pro každé číslo $n$ je $f (n)$ definováno právě tehdy, pokud je $n$ v sadě. Sada je tedy vyčíslitelná pouze tehdy, pokud je doménou nějaké vypočítatelné funkce. Slovo vyčíslitelné se používá, protože následující jsou ekvivalentní pro neprázdnou podmnožinu $B$ přirozených čísel:

$B$ je doménou vypočítatelné funkce.
$B$ je rozsah celkové vypočítatelné funkce. Pokud je $B$ nekonečné, lze tuto funkci považovat za injektivní .

Je-li sada $B$ je řada funkčního $f$ pak funkce může být považována za základ výčet $B$ , protože seznam $f (0), f (1), ...$ bude zahrnovat všechny prvky $B$ .

Protože každý konečný vztah k přirozeným číslům lze identifikovat s odpovídající sadou konečných posloupností přirozených čísel, lze definice pojmů spočitatelný vztah a spočitatelně vyčíslitelný vztah definovat z jejich analogů pro množiny.

Formální jazyky

V teorii vyčíslitelnosti v informatice je běžné uvažovat o formálních jazycích . Abeceda je libovolná množina. Slovo na abecedě je konečná posloupnost symbolů z abecedy; stejný symbol může být použit více než jednou. Například binární řetězce jsou přesně slova v abecedě ${0, 1}$ . Jazyk je podmnožinou sběr všech slov na pevnou abecedy. Například kolekce všech binárních řetězců, které obsahují přesně 3 jedničky, je jazykem nad binární abecedou.

Klíčovou vlastností formálního jazyka je úroveň obtížnosti potřebná k rozhodnutí, zda je dané slovo v jazyce. Musí být vyvinut nějaký kódovací systém, aby umožnil výpočetní funkci převzít libovolné slovo v jazyce jako vstup; toto je obvykle považováno za rutinu. Jazyk se nazývá vypočítatelný (synonyma: rekurzivní , rozhodnutelný ), pokud existuje vyčíslitelná funkce $f$ taková, že pro každé slovo $w$ nad abecedou je $f (w) = 1,$ pokud je slovo v jazyce, a $f (w) = 0,$ pokud slovo není v jazyce. Jazyk je tedy vyčíslitelný pouze v případě, že existuje postup, který je schopen správně zjistit, zda jsou v jazyce libovolná slova.

Jazyk je vyčíslitelně vyčíslitelný (synonyma: rekurzivně vyčíslitelný , semidecidovatelný ), pokud existuje vyčíslitelná funkce $f$ taková, že $f (w)$ je definována právě tehdy, pokud je v jazyce slovo $w$ . Termín vyčíslitelný má stejnou etymologii jako v počitatelně vyčíslitelných množinách přirozených čísel.

Příklady

Vyčíslitelné jsou následující funkce:

Každá funkce s konečnou doménou ; např. jakákoli konečná posloupnost přirozených čísel.
Každá konstantní funkce f : N ^k → N , f ( n ₁ , ... n _k ): = n .
Sčítání f : N ² → N , f ( n ₁ , n ₂ ): = n ₁ + n ₂
Největší společný dělitel dvou čísel
Bézout koeficient dvou čísel
Nejmenší primární faktor čísla

Pokud jsou f a g vyčíslitelné, platí to také pro: f + g , f * g , pokud f je unární , max ( f , g ), min ( f , g ), arg max { y ≤ f ( x )} a mnoho více kombinací. ${\ Displaystyle f \ circ g}$

Následující příklady ilustrují, že funkce může být vypočítatelná, i když není známo, který algoritmus ji vypočítá.

Funkce f taková, že f ( n ) = 1, pokud existuje sekvence alespoň n po sobě jdoucích pěti v desítkové expanzi π , a f ( n ) = 0, jinak je vypočítatelná. (Tato funkce f je buď konstantní 1 funkce, která je vypočitatelný, jinak je k takové, že f ( n ) = 1, pokud n < k a f ( n ) = 0, pokud n ≥ k . Každá taková funkce je vypočitatelný . Není známo, zda existují libovolně dlouhé běhy pěti v desítkové expanzi π, takže nevíme, která z těchto funkcí je f . Přesto víme, že funkce f musí být vyčíslitelná.)
Každý konečný segment s un počítačově sekvence přirozených čísel (jako je Busy Beaver funkce å ) je vypočitatelný. Například pro každé přirozené číslo n existuje algoritmus, který vypočítá konečnou posloupnost Σ (0), Σ (1), Σ (2), ..., Σ ( n ) - na rozdíl od skutečnosti, že neexistuje algoritmus, který počítá celou sekvenci Σ, tj. Σ ( n ) pro všechna n . „Print 0, 1, 4, 6, 13“ je tedy triviální algoritmus pro výpočet Σ (0), Σ (1), Σ (2), Σ (3), Σ (4); podobně pro jakoukoli danou hodnotu n existuje takový triviální algoritmus (i když ho nikdy nikdo nemusí znát ani produkovat) pro výpočet Σ (0), Σ (1), Σ (2), ..., Σ ( n ).

Church – Turingova práce

Tyto práce Church-Turingovy uvádí, že nějaká funkce vypočitatelný z postupu majícího tři vlastností uvedených výše se o vypočitatelný funkce. Protože tyto tři vlastnosti nejsou formálně uvedeny, nelze tezi Church -Turing dokázat. Následující fakta jsou často považována za důkaz práce:

Je známo mnoho ekvivalentních modelů výpočtu a všechny poskytují stejnou definici vypočítatelné funkce (nebo v některých případech slabší verze).
Nebyl navržen žádný silnější model výpočtu, který je obecně považován za efektivně vypočítatelný .

Church -Turingova teze se někdy používá v důkazech, aby odůvodnila, že je určitá funkce vypočítatelná, a to konkrétním popisem postupu pro výpočet. To je povoleno, protože se věří, že všechna taková použití práce lze odstranit únavným procesem psaní formálního postupu pro funkci v nějakém modelu výpočtu.

Prokazatelnost

Vzhledem k funkci (nebo podobně jako množině) může člověka zajímat nejen to, zda je spočitatelná, ale také to, zda to lze dokázat v konkrétním důkazním systému (obvykle aritmetika Peano prvního řádu ). Funkce, u které lze prokázat, že je vypočítatelná, se nazývá prokazatelně celková .

Soubor prokazatelně celkových funkcí je rekurzivně vyčíslitelný : všechny prokazatelně celkové funkce lze vyjmenovat výčtem všech jejich odpovídajících důkazů, které dokazují jejich vyčíslitelnost. To lze provést vyjmenováním všech důkazů systému důkazů a ignorováním nepodstatných.

Vztah k rekurzivně definovaným funkcím

Ve funkci definované rekurzivní definicí je každá hodnota definována pevným vzorcem prvního řádu jiných, dříve definovaných hodnot stejné funkce nebo jiných funkcí, které mohou být jednoduše konstanty. Jejich podmnožinou jsou primitivní rekurzivní funkce . Každá taková funkce je prokazatelně celková: U takové k-ary funkce f lze každou hodnotu vypočítat podle definice zpětně, iterativně a po konečném počtu iterací (jak lze snadno dokázat) je dosaženo konstanty. ${\ displaystyle f (n_ {1}, n_ {2} ... n_ {k})}$

Opak není pravdivý, protože ne každá prokazatelně celková funkce je primitivní rekurzivní. Skutečně lze vyčíslit všechny primitivní rekurzivní funkce a definovat funkci en tak, že pro všechna n , m : en ( n , m ) = f _n ( m ), kde f _n je n-ta primitivní rekurzivní funkce (pro k -ary funkce, toto bude nastaveno na f _n ( m , m ... m )). Nyní g ( n ) = en ( n , n ) +1 je prokazatelně celkový, ale ne primitivní rekurzivní, pomocí diagonalizačního argumentu: kdyby existovalo j takové, že g = f _j , dostali bychom g ( j ) = en ( j , j ) +1 = f _j ( j )+1 = g ( j ) +1, rozpor. ( Gödelova čísla všech primitivních rekurzivních funkcí mohou být vyčíslena primitivní rekurzivní funkcí, ačkoli hodnoty primitivních rekurzivních funkcí nemohou.)

Jednou z takových funkcí, která je prokazatelná úplná, ale ne primitivní rekurzivní, je Ackermannova funkce : protože je rekurzivně definována, je skutečně snadné dokázat její vyčíslitelnost (Podobný argument diagonalizace lze však také vytvořit pro všechny funkce definované rekurzivní definicí ; existují tedy prokazatelné celkové funkce, které nelze definovat rekurzivně).

Celkem funkcí, které nejsou prokazatelně úplné

Ve zvukově důkazním systému je každá prokazatelně celková funkce skutečně úplná, ale opak není pravdivý: v každém důkazním systému prvního řádu, který je dostatečně silný a zdravý (včetně aritmetiky Peano), lze prokázat (v jiném důkazním systému) existence celkových funkcí, které nelze v systému důkazů celkem prokázat.

Pokud jsou všechny vyčíslitelné funkce sečteny prostřednictvím Turingových strojů, které je produkují, pak výše uvedené tvrzení lze zobrazit, pokud je důkazní systém zdravý, podobným diagonalizačním argumentem, jaký byl použit výše, s využitím výčtu prokazatelně celkových funkcí, který byl uveden dříve. Jeden používá Turingův stroj, který vyjmenovává příslušné důkazy, a pro každý vstup n zavolá f _n ( n ) (kde f _n je n -tou funkcí podle tohoto výčtu) vyvoláním Turingova stroje, který jej vypočítá podle n -tého důkazu . Takový Turingův stroj se zaručeně zastaví, pokud je kontrolní systém v pořádku.

Nepočitatelné funkce a neřešitelné problémy

Každá vyčíslitelná funkce má konečný postup, který poskytuje explicitní a jednoznačné pokyny, jak ji vypočítat. Kromě toho musí být tento postup zakódován do konečné abecedy používané výpočetním modelem, takže existuje pouze spočitatelně mnoho vypočítatelných funkcí. Funkce mohou být například kódovány pomocí řetězce bitů (abeceda $Σ = {0, 1$ }).

Skutečná čísla jsou nepočítatelná, takže většina reálných čísel nelze spočítat. Viz vypočítatelné číslo . Sada konečných funkcí na přirozených číslech je nespočetná, takže většina z nich není vyčíslitelná. Konkrétními příklady takových funkcí jsou zaneprázdněný bobr , složitost Kolmogorova nebo jakákoli funkce, která vydává číslice nepočitatelného čísla, například Chaitinova konstanta .

Podobně většina podmnožin přirozených čísel není vypočítatelná. Problém zastavení byl první takovou sadou, která byla postavena. Entscheidungsproblem , navržený David Hilbert , zeptal, jestli existuje účinný postup k určení, které matematické výkazy (kódovány jako přirozených čísel) jsou pravdivé. Turing a Church ve třicátých letech nezávisle ukázali, že tento soubor přirozených čísel nelze spočítat. Podle teze Church -Turing neexistuje žádný účinný postup (s algoritmem), který by tyto výpočty mohl provádět.

Rozšíření vyčíslitelnosti

Relativní vyčíslitelnost

Pojem vyčíslitelnost z funkce může být relativizovány na libovolný sadu z přirozených čísel A . Funkce f je definována jako vyčíslitelná v A (ekvivalentně A -vypočítatelná nebo vypočítatelná ve vztahu k A ), pokud splňuje definici vypočítatelné funkce s úpravami umožňujícími přístup k A jako orákulum . Stejně jako u konceptu vypočítatelné funkce lze relativní vypočítatelnosti dát ekvivalentní definice v mnoha různých modelech výpočtu. To se běžně provádí doplněním model výpočtu s přídavným primitivní operace, která je, zda daná celé číslo je členem A . Můžeme také hovořit o f, který lze vypočítat v g identifikací g s jeho grafem.

Teorie vyšší rekurze

Hyperaritmetická teorie studuje ty sady, které lze vypočítat z počitatelného pořadového počtu iterací Turingova skoku prázdné množiny. To je ekvivalentní množinám definovaným univerzálním i existenciálním vzorcem v jazyce aritmetiky druhého řádu a některým modelům Hypercomputation . Byly studovány ještě obecnější rekurzivní teorie, jako je teorie E-rekurze, ve které lze jako argument pro E-rekurzivní funkci použít libovolnou množinu.

Hyper-výpočet

Ačkoli teze Church -Turing uvádí, že spočitatelné funkce zahrnují všechny funkce s algoritmy, je možné uvažovat o širších třídách funkcí, které uvolňují požadavky, které musí algoritmy mít. Pole Hypercomputation studuje modely výpočtu, které jdou nad rámec běžného Turingova výpočtu.

Viz také

Reference

Cutland, Nigel. Vypočitatelnost . Cambridge University Press, 1980.
Enderton, HB Prvky teorie rekurze. Handbook of Mathematical Logic (North-Holland 1977) s. 527–566.
Rogers, H. Teorie rekurzivních funkcí a efektivní výpočet (McGraw – Hill 1967).
Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem . Proceedings of the London Mathematical Society , Series 2, Volume 42 (1937), p.230–265. Přetištěno v M. Davis (ed.), The Undecidable , Raven Press, Hewlett, NY, 1965.

Languages

In other projects