TS sa sklada z riadiacej jednotky a pasky, po ktorej sa vdaka citacu/zapisovacej hlave da pohybovat oboma smermi. Riadaca jednotka moze zapisovat/citat len jedno policko. V zavislosti na svojom stave a na symbole citanom z pasky meni svoj stav aj TS - teda prejde do dalsieho stavu a prepise symbol, alebo sa posunie doprava/dolava.
TS je ale vlastne matematicky model, ktory ma charakter automatu, musi byt co najjednoduchsi a musi byt dostatocne obecny s ohladom na vypocty, ktore ma vykonavat. Takze, TS ja automat M = (Q, A, delta, s, F),
kde Q je konecna mnozina stavov
A je abeceda
s je pociatocny symbol
F je mnozina koncovych stavov
a delta je prechodove zobrazenie
Kazdy TS ma svoju konfiguraciu (q, alfa, beta)
alfa - obsah pasky zlava (k hlave)
beta - obsah pasy napravo
q - aktualny stav
TS prijme dany vstup, ak sa po konecnom stave krokov dostane do prijimacieho stavu. Pokial TS dokaze rozhodnut nejaky jazyk, tak jazyk je rekurzivny. Koniec koncov, je to automat, takze pokial dokaze prejst do jedneho z F stavov, tak jazyk je OK.
Problem, ktory nazyvame halting problem sa da ukazat na TS - nejde ale vyriesit. Patri do skupiny nerozhodnutelnych problemov.
http://www.earchiv.cz/a94/a433c120.php3
TS mozu mat v obecnejsom ponati viac citacich/zapisovacich hlav a napriklad len jednu pasku, po ktorej sa pohybuje viac hlav. Dalsou moznostou je obojstranna paska - takyto stroj pracuje s dvojrozmernou mriezkou. TS s nahodnym pristupom je model dnesneho PC, ktory nemusi sekvencne prechadzat celu pasku. Nedeterministicky TS - stroj, vlastne nedeterministicky automat, takze jeho rozhodnutie nie je jasne. Univerzalny TS - simuluje cinnost lubovolneho ineho TS a ma 3 pasky, jedna simuluje pasku stroja M, druha zakodovava strukturu stroja M a tretia aktivny stav stroja.
