Diagrama de turing

Un diagrama de Turing es una forma gráfica de describir el funcionamiento de una máquina de Turing . Consiste en símbolos que denotan datos de la máquina de Turing que tienen un alfabeto de trabajo común, un símbolo de punto que indica el lugar donde debe comenzar a trabajar, flechas con letras escritas en ellas. En el diagrama de Turing, el símbolo "punto" aparece solo una vez, de cualquier símbolo no hay más de una flecha con cada letra del alfabeto. Cada tabla de Turing sobre un alfabeto se puede asociar efectivamente con un diagrama formado por símbolos y un punto, de modo que la máquina de Turing definida por este diagrama simula una máquina de Turing con una tabla [1] . $T$ ${\ Displaystyle A_ {t}}$ $D$ ${\displaystyle r,l,a_{0},...,a_{t))$ $T$

Notas

↑ Ebbinhouse, 1972 , pág. 55.

Véase también

máquina de Turing

Literatura

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Máquinas de Turing y funciones recursivas. — M .: Mir, 1972. — 262 p.