SML kordamisküsimustele vastused.
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
masinate tabelite järgi alati koostada kompositsioonmasina tabeli.
Tõestus. Olgu masinal M1 aktiivsed seisundid q1,q2,...,qk ning masinal M2 seisundid r1,r2,...rl.
Kirjutame masinate M1 ja M2 tabelid teinteise järele, andes esimese masina peatumiskohtades
annaabi.ee 
