Turingův diagram

Turingův diagram je grafický způsob, jak popsat činnost Turingova stroje . Skládá se ze symbolů označujících data Turingova stroje, které mají společnou pracovní abecedu, symbol tečky označující místo, kde je třeba začít pracovat, šipky s napsanými písmeny. V Turingově diagramu se symbol „tečka“ vyskytuje pouze jednou, od žádného symbolu není více než jedna šipka s každým písmenem abecedy. Každá Turingova tabulka nad abecedou může být efektivně spojena s diagramem tvořeným symboly a tečkou, takže Turingův stroj definovaný tímto diagramem simuluje Turingův stroj s tabulkou [1] . $T$ ${\displaystyle A_{t))$ $D$ ${\displaystyle r,l,a_{0},...,a_{t))$ $T$

Poznámky

↑ Ebbinhouse, 1972 , s. 55.

Viz také

Turingův stroj

Literatura

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingovy stroje a rekurzivní funkce. — M .: Mir, 1972. — 262 s.