Turingův stroj

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Umělecké znázornění Turingova stroje.

Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem. Skládá se z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a pravostranně nekonečné pásky pro zápis mezivýsledků. Využívá se pro modelování algoritmů v teorii vyčíslitelnosti.

Jeden ze způsobu vyjádření Churchovy-Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj.

Od výpočetní síly Turingova stroje se odvozuje turingovská úplnost: turingovsky úplné jsou právě ty programovací jazyky nebo počítače, které mají stejnou výpočetní sílu jako Turingův stroj.

Definice[editovat | editovat zdroj]

Turingův stroj je šestice \ M=(Q, \Gamma, s, b, F, \delta) kde :

  • Q je konečná množina vnitřních stavů
  • \Gamma je konečná abeceda symbolů a znaků
  • s\in Q je počáteční stav
  • b\in \Gamma je symbol reprezentující prázdný symbol ( b neni součástí vstupní abecedy přijímaného řetězce)
  • F\subseteq Q je množina koncových stavů
  • \delta: Q\times\Gamma\rightarrow Q\times\Gamma \times \{L,R\} přechodová funkce, kde:
    • L znamená posun čtecí hlavy vlevo
    • R znamená posun čtecí hlavy vpravo

Konfigurace[editovat | editovat zdroj]

Konfigurace Turingova stroje je prvek \left \langle q, s, n \right \ranglemnožiny Q\times\{yb^\omega \mid y \in \Gamma^*\}\times \mathbb{N}_0, kde q je aktuální stav, s je nejmenší souvislá část pásky obsahující všechny neprázdné symboly a n je pozice čtecí hlavy (číslo buňky).

Vzhledem k tomu, že množiny Q a \Gamma jsou obvykle disjunktní (resp. lze vhodnou volbou prvků množiny Q dosáhnout toho, aby byly), používá se též kompaktní tvar, ve kterém se konfigurace Turingova stroje zapisuje jako řetězec symbolů odpovídající stavu pásky a aktuální stav se do něj vloží před symbol, na kterém se nachází čtecí hlavy. Pokud například páska obsahuje 1234, stroj je ve stavu q a čtecí hlava stojí na symbolu 2, zapíše se tato konfigurace jeko 1q234.

Počáteční konfigurace Turingova stroje pro vstup w\in\Gamma^* je konfigurace (s,wb^\omega,0), resp. v kompaktním zápisu sw.

Výpočet[editovat | editovat zdroj]

Na začátku výpočtu je Turingův stroj v počáteční konfiguraci a na pásce je zapsané vstupní slovo. Dále pracuje v jednotlivých krocích:

  1. pokud je aktuální stav zároveň stavem koncovým, výpočet končí
  2. čtecí hlava přečte jeden vstupní symbol z buňky, na které se právě nachází
  3. pokud je v přechodové funkci pro aktuální stav a pro přečtený symbol definovaný přechod, provede se (v případě více možných přechodů u nedeterministických strojů se vybere jeden náhodně):
    • změní se stav
    • na aktuální pozici hlavy se zapíše příslušný symbol
    • hlava se příslušným způsobem posune (či neposune)

Neformální popis[editovat | editovat zdroj]

Neformálně řečeno je TS primitivní počítač s nejjednoduššími instrukcemi a jednou zapisovací páskou, pamětí. Existuje více různých modelů TS, které jsou ovšem co do síly výpočtu ekvivalentní. Další modely se zavádějí kvůli jednodušší demonstraci daných problémů. Za základní model můžeme považovat ten s jednostranně nekonečnou páskou. Samotný TS poté postupuje podobně jako konečný automat, ale s tím zásadním rozdílem, že má nekonečně velkou pásku, na kterou může zapisovat a libovolně se po ní může pohybovat. Na začátku definujeme stavy a přechodové funkce, přijímající a zamítající stav a abecedu, nad kterou TS pracuje. Poté na pásku TS vložíme slovo, které se skládá ze symbolů abecedy a TS se pokusí toto slovo přijmout. Při tom můžeme po TS chtít, aby nám nějakým způsobem pozměnil symboly na pásce, čímž můžeme realizovat nějaký výpočet, například násobení. TS může ukončit svůj výpočet třemi možnými stavy: pokud vstupní slovo w vyhovuje podmínkám, TS slovo přijme (akceptuje). Pokud slovo w nevyhovuje, TS slovo odmítne. Třetí možností je, že se TS zacyklí, což znamená, že TS bude donekonečna přecházet mezi nějakými stavy a nikdy se nezastaví. Turingův stroj tedy neumí vyřešit všechny problémy. Další příklady a důkazy budou následovat.

Příklad Turingova stroje[editovat | editovat zdroj]

Napíšeme jednoduchý TS, který bude mít za úkol zjistit, zda slovo napsané na pásku má tvar 0n1n, n>0 (zda řetězec obsahuje n nul a následně n jedniček). Víme, že konečný automat tento problém řešit neumí, ale zásobníkový automat to již řešit umí. Ukážeme, jak by vypadal TS M, který by tento problém vyřešil.

Základní myšlenkou algoritmu je, že náš Turingův stroj vždy vymaže počáteční 0, přesune hlavu na konec slova, vymaže z něj poslední 1 a přesune se zpět na začátek slova. Tuto činnost opakuje, dokud slovo nevymaže nebo se nedostane do stavu, kdy další krok není definován (v tom případě slovo do jazyka nepatří).

Formální zápis: Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7\}, \Gamma = \{0, 1, b \}, počáteční stav je q_0 a F = \{ q_7 \}. Přechodová funkce by vypadala následovně:

  1. \delta( q_0, 0 ) = ( q_1, b, R) vymažeme počáteční nulu a zahájíme přesun čtecí hlavy doprava
  2. \delta( q_1, 0 ) = ( q_1, 0, R) přesouváme hlavu doprava přes nuly, pásku neměníme
  3. \delta( q_1, 1 ) = ( q_2, 1, R) narazili jsme na první jedničku, měníme stav a pokračujeme v pohybu doprava
  4. \delta( q_2, 1 ) = ( q_2, 1, R) přesouváme hlavu doprava přes jedničky
  5. \delta( q_2, b ) = ( q_3, b, L) ocitli jsme se za slovem, vrátíme se před poslední symbol
  6. \delta( q_3, 1 ) = ( q_4, b, L) vymažeme poslední jedničku a přesuneme se na předchozí znak
  7. \delta( q_4, b ) = ( q_7, b, R) pokud jsme v kroku 6 vymazali poslední symbol slova, algoritmus končí přechodem do koncového stavu
  8. \delta( q_4, 1 ) = ( q_5, 1, L) jinak zahájíme přesun doleva
  9. \delta( q_5, 1 ) = ( q_5, 1, L) přesouváme hlavu doleva přes jedničky
  10. \delta( q_5, 0 ) = ( q_6, 0, L) narazili jsme na poslední nulu, měníme stav a pokračujeme v pohybu doleva
  11. \delta( q_6, 0 ) = ( q_6, 0, L) přesouváme hlavu doleva přes nuly
  12. \delta( q_6, b ) = ( q_0, b, R) dostali jsme se před slovo, vrátíme se na jeho první znak a začínáme zase od začátku, slovo je nyní o dva znaky kratší

Několik poznámek k algoritmu:

  • Čtecí hlava se může libovolně pohybovat po pásce tím způsobem, že přečte symbol A, zapíše (stejný) symbol A a posune se doleva nebo doprava. Tím se hlava může posunout o libovolný počet míst, aniž by cokoliv na pásce změnila. Tento přístup je použit ve většině kroků (s výjimkou kroků 1 a 6, kde se obsah pásky mění).
  • Místo vymazání by bylo možné zpracované symboly 0 a 1 „škrtnout“, tedy nahradit speciálním znakem, který by se pro tento účel přidal do páskové abecedy.
  • Za posledním symbolem ze vstupního slova w se nachází prázdné symboly, takže čtecí hlava může takto poznat konec slova. Začátek slova může poznat stejným způsobem. V opačném případě by bylo nutné například přidat speciální symbol před začátek slova w, který označí začátek slova.

Ukázka výpočtu výše uvedeného Turingova stroje při vstupu 0011. Zapíšeme ji jako posloupnost po sobě následujících konfigurací. Nad šipkou představující jeden krok výpočtu je vždy uvedeno číslo použitého pravidla: q_0 0011 \overset{1}{ \rarr} q_1 011 \overset{2}\rarr 0 q_1 11 \overset{3}\rarr 01 q_2 1,\overset{4}\rarr 011 q_2 \overset{5}\rarr 01 q_3 1 \overset{6}\rarr 0 q_4 1 \overset{8}\rarr q_5 01 \overset{10}\rarr q_6 b01 \overset{12}\rarr q_0 01 \overset{1}\rarr q_1 1 \overset{3}\rarr 1 q_2 \overset{5}\rarr q_3 1 \overset{6}\rarr q_4 b \overset{7}\rarr q_7 b. Turingův stroj dospěl do koncového stavu, výpočet končí úspěšně.

Ukázka výpočtu při vstupu 001: q_0 001 \overset{1}\rarr q_1 01 \overset{2}\rarr 0 q_1 1 \overset{3}\rarr 01 q_2,\overset{5}\rarr 0 q_3 1 \overset{6}\rarr q_4 0. Ale \delta(q_4, 0) není definováno, výpočet končí neúspěšně. Do stavu q_4 se náš stroj dostane po vymazání poslední 1. U slova 0^n1^n mohou v této situaci nastat jen dva případy − buď se tím slovo vyprázdnilo (instrukce 7) nebo ještě jeho část zbývá, ta ale musí končit jedničkami (instrukce 8).

Ukázka výpočtu při vstupu 0101: q_0 0101 \overset{1}\rarr q_1 101 \overset{3}\rarr 1 q_2 01. Výpočet opět končí neúspěšně, protože přechodová funkce \delta(q_2, 0) není definována. V korektním slově řetězec jedniček zahájený za první nulou pokračuje až do konce slova, ve stavu q_2 tedy stroj může na pásce najít jen symboly 1 nebo b.

Modifikace[editovat | editovat zdroj]

Existuje velké množství různých modifikací Turingova stroje, všechny však mají stejnou sílu, tzn. že přijímají stejnou třídu jazyků jako základní model.

  • TS s možností provedení výpočtu bez posunu čtecí hlavy
    • přechodová funkce je rozšířena o N (čtecí hlava zůstane na místě)
    • \delta: Q\times\Gamma\rightarrow Q\times\Gamma \times \{L,R,N\}
    • Idea důkazu, že se jedná o výpočetně stejně silný TS: posun N (žádný posun čtecí hlavy) můžeme na běžném TS zařídit tak, že čtecí hlava přečte vstupní symbol z buňky, na které se nachází, provede příslušnou operaci a posune se doprava (R). Nyní opět přečte symbol z buňky, zapíše tam stejný symbol (tj. nezmění symbol, na kterém se hlava nachází) a posune se doleva (L). Tím jsme dostali čtecí hlavu do předchozího umístění a žádný jiný symbol nebyl změněn. Pokud máme jako výchozí TS s levou zarážkou (páska je nekonečná jen zprava), je důležité posouvat se nejprve vpravo, protože pokud bychom se posunuli doleva a čtecí hlava by stála na prvním symbolu, posunula by se čtecí hlava v druhém kroku na druhý symbol.
  • TS s oboustranně nekonečnou páskou
    • páska není zleva ohraničená
    • možný posun čtecí hlavy doleva z libovolné konfigurace
    • Idea důkazu:
      • Jako první dokážeme, že na běžném TS (označme TS) dokážeme nasimulovat TS s oboustranně nekonečnou páskou (označme TS). V TS si zvolíme takový symbol D, který se nenachází v abecedě symbolů (\Gamma). Na začátku se tento symbol nachází nalevo od vstupního slova w. Nyní nadefinujeme TS tak, že ve chvíli, kdy čtecí hlava dosáhne na symbol D, posune celý obsah pásky napravo od symbolu D o jednu buňku doprava a vrátí čtecí hlavu na vzniklou prázdnou buňku, které vznikla mezi obsahem pásky a symbolem D. Tím dosáhneme funkčnosti TS.
      • A nyní naopak. Zlomíme TS tak, aby nám vznikly dva TS s zleva omezenou páskou. Tyto dvě pásky dáme pod sebe a nadefinujeme přechody tak, aby když čtecí hlava dojde na levý konec horní pásky, aby při dalším pokusu o posun doleva přešla na spodní pásku a pokračovala doprava. A naopak. Když se čtecí hlava dostane na levý okraj spodní pásky a bude chtít jít doprava (na spodní stopě musí být směry prohozené), hlava se přesune na horní pásku a pokračuje dále. Okraj pásky poznáme podle pomocného symbolu D, podobně jako v předchozím případě.
  • n-páskový TS
    • čte z a zapisuje do více pásek najednou
    • jediná změna je v přechodové funkci:
\delta: Q\times\Gamma^n\rightarrow Q\times(\Gamma\times\{L,R,N\})^n
  • nedeterministický TS (NTS)
    • umožňuje „výběr z více možností“
    • \delta: Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R,N\}} (Symbol 2^X značí potenční množinu k X.)
    • Idea důkazu: NTS si můžeme představit jako strom. Kořenem stromu je počáteční konfigurace NTS a každá větev z tohoto uzlu představuje jednu možnost, kudy může NTS jít. Pokud může například NTS přečíst jedničku a zapsat nulu a nebo přečíst nulu a zapsat jedničku, povedou z uzlu dvě větve, které reprezentují tyto možnosti. My předpokládáme, že NTS vybere vždy tu správnou cestu. Deterministicky bychom mohli tento stroj naprogramovat tak, že projdeme všechny větve NTS, ze kterých může NTS vybírat a když nalezneme alespoň jednu akceptující větev, respektive alespoň jeden akceptující uzel (list), stroj uspěl a dané slovo přijímá. Pokud bude ve všech větvích (listech) zamítající stav, stroj slovo zamítá. Pokud je alespoň jedna větev nekonečná a ostatní zamítající, stroj cyklí. Důležité je, jak budeme strom procházet. Pokud projdeme strom do hloubky, hrozí nám zacyklení. Například pokud bude hned první cesta nekonečná, ale všechny ostatní cesty by vedly do přijímajícího stavu, stroj by fungoval špatně, protože by se utopil hned v první cestě. Pokud ale projdeme do šířky, toto se nám nestane, protože budeme po částech procházet všechny možné větve najednou a postupně narazíme na všechny zamítající a přijímající stavy (ten nám ale stačí jeden). Ani tento postup nám ale nezaručí, že se vyhneme cyklům, pokud není nalezen žádný přijímající stav. Zbývá-li již poslední větev, která je nekonečná a ostatní cesty vedly do zamítajícího stavu, NTS se zacyklí stejně jako se zacyklí TS. Proto není NTS silnější nástroj než TS, oba přijímají stejnou množinu jazyků.

Subrutiny[editovat | editovat zdroj]

Tvorba složitějších TS není jednoduchá záležitost a subrutiny slouží k usnadnění této činnosti. Subrutina je množina stavů, která obsahuje počáteční a koncový stav. Z pravidla řeší nějaký dílčí problém v TS. V běžném programování má ekvivalent ve funkci, která také má nějaké vstupní a výstupní stavy a řeší z pravidla nějaký dílčí problém celého programu. V předchozím příkladě kontroly 0n1n by mohla být subrutina například vrácení čtecí hlavy na začátek nebo kontrola, zda už máme označena všechna čísla.

Zakódování Turingova stroje[editovat | editovat zdroj]

Každý Turingův stroj můžeme zakódovat do jednoho řetězce. Existuje nekonečně mnoho způsobů, jak TS zakódovat, záleží na vlastní definici. Můžeme například očíslovat všechny stavy, očíslovat všechny symboly z abecedy a očíslovat všechny směry, kterými se může čtecí hlava vydat. Následně můžeme přechodovou funkci (q1,a2)→(q3,t6,L1), kde dolní indexy označují očíslování, zakódovat takto: 01001000100000010. Jako oddělovač jsme použili jedničku a počet nul se vždy rovná očíslování daného objektu. Více různých přechodových funkcí můžeme oddělit dvěma jedničkami, takže pokud bychom přidali ještě funkci (q1,b3)→(q3,t6,R2), získali bychom řetězec 01001000100000010110100010001000000100. Takto můžeme zakódovat všechny přechodové funkce. Zbývá už jen označit startovací, přijímající a ukončovací stav, což můžeme udělat například tak, že startovací stav bude mít vždy index jedna, přijímající dva a zamítající tři. Do tohoto formátu pak můžeme zakódovat libovolný TS. Důsledkem tohoto faktu je, že množina všech Turingových strojů je spočetná.

Univerzální TS[editovat | editovat zdroj]

Univerzální Turingův stroj je takový TS U, který jako vstup přijímá kód jiného TS T (jeho Gödelovo číslo) a vstupní slovo stroje T. Dokáže rozkódovat přechodovou funkci stroje T a výpočet tohoto stroje simulovat. Univerzální TS dokáže vypočítat libovolnou částečně rekurzivní funkci (neboli je ekvivalentní k univerzální částečně rekurzivní funkci), rozhoduje jakýkoliv rekurzivní jazyk a přijímá libovolný rekurzivně spočetný jazyk.

Univerzální jazyk Lu[editovat | editovat zdroj]

Univerzální jazyk Lu je takový jazyk, který obsahuje dvojice TS a řetězec, přičemž tento TS daný řetězec přijímá. Platí: Lu = {[M, w]| TS M přijímá slovo w}. Tento jazyk je rekurzivně spočetný. Abychom zjistili, zda daná dvojice patří do tohoto jazyka, potřebovali bychom sestrojit TS Tu, který by rozhodoval problém, zda TS M přijímá slovo w. K tomu budeme potřebovat Univerzální TS. Tento TS Tu bude postupovat tak, že na vstupu vezme libovolný (zakódovaný) TS M a slovo w a nasimuluje činnost TS M při vstupu w. Neexistuje jiná možnost jak zjistit, jestli TS M přijímá slovo w než ta, že prostě do TS M to slovo w dáme a počkáme, jak nám TS M odpoví. Takže Universální TS Tu nasimuluje činnost TS M a pokud TS M slovo přijme, i Tu dvojici přijme. Pokud TS M slovo odmítne, i Tu dvojici odmítne. Problém nastane, když se TS M při vstupu w zacyklí. Neexistuje postup, jakým by měl TS Tu poznat, že se vnitřní TS M zacyklil, takže se zacyklí taktéž. Náš Tu je tudíž schopen rozpoznat a přijmout všechny dvojice, které do jazyka Lu patří, ale není schopen identifikovat všechny dvojice, které do jazyka Lu nepatří. A to v případě, kdy se TS M při vstupu w zacyklí. Přičemž takový TS jistě existuje, například TS, který se zacyklí pro jakýkoliv vstup.

Redukce problémů[editovat | editovat zdroj]

Některé problémy (Turingovy stroje) můžeme redukovat na jiné, což nám může pomoci při hledání důkazu, zda daný jazyk je rekurzivní jazyk, rekurzivně spočetný jazyk nebo zda není ani rekurzivně spočetný jazyk. Modelová situace: Víme, že jazyk A je rekurzivně spočetný (existuje důkaz). Chceme zjistit, zda je jazyk B rekurzivní, přičemž platí, že pokud by pro B existoval rozhodovací algoritmus, byli bychom s jeho pomocí schopni rozhodnout také problém A, tedy z A by se rázem stal rekurzivní jazyk. My ale víme, že A není rekurzivní jazyk, proto ani B nemůže být rekurzivní jazyk. Konkrétní příklad:

Jazyk HALT[editovat | editovat zdroj]

Jazyk HALT představuje množinu všech dvojic TS a slovo, pro které platí, že TS pro dané slovo zastaví (buď přijme, nebo odmítne, ale nezacyklí se). Tento jazyk není rekurzivní, protože pokud by tento jazyk byl rekurzivní, byli bychom schopni sestavit algoritmus, který by rozhodoval Univerzální jazyk Lu. TS, který by rozhodoval Lu by mohl vypadat následovně (předpokládáme vstup TS M a w, TSHALT je TS, který rozhoduje jazyk HALT):

  1. Pomocí TSHALT zjisti, zda M zastaví pro w.
  2. Pokud nezastaví, odmítni slovo.
  3. V opačném případě simuluj TS M pro vstup w a vrať to, co vrátí TS M.

Tento TS by byl schopný identifikovat, zda TS M přijímá slovo w. Nejdříve zjistí, zda daný TS M pro slovo w zastaví. Pokud se zacyklí, slovo rovnou odmítne. V opačném případě simuluje činnost M, který už musí vrátit nějaký výsledek, nemůže se zacyklit, to by bylo v rozporu s rozhodnutím TSHALT. Tento TS by tudíž rozhodoval Lu. My ale víme, že to není možné. A pokud není možné rozhodnout Lu, ale pomocí TSHALT by to šlo, znamená to, že HALT nemůže být rekurzivní jazyk.

Jazyk EMPTY[editovat | editovat zdroj]

Jazyk EMPTY je množina všech TS, které přijímají prázdný jazyk. Tento jazyk není rekurzivní, protože s jeho pomocí lze řešit Lu. Představme si TSEMPTY, který by rozhodoval, zda TS přijímá prázdný jazyk. Nyní sestrojíme TS, který je schopen rozhodnout Lu při vstupu TS M a slova w:

  1. Sestrojíme nový TS M1, který odmítne všechna slova krom w; pokud je na vstupu slovo w, simuluje činnost původního TS M.
  2. Pomocí TSEMPTY zjistíme, zda TS M1 přijímá prázdný jazyk.
  3. Pokud TS M1 přijímá prázdný jazyk, nepřijímá slovo w. Pokud TS M1 přijímá neprázdný jazyk, přijímá slovo w. Všechna slova krom w totiž musí TS M1 odmítnout, přijímá-li TS M1 neprázdný jazyk, jediné slovo, které může přijímat, je právě w. Přijímá-li TS M1 slovo w, přijímá ho i TS M, protože pro slovo w se chová TS M1 a TS M stejně.

Protože ale víme, že jazyk Lu není rozhodnutelný, nemůže ani jazyk EMPTY být rozhodnutelný/rekurzivní.

Problémy, které TS nedokáže vyřešit[editovat | editovat zdroj]

Přestože je TS mocný nástroj, nedokáže vyřešit všechny problémy. Každý Turingův stroj můžeme zakódovat do řetězce skládajícího se z jedniček a nul podobně jako se kódují programy na reálných počítačích. Tím máme dokázáno, že Turingových strojů je spočetně mnoho, protože uzávěr nad abecedou {0, 1}* můžeme uspořádat do nekonečné posloupnosti 0, 1, 01, 10, 100, 101, 110, 111, 1000, ... a každý Turingův stroj zakódovaný do jedniček a nul tudíž v této posloupnosti nalezneme. Teď dokážeme, že jazyků (= problémů), které mohou Turingovy stroje přijímat, je nespočetně mnoho. Použijeme k tomu diagonální metodu. Jazyk je vybraná podmnožina z uzávěru nad abecedou. Předpokládejme abecedu A={0,1} a jazyky (- značí, že daný jazyk slovo v prvním řádku neobsahuje, + značí, že obsahuje):

A* = 0, 1, 01, 10, 100, 101, ...
L1 = -  -  +   +   -    +    ...
L2 = +  -  -   -   -    +    ...
L3 = +  +  +   +   +    -    ...
...

Takže platí, že L1 = {0, 1, 01, 10, 100, 101, ...}, tedy L1 = {01, 10, 101, ...} atd. Nyní sestrojíme jazyk, který jistě nenajdeme v předchozím (nekonečném) výčtu jazyků. Nový jazyk Ln sestrojíme tak, že pokud jazyk Li obsahuje slovo z A* na i-té pozici, jazyk Ln ho obsahovat nebude a naopak. Tak jistě docílíme toho, že nový jazyk Ln se bude lišit alespoň v tomto jednom slově. Takže L1 neobsahuje slovo na prvním místě, tedy slovo 0, takže Ln ho obsahovat bude. Jazyk L2 neobsahuje slovo na druhém místě, 1, takže Ln ho bude obsahovat. Jazyk L3 obsahuje 01, takže Ln ho nebude obsahovat. A tak dále. Ln={0, 1, 01,...}. Jazyk Ln nenajdeme v předchozím výčtu jazyků, protože s každým uvedeným jazykem Li se bude lišit alespoň v tom, zda (ne)obsahuje slovo z A* na i-té pozici. Tím jsme dokázali, že množina všech jazyků (problémů) je nespočetná.

Pokud existuje nespočetně mnoho jazyků (problémů) a spočetně mnoho Turingových strojů, musí nutně existovat problémy, které Turingovy stroje nejsou schopné řešit. Jazyků (problémů) je zkrátka více než Turingových strojů.

Externí odkazy[editovat | editovat zdroj]