Turingův stroj

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

Turingův stroj je sedmice $\ M=(Q,\Gamma ,b,\Sigma ,s,\delta ,F)$ kde :

• $Q$ je konečná množina vnitřních stavů
• $\Gamma$ je konečná abeceda symbolů na pásce
• $b\in \Gamma$ je symbol reprezentující prázdný symbol ( $b$ není součástí vstupní abecedy přijímaného řetězce)
• $\Sigma \subseteq \Gamma \setminus b$ je konečná množina vstupních symbolů
• $s\in Q$ je počáteční 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
• $F\subseteq Q$ je množina koncových stavů

Konfigurace

Konfigurace Turingova stroje je prvek $\left\langle q,s,n\right\rangle$ množ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 jako 1$q$234.

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

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

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

Napíšeme jednoduchý TS, který bude mít za úkol zjistit, zda slovo napsané na pásku má tvar 0ⁿ1ⁿ, 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}{\rightarrow }}$ $q_{1}011$ ${\overset {2}{\rightarrow }}$ $0q_{1}11$ ${\overset {3}{\rightarrow }}$ $01q_{2}1$,${\overset {4}{\rightarrow }}$ $011q_{2}$ ${\overset {5}{\rightarrow }}$ $01q_{3}1$ ${\overset {6}{\rightarrow }}$ $0q_{4}1$ ${\overset {8}{\rightarrow }}$ $q_{5}01$ ${\overset {10}{\rightarrow }}$ $q_{6}b01$ ${\overset {12}{\rightarrow }}$ $q_{0}01$ ${\overset {1}{\rightarrow }}$ $q_{1}1$ ${\overset {3}{\rightarrow }}$ $1q_{2}$ ${\overset {5}{\rightarrow }}$ $q_{3}1$ ${\overset {6}{\rightarrow }}$ $q_{4}b$ ${\overset {7}{\rightarrow }}$ $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}{\rightarrow }}$ $q_{1}01$ ${\overset {2}{\rightarrow }}$ $0q_{1}1$ ${\overset {3}{\rightarrow }}$ $01q_{2}$,${\overset {5}{\rightarrow }}$ $0q_{3}1$ ${\overset {6}{\rightarrow }}$ $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^{n}1^{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}{\rightarrow }}$ $q_{1}101$ ${\overset {3}{\rightarrow }}$ $1q_{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

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

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. Zpravidla ř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 0ⁿ1ⁿ 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

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 (q₁,a₂)→(q₃,t₆,L₁), 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 (q₁,b₃)→(q₃,t₆,R₂), 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

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 L_u

Univerzální jazyk L_u je takový jazyk, který obsahuje dvojice TS a řetězec, přičemž tento TS daný řetězec přijímá. Platí: L_u = {[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 T_u, který by rozhodoval problém, zda TS M přijímá slovo w. K tomu budeme potřebovat Univerzální TS. Tento TS T_u 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 T_u nasimuluje činnost TS M a pokud TS M slovo přijme, i T_u dvojici přijme. Pokud TS M slovo odmítne, i T_u dvojici odmítne. Problém nastane, když se TS M při vstupu w zacyklí. Neexistuje postup, jakým by měl TS T_u poznat, že se vnitřní TS M zacyklil, takže se zacyklí taktéž. Náš T_u je tudíž schopen rozpoznat a přijmout všechny dvojice, které do jazyka L_u patří, ale není schopen identifikovat všechny dvojice, které do jazyka L_u 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ů

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

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 L_u. TS, který by rozhodoval L_u by mohl vypadat následovně (předpokládáme vstup TS M a w, TS_HALT je TS, který rozhoduje jazyk HALT):

1. Pomocí TS_HALT 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 TS_HALT. Tento TS by tudíž rozhodoval L_u. My ale víme, že to není možné. A pokud není možné rozhodnout L_u, ale pomocí TS_HALT by to šlo, znamená to, že HALT nemůže být rekurzivní jazyk.

Jazyk EMPTY

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 L_u. Představme si TS_EMPTY, který by rozhodoval, zda TS přijímá prázdný jazyk. Nyní sestrojíme TS, který je schopen rozhodnout L_u při vstupu TS M a slova w:

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

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

Problémy, které TS nedokáže vyřešit

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ů) 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

• Obrázky, zvuky či videa k tématu Turingův stroj na Wikimedia Commons
• Více informací a popis Turingova stroje

Autoritní data	BNE: XX550362 BNF: cb11978871z (data) GND: 4203525-9 LCCN: sh85138778 NDL: 00573533 NLI: 987007555894805171 SUDOC: 027831655