Turingův stroj: Porovnání verzí

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á množina|spočetně mnoho]], protože [[Formální jazyk|uzávěr nad abecedou]] <code>{0, 1}*</code> 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 [[Cantorova diagonální metoda|diagonální metodu]]. Jazyk je vybraná [[podmnožina]] z uzávěru nad abecedou. Předpokládejme abevykuř mi ho kráskoceduabecedu <code>A={0,1}</code> a jazyky (<code>-</code> značí, že daný jazyk slovo v prvním řádku neobsahuje, <code>+</code> značí, že obsahuje):