SML kordamisküsimustele vastused.
Teoreem 2. Kui M0, M1 ja M2 on samas tähestikus töötavad Turingi masinad, kusjuures masinal
M0 on kaks passiivset seisundit 01 ja 02 , siis saab nende masinate tabelite järgi alati koostada
sellise masina tabeli, mis on masinate M1 ja M2 hargnemine masina M0 järgi.
Tõestus. Kirjutame masinate M0, M1 ja M2 tabelid järjest. Asendame kõik seisundid 01 masina
M1 esimese seisundiga ning seisundid 02 masina M2 esimese seisundiga.
Turingi masinate numeratsioon.
Turingi mõttes mittearvutatavad funktsioonid. Eneselerakendatavuse ja
peatumise probleemi mittelahenduvus. Rice'i teoreem (tõestuseta).
Järeldused programmeerimise jaoks.
Def 5. Ütleme, et Turingi masin M lahendab omadust R, kui tema poolt arvutatav ühe muutuja
funktsioon on
1, ,
() =
0, .
Teoreem 3.Ei leidu Turingi masinat, mis lahendaks enese,erakendatavuse omadust.
Tõestus lk 124
Teoreem 4
annaabi.ee 
