La notación de la máquina de Turing, necesita traducción

Question

Estoy aprendiendo sobre las máquinas de Turing y he visto ejemplos como éste:

Por ejemplo, si estamos en el estado "A" y leemos "0", lo sustituimos por "P" y nos movemos hacia la derecha.

Sin embargo, me encontré con esto en los antiguos exámenes:

¿Cómo debo leer este TM? por ejemplo en el medio tenemos $\#R_\#L$ .

Me piden que describa la lengua sobre el alfabeto $\{a,b\}$ que representa la TM. Pero no sé cómo leer la máquina en absoluto.

Gracias.

Answer 1

La primera máquina de Turing es una máquina de Turing representada en forma de estados. La segunda es una Máquina de Turing "compleja" representada en forma de máquinas de Turing básicas. Compleja en el sentido de que está formada por Máquinas de Turing más pequeñas y básicas combinadas de alguna forma.

R _a es una máquina de Turing cuya cabeza se desplaza hacia la derecha en la cinta de entrada hasta leer a . "#" es una máquina de Turing que sustituye el símbolo de entrada apuntado por la cabeza en la cinta de entrada por "#" .

Por fin una máquina de Turing R _a L es equivalente a:
R _a L
Esto significa que la Máquina de Turing equivalente en su conjunto se moverá hacia la derecha hasta encontrar un a en la cinta de entrada; la flecha sin ningún símbolo representa que la Máquina de Turing se moverá hacia la izquierda (ya que la Máquina de Turing 'L' está presente en el extremo de la flecha) al encontrar cualquier símbolo en el alfabeto.

Le recomiendo que lea Elementos de la teoría de la computación escrito por Harry R. Lewis si todavía no lo entiendes.