Vyčíslitelnost - Computability

Vypočitatelnost je schopnost efektivně vyřešit problém. Jedná se o klíčové téma v oblasti teorie vypočítatelnosti v rámci matematické logiky a teorie výpočtu v rámci výpočetní techniky . Vyčíslitelnost problému úzce souvisí s existencí algoritmu k jeho vyřešení.

Nejčastěji studovanými modely vypočitatelnosti jsou Turingovy vypočítatelné a μ-rekurzivní funkce a lambda kalkul , které všechny mají výpočetně ekvivalentní výkon. Rovněž jsou studovány jiné formy vypočítatelnosti: pojmy vypočítatelnosti slabší než Turingovy stroje jsou studovány v teorii automatů , zatímco pojmy vypočítatelnosti silnější než Turingovy stroje jsou studovány v oblasti hyperpočítání .

Problémy

Ústřední myšlenkou ve vyčíslitelnosti je myšlenka ( výpočetního ) problému , což je úkol, jehož vyčíslitelnost lze prozkoumat.

Existují dva klíčové typy problémů:

A rozhodnutí problém řeší množina S , který může být množina řetězců, přirozených čísel, či jiných předmětů odebraných z nějakého většího souboru U . Konkrétní příklad tohoto problému je rozhodnout, neboť prvek u o U , ať už u je v S . Například nechť U je množina přirozených čísel a S množina prvočísel. Odpovídající rozhodovací problém odpovídá testování primality .
Problém funkce se skládá z funkce f ze sady U na nastavenou V . Instance problému je pro výpočet, vzhledem k tomu, prvek U v U , odpovídající prvek f ( u ) v V . Například U a V může být množina všech konečných binárních řetězců a f může mít řetězec a vrátit řetězec získaný obrácením číslic vstupu (takže f (0101) = 1010).

Mezi další typy problémů patří problémy s vyhledáváním a optimalizací .

Jedním z cílů teorie vypočítatelnosti je určit, které problémy nebo třídy problémů lze vyřešit v každém modelu výpočtu.

Formální modely výpočtu

Model výpočtu je formální popis konkrétního typu výpočetního procesu. Popis má často podobu abstraktního stroje, který je určen k provádění daného úkolu. Obecné modely výpočtu ekvivalentní Turingovu stroji (viz Church-Turingova práce ) zahrnují:

Lambda kalkul: Výpočet se skládá z počátečního výrazu lambda (nebo dvou, pokud chcete oddělit funkci a její vstup) a konečné sekvence výrazů lambda, z nichž každý je odvozen od předchozího výrazu jednou aplikací redukce beta .
Kombinovaná logika: Koncept, který má mnoho podobností s -calculus, ale také existují významné rozdíly (např. Kombinátor Y s pevným bodem má normální formu v kombinační logice, ale ne v -calculus). Kombinatorická logika byla vyvinuta s velkými ambicemi: pochopit podstatu paradoxů, učinit základy matematiky ekonomičtějšími (koncepčně), eliminovat pojem proměnných (a tak objasnit jejich roli v matematice). ${\ displaystyle \ lambda}$ ${\ displaystyle \ lambda}$
μ-rekurzivní funkce: Výpočet se skládá z μ-rekurzivní funkce, tj. Její definující posloupnosti, jakékoli vstupní hodnoty a posloupnosti rekurzivních funkcí, které se objevují v určující posloupnosti se vstupy a výstupy. Pokud se tedy v definující posloupnosti rekurzivní funkce $f (x)$ objeví funkce $g (x)$ a $h (x, y)$ , pak členy tvaru $g (5) = 7$ nebo $h (3,2) = 10$ se může objevit. Každá položka v této sekvenci musí být aplikací základní funkce nebo následovat z výše uvedených položek pomocí složení , primitivní rekurze nebo μ-rekurze . Například pokud $f (x) = h (x, g (x))$ , pak aby se objevilo $f (5) = 3$ , musí se výše vyskytovat pojmy jako $g (5) = 6$ a $h (5,6) = 3$ . Výpočet končí pouze v případě, že poslední člen udává hodnotu rekurzivní funkce aplikované na vstupy.
Systémy přepisování řetězců: Zahrnuje Markovovy algoritmy , které používají pravidla podobná gramatice pro práci s řetězci symbolů; také Post kanonický systém .
Zaregistrujte stroj: Teoretická idealizace počítače. Existuje několik variant. Ve většině z nich může každý registr obsahovat přirozené číslo (neomezené velikosti) a pokyny jsou jednoduché (a málo), např. Existuje pouze dekrementace (v kombinaci s podmíněným skokem) a přírůstek (a zastavení). Nedostatku nekonečného (nebo dynamicky rostoucího) externího úložiště (viděného u Turingových strojů) lze porozumět nahrazením jeho role technikami číslování Gödel : skutečnost, že každý registr obsahuje přirozené číslo, umožňuje možnost představovat komplikovanou věc (např. posloupnost nebo matice atd.) příslušným obrovským přirozeným číslem - jednoznačnost reprezentace i interpretace lze určit pomocí řady teoretických základů těchto technik.
Turingův stroj: Podobně jako stroj s konečným stavem, až na to, že vstup je poskytován na provedení „pásky“, z něhož může Turingův stroj číst, zapisovat na něj nebo se přesouvat tam a zpět za svou „hlavu“ pro čtení / zápis. Páska se může zvětšit na libovolnou velikost. Turingův stroj je schopen provádět složité výpočty, které mohou mít libovolné trvání. Tento model je možná nejdůležitějším modelem výpočtu v počítačové vědě, protože simuluje výpočet při absenci předdefinovaných limitů zdrojů.
Multitape Turingův stroj: Tady může být více než jedna páska; navíc na jedné kazetě může být více hlav. Překvapivě lze jakýkoli výpočet, který lze provést tímto typem stroje, provést také běžný Turingův stroj, i když ten může být pomalejší nebo vyžadovat větší celkovou oblast jeho pásky.
P ′ ′: Stejně jako Turingovy stroje i P ′ ′ používá nekonečnou pásku symbolů (bez náhodného přístupu) a poměrně minimalistický soubor pokynů. Ale tyto pokyny jsou velmi odlišné, takže na rozdíl od Turingových strojů nemusí P ′ ′ udržovat odlišný stav, protože všechny funkce podobné „paměti“ mohou poskytovat pouze pásky. Místo přepsání aktuálního symbolu může na něm provést modulární aritmetický přírůstek. P ′ ′ má také pár instrukcí pro cyklus a kontroluje prázdný symbol. Přes svou minimalistickou povahu se stal rodičovským formálním jazykem implementovaného a (pro zábavu) používaného programovacího jazyka s názvem Brainfuck .

Kromě obecných výpočetních modelů jsou některé speciální výpočetní modely užitečné pro speciální omezené aplikace. Regulární výrazy například určují řetězcové vzory v mnoha kontextech, od kancelářského softwaru pro produktivitu až po programovací jazyky . Finální automaty, další matematicky ekvivalentní regulárním výrazům, se používají při navrhování obvodů a při některých druzích řešení problémů. Bezkontextové gramatiky určují syntaxi programovacího jazyka. Non-deterministické zásobníkové automaty jsou další formalizmus ekvivalentní bezkontextových gramatik.

Různé modely výpočtu mají schopnost provádět různé úkoly. Jedním ze způsobů, jak měřit sílu výpočetního modelu, je studium třídy formálních jazyků, které model může generovat; takovým způsobem je získána Chomského hierarchie jazyků.

Mezi další omezené modely výpočtu patří:

Deterministický konečný automat (DFA): Také se nazývá stroj konečného stavu. Všechna skutečná výpočetní zařízení, která dnes existují, lze modelovat jako stroj v konečném stavu, protože všechny skutečné počítače fungují na omezených zdrojích. Takový stroj má sadu stavů a sadu přechodů stavů, které jsou ovlivněny vstupním proudem. Určité státy jsou definovány jako přijímající státy. Vstupní proud se přivádí do zařízení po jednom znaku a přechody stavu pro aktuální stav se porovnávají se vstupním proudem, a pokud existuje odpovídající přechod, stroj může vstoupit do nového stavu. Pokud je stroj na konci vstupního proudu v přijímajícím stavu, je přijat celý vstupní proud.
Nedeterministický konečný automat (NFA): Další jednoduchý model výpočtu, i když jeho sled zpracování není jednoznačně určen. Lze jej interpretovat jako více výpočetních cest současně přes konečný počet stavů. Je však možné dokázat, že jakýkoli NFA je redukovatelný na ekvivalentní DFA.
Pushdown automat: Podobně jako stroj s konečným stavem, až na to, že má k dispozici vykonávací zásobník, který může růst na libovolnou velikost. Přechody stavu dodatečně určují, zda se má do zásobníku přidat symbol nebo odebrat symbol ze zásobníku. Je výkonnější než DFA díky zásobníku s nekonečnou pamětí, i když je kdykoli přístupný pouze horní prvek zásobníku.

Síla automatů

S těmito výpočetními modely v ruce můžeme určit, jaké jsou jejich limity. To znamená, jaké třídy jazyků mohou přijmout?

Síla strojů s konečným stavem

Počítačoví vědci nazývají jakýkoli jazyk, který může stroj s konečným stavem přijmout, běžným jazykem . Kvůli omezení, že počet možných stavů v automatu konečných stavů je konečný, vidíme, že abychom našli jazyk, který není pravidelný, musíme zkonstruovat jazyk, který by vyžadoval nekonečný počet stavů.

Příkladem takového jazyka je sada všech řetězců skládajících se z písmen „a“ a „b“, která obsahují stejný počet písmen „a“ a „b“. Chcete-li zjistit, proč tento jazyk nelze správně rozpoznat strojem s konečným stavem, předpokládejme nejprve, že takový stroj M existuje. M musí mít určitý počet stavů n . Nyní zvažte řetězec x skládající se z 'a následovaných ' b. ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + 1)}$

Jak M čte v x , musí existovat nějaký stav ve stroji, který se opakuje, jak se čte v první sérii „a“, protože existují „a“ a pouze n stavů podle principu pigeonhole . Zavolejte tento stav S a dále nechme d být počet 'a, které náš stroj přečetl, aby se dostal z prvního výskytu S do nějakého následného výskytu během sekvence' a '. Víme tedy, že v tomto druhém výskytu S můžeme přidat dodatečné d (kde ) ‚áček a budeme zase na státní S . To znamená, že víme, že řetězec „a“ musí skončit ve stejném stavu jako řetězec „a“. To znamená, že pokud náš stroj přijímá x , musí také přijmout řetězec 'a následovaný ' b, který není v jazyce řetězců obsahujících stejný počet 'a' a 'b'. Jinými slovy, M nemůže správně rozlišovat mezi řetězcem se stejným počtem písmen „a“ a „b“ a řetězcem s „a “ a „b“. ${\ displaystyle (n + 1)}$ ${\ displaystyle d> 0}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle n + 1}$

Víme tedy, že tento jazyk nemůže žádný stroj s konečným stavem správně přijmout, a není tedy běžným jazykem. Obecnější forma tohoto výsledku se nazývá Pumping lemma pro běžné jazyky , kterou lze použít k ukázání, že široké třídy jazyků nelze rozpoznat pomocí stroje s konečným stavem.

Síla pushdown automatů

Počítačoví vědci definují jazyk, který může být přijímán automatizací, jako bezkontextový jazyk , který lze specifikovat jako bezkontextovou gramatiku . O jazyce skládajícím se ze řetězců se stejným počtem písmen „a“ a „b“, který jsme ukázali, nebyl běžným jazykem, může rozhodnout automatický rozevírací seznam. Obecně platí, že automat se může chovat stejně jako stroj s konečným stavem, takže může rozhodovat o jakémkoli jazyce, který je běžný. Tento model výpočtu je tedy přísně výkonnější než stroje s konečným stavem.

Ukázalo se však, že existují jazyky, o kterých nemůže rozhodnout ani push-down automat. Výsledek je podobný jako u regulárních výrazů a nebude zde podrobně popsán. Pro bezkontextové jazyky existuje lumpovací lemma . Příkladem takového jazyka je sada prvočísel.

Síla Turingových strojů

Turingovy stroje mohou rozhodovat o jakémkoli bezkontextovém jazyce, kromě jazyků, které nelze určit pomocí automatu, jako je jazyk skládající se z prvočísel. Jedná se tedy o přísně výkonnější model výpočtu.

Protože Turingovy stroje mají schopnost „zálohovat“ na své vstupní pásce, je možné, aby Turingův stroj běžel po dlouhou dobu způsobem, který u jiných dříve popsaných výpočetních modelů není možný. Je možné postavit Turingův stroj, který na některých vstupech nikdy nedojde (nezastaví). Říkáme, že Turingův stroj může rozhodnout jazyk, pokud se nakonec zastaví na všech vstupech a dá odpověď. Jazyk, o kterém lze tak rozhodnout, se nazývá rekurzivní jazyk . Můžeme dále popsat Turingovy stroje, které se nakonec zastaví a poskytnou odpověď na jakýkoli vstup v jazyce, ale který může běžet navždy pro vstupní řetězce, které nejsou v daném jazyce. Takové Turingovy stroje nám mohly říci, že daný řetězec je v jazyce, ale nikdy si nemůžeme být jisti na základě jeho chování, že daný řetězec není v jazyce, protože v takovém případě může běžet navždy. Jazyk, který je takovým Turingovým strojem přijímán, se nazývá rekurzivně vyčíslitelný jazyk .

Ukázalo se, že Turingův stroj je mimořádně výkonný model automatů. Pokusy změnit definici Turingova stroje tak, aby vznikl výkonnější stroj, se překvapivě setkaly s neúspěchem. Například přidání další pásky k Turingovu stroji, které mu dá dvourozměrný (nebo trojrozměrný) nekonečný povrch pro práci, může být simulováno Turingovým strojem se základní jednorozměrnou páskou. Tyto modely proto nejsou výkonnější. Důsledkem teze Church-Turing je ve skutečnosti to, že neexistuje žádný rozumný model výpočtu, který by mohl rozhodovat o jazycích, o nichž by nemohl rozhodovat Turingův stroj.

Otázkou pak je: existují jazyky, které jsou rekurzivně vyčíslitelné, ale ne rekurzivní? A navíc existují jazyky, které nejsou ani rekurzivně spočetné?

Problém zastavení

Problém zastavení je jedním z nejznámějších problémů v počítačové vědě, protože má hluboké důsledky pro teorii vypočítatelnosti a pro to, jak používáme počítače v každodenní praxi. Problém lze formulovat:

Vzhledem k popisu Turingova stroje a jeho počátečního vstupu určete, zda se program při spuštění na tomto vstupu vůbec zastaví (dokončí). Alternativou je, že běží navždy bez zastavení.

Tady se neptáme na jednoduchou otázku o prvočísle nebo palindromu, ale místo toho obracíme tabulky a žádáme Turingův stroj, aby odpověděl na otázku o jiném Turingově stroji. Je možné ukázat (Viz hlavní článek: Problém zastavení ), že není možné postavit Turingův stroj, který by na tuto otázku mohl odpovědět ve všech případech.

To znamená, že jediný obecný způsob, jak zjistit, zda se daný program zastaví na konkrétním vstupu ve všech případech, je jednoduše jej spustit a zjistit, zda se zastaví. Pokud se zastaví, pak víte, že se zastaví. Pokud se však nezastaví, možná nikdy nevíte, zda se nakonec zastaví. Jazyk skládající se ze všech popisů Turingova stroje spárovaných se všemi možnými vstupními toky, na kterých se tyto Turingovy stroje nakonec zastaví, není rekurzivní. Problém zastavení se proto nazývá nevypočitatelný nebo nerozhodnutelný .

Rozšíření problému zastavení se nazývá Riceova věta , která uvádí, že je obecně nerozhodné, zda daný jazyk má nějakou konkrétní netriviální vlastnost.

Kromě rekurzivně nesčetných jazyků

Problém zastavení je snadné vyřešit, pokud však dovolíme, aby Turingův stroj, který rozhodne, že může běžet navždy, když dostane vstup, který je reprezentací Turingova stroje, který se sám nezastaví. Zastavovací jazyk je proto rekurzivně spočetný. Je možné konstruovat jazyky, které však ani rekurzivně nelze spočítat.

Jednoduchým příkladem takového jazyka je doplněk zastavovacího jazyka; že je jazyk skládající se ze všech Turingových strojů spárována s vstupních řetězcích, kde Turing stroje se není zastavují na jejich vstupu. Abychom zjistili, že tento jazyk není rekurzivně vyčíslitelný, představme si, že postavíme Turingův stroj M, který je schopen dát definitivní odpověď na všechny takové Turingovy stroje, ale že může běžet navždy na jakémkoli Turingově stroji, který se nakonec zastaví. Poté můžeme sestavit další Turingův stroj, který simuluje provoz tohoto stroje, spolu s přímou simulací provádění stroje uvedeného ve vstupu také prokládáním provádění těchto dvou programů. Protože se přímá simulace nakonec zastaví, pokud program, který simuluje, zastaví, a protože podle předpokladu se simulace M nakonec zastaví, pokud se vstupní program nikdy nezastaví, víme, že se nakonec zastaví jedna z jejích paralelních verzí. je tedy rozhodujícím faktorem problému zastavení. Dříve jsme však ukázali, že problém zastavení je nerozhodnutelný. Máme rozpor, a tak jsme ukázali, že náš předpoklad, že M existuje, je nesprávný. Doplněk zastavovacího jazyka proto není rekurzivně vyčíslitelný. ${\ displaystyle M '}$ ${\ displaystyle M '}$ ${\ displaystyle M '}$

Modely založené na souběžnosti

Byla vyvinuta řada výpočetních modelů založených na souběžnosti , včetně paralelního stroje s náhodným přístupem a Petriho sítě . Tyto modely souběžného výpočtu stále neimplementují žádné matematické funkce, které nemohou být implementovány Turingovými stroji.

Silnější modely výpočtu

Church-Turingova teze domněnky, že neexistuje žádný účinný model výpočtu, které mohou vypočítat více matematických funkcí než Turing stroj. Počítačoví vědci si představili mnoho druhů hyperpočítačů , modelů výpočtu, které přesahují Turingovu vypočítatelnost.

Nekonečné provedení

Představte si stroj, kde každý krok výpočtu vyžaduje polovinu času předchozího kroku (a doufejme, že polovinu energie předchozího kroku ...). Pokud normalizujeme na 1/2 časové jednotky množství času potřebného pro první krok (a na 1/2 energetické jednotky množství energie potřebné pro první krok ...), provedení by vyžadovalo

{\ displaystyle 1 = \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {2 ^ {n}}} = {\ frac {1} {2}} + {\ frac {1} {4}} + {\ frac {1} {8}} + {\ frac {1} {16}} + \ cdots}

časová jednotka (a 1 energetická jednotka ...), které mají běžet. Tato nekonečná řada konverguje k 1, což znamená, že tento stroj Zeno může provádět nespočetně nekonečný počet kroků v 1 časové jednotce (pomocí 1 energetické jednotky ...). Tento stroj je schopen rozhodnout o zastavení problému přímou simulací provádění daného stroje. Rozšířením by fungovala jakákoli konvergentní nekonečná [musí být prokazatelně nekonečná] řada. Za předpokladu, že nekonečná řada konverguje k hodnotě n , by stroj Zeno dokončil nespočetně nekonečné provedení v n časových jednotkách.

Stroje Oracle

Tzv. Stroje Oracle mají přístup k různým „věštcům“, které poskytují řešení konkrétních nerozhodnutelných problémů. Například Turingův stroj může mít „zastavení věštění“, které okamžitě odpovídá, zda se daný Turingův stroj na daném vstupu někdy zastaví. Tyto stroje jsou ústředním tématem studia teorie rekurze .

Limity hyper-výpočtu

I tyto stroje, které zdánlivě představují hranici automatů, kterou jsme si dokázali představit, narážejí na svá vlastní omezení. I když každý z nich může vyřešit problém zastavení u Turingova stroje, nemůže vyřešit svou vlastní verzi problému zastavení. Například stroj Oracle nemůže odpovědět na otázku, zda se daný stroj Oracle někdy zastaví.

Viz také

Reference

Michael Sipser (1997). Úvod do teorie výpočtu . PWS Publishing. ISBN 0-534-94728-X. Část druhá: Teorie vypočítatelnosti, kapitoly 3–6, s. 123–222.
Christos Papadimitriou (1993). Výpočetní složitost (1. vyd.). Addison Wesley. ISBN 0-201-53082-1. Kapitola 3: Vyčíslitelnost, str. 57–70.
Barry Cooper (2004). Teorie vypočítatelnosti (1. vyd.). Chapman & Hall / CRC. ISBN 978-1-58488-237-4.

Languages

In other projects