Diagrama Turing

O diagramă Turing este o modalitate grafică de a descrie funcționarea unei mașini Turing . Este format din simboluri care denotă datele mașinii Turing care au un alfabet comun de lucru, un simbol punct care indică locul de unde trebuie să începeți lucrul, săgeți cu litere scrise pe ele. În diagrama Turing, simbolul „punct” apare o singură dată, de la orice simbol nu există mai mult de o săgeată cu fiecare literă a alfabetului. Fiecare tabel Turing peste un alfabet poate fi asociat eficient cu o diagramă formată din simboluri și un punct, astfel încât mașina Turing definită de această diagramă simulează o mașină Turing cu un tabel [1] . $T$ $A_{t)$ $D$ $r,l,a_{0},...,a_{t)$ $T$

Note

↑ Ebbinhouse, 1972 , p. 55.

Vezi și

mașină Turing

Literatură

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turing machines and recursive functions. — M .: Mir, 1972. — 262 p.