SML kordamisküsimustele vastused.
· Töö lõpeb, kui masin siirdub passiivsesse seisundisse q0 või kui täitmisjärg jõuab tühja
lahtrisse.
Turingi masina omadused:
· Vastab hästi meie intuitiivsele arusaamale algoritmist.
· Lihtsuse ja elementaarsuse tõttu võib tabel olla üsna mahukas, kuid praktilise
kasutatavusega seotud küsimused on antud juhul teisejärgulised.
· Samas on hõlpus tõestada Turingi masinate kohta üldisi teoreeme, mh algoritmide
mitteleidumist.
· Taktide arv sobib hästi algoritmi keerukuse mõõduks.
Arvude ja arvujärjendite esitamine lindil:
Turingi masinate kompositsioon ja hargnemine.
Definitsioon 3. Turingi masinat M nim masinate M1 ja M2 konpositsiooniks, kui iga
algkonfiguratsiooni X korral kehtib võrdus M(X)=M2(M1(X))
6
Teoreem 1. Kui M1 ja M2 on samas tähestikus töötavad Turingi masinad, siis saab nende
annaabi.ee 
