¿Cuál es el significado de Oblivious Turing Machine?

Question

Realmente no entiendo la diferencia entre OTM y Standard TM. ¿Podría alguien explicármelo? Gracias

Answer 1

La función de transición de una máquina de Turing regular es una función $$\delta : Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{\rightarrow, \leftarrow, \text{stay}\}^k$$ lo que significa que mira en su estado actual $q \in Q$ , mira un símbolo $\in \Gamma$ en cada uno de $k$ cintas, y en función de ello decide cómo cambiar su estado, qué símbolo escribir en cada una de las cintas y dónde ir en cada una de las cintas .

En cambio, la función de transición de una Máquina de Turing Oblivious es una función $$\delta : Q \times \Gamma^k \rightarrow Q \times \Gamma^k$$ así que no tiene elección sobre a dónde ir pero aún tiene la opción de cambiar su estado y escribir un nuevo símbolo en cada una de las cintas.

Esto significa lo mismo que una Máquina de Turing Oblivious definida en Complejidad computacional: A Modern Approach, p. 49

Definir una TM $M$ t de la entrada, sino sólo de la longitud de la entrada. Es decir, $M$ i si para cada entrada $x \in \{0, 1\}^*$ y $i \in N$ , cada una de las cabezas de M en el $i$ ª etapa de ejecución de la entrada $x$ i función de $|x|$ y $i$ .

P.D. Otra respuesta que afirma "si acepta la cadena de entrada $aabab$ también aceptará $babaa$ y, de hecho, cualquier otra cadena de longitud $5$ " es erróneo.