Turingin kaavio

Turingin kaavio on graafinen tapa kuvata Turingin koneen toimintaa . Se koostuu Turingin konetietoja ilmaisevista symboleista, joilla on yhteinen työaakkoset, pistesymbolista, joka osoittaa paikan, josta sinun on aloitettava työ, sekä nuolista, joihin on kirjoitettu kirjaimia. Turingin kaaviossa symboli "piste" esiintyy vain kerran, mistä tahansa symbolista ei ole enempää kuin yksi nuoli jokaisessa aakkoston kirjaimessa. Jokainen aakkosten yli oleva Turing-taulukko voidaan yhdistää tehokkaasti symboleista ja pisteestä muodostettuun kaavioon , jolloin tämän kaavion määrittelemä Turingin kone simuloi Turingin konetta taulukolla [1] . $T$ ${\näyttötyyli A_{t))$ $D$ ${\displaystyle r,l,a_{0},...,a_{t))$ $T$

Muistiinpanot

↑ Ebbinhouse, 1972 , s. 55.

Katso myös

Turingin kone

Kirjallisuus

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingin koneet ja rekursiiviset funktiot. - M .: Mir, 1972. - 262 s.