¿Cada lenguaje recursivo es reconocido por una máquina mortal de Turing?

Decimos que una máquina de Turing es mortal si detiene para cada configuración inicial (en particular, el contenido de la cinta y el estado inicial pueden ser arbitrarios). ¿Cada lenguaje recursivo es reconocido por una máquina de Turing mortal? (es decir, si hay una TM que acepta , también hay una TM mortal que acepta ) $M$ $M$ $L$ $L$

computability Marcin Kotowski
fuente

¿Puede dar referencia (s) a las máquinas Mortal Turing? Gracias :)

Tayfun paga

¿Cómo es que el estado inicial puede ser arbitrario? ¿No es una máquina mortal de Turing solo una TM que se detiene en cada entrada?

Philip White

@ Marcin: ¿le interesan las máquinas que se detienen en todas las configuraciones, incluidas las infinitas, o solo aquellas que se detienen en todas las configuraciones finitas ?

Joshua Grochow

Creo que se refiere a configuraciones de inicio finitas. ¿Derecho?

Philip White

@Philip: solo imagine la máquina en un estado y configuración arbitrarios, y luego ejecute el cálculo hacia adelante desde ese punto siguiendo las reglas habituales.

Joshua Grochow

Respuestas:

Aquí hay dos resultados citados en Charles E. Hughes "Indecidibilidad de la convergencia finita para los operadores de concatenación, inserción y shuffle acotado" :

Teorema 3 : La clase de máquinas Turing mortales es exactamente la clase de las máquinas Turing de tiempo de funcionamiento constante.

st para todas las configuraciones iniciales , detiene en no más de pasos $ConstT = \{ M \mid \exists s$ $C$ $M$ $s$ $\}$

Así que creo que podemos derivar lo siguiente: dada una máquina de Turing mortal , que sea el tiempo constante correspondiente TM y su tiempo de ejecución. El lenguaje reconocido por sobre el alfabeto es exactamente: $M$ $M', s$ $M$ $\Sigma = \{0,1\}$

{X y ∣ El | X El | \leq s \land {METRO}^{'} acepta X en no más de s pasos, y \in {0 0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Entonces, la clase de idiomas reconocidos por las máquinas mortales de Turing es un subconjunto apropiado de la clase de idiomas regulares. Por ejemplo, puede usar para engañar cada vez constante TM. $L = \{(0|1)^*1^*\}$

Las cosas se ponen interesantes cuando intentamos decidir si una máquina de Turing es mortal porque tenemos que enfrentarnos con una cinta y estado iniciales arbitrarios (finitos).

Teorema 4 : el conjunto de máquinas mortales de Turing es recursivamente enumerable.

Marzio De Biasi
fuente

Creo que hay Tenemos que hacer para cada L y M que lo acepte de tal manera que todos sus movimientos se graben en una cinta y después de cada "paso principal" verifica si todos sus pasos hasta ese punto fueron realmente válidos. A continuación, presento un bosquejo sobre cómo se debe hacer una máquina de este tipo (que puede contener algunos errores menores, pero la idea principal debería estar bien).

Denote una máquina que acepta L por T. Ahora describimos M. Primero, copiamos x a una cinta de memoria separada. Luego, cada vez que T haga un movimiento, lo escribimos en esta cinta de memoria, después de x. Después de esto, copiamos todo el contenido de las cintas de T en algunas cintas de trabajo adicionales y verificamos si desde la configuración inicial T realmente alcanzará su estado actual después de los pasos grabados en la cinta de memoria. Si no, nos detenemos. Si es así, continuamos.

domotorp
fuente

mientras escribo mi respuesta, leo la suya ... que dice lo contrario :-) ... ¿tal vez estoy interpretando erróneamente qué es una cadena aceptada por una máquina mortal de Turing?

Marzio De Biasi

@MarzioDeBiasi: La noción de mortal considerada en ese documento requiere que una máquina se detenga en un número finito de pasos, incluso si se inicia con una cantidad infinita de datos arbitrarios en su cinta. Pero creo que la construcción de domotorp en la mayoría de los trabajos para configuraciones finitas. Por ejemplo, en una configuración con una entrada de longitud infinita, la M de domotorp queda atrapada en una secuencia infinita de copiar la entrada de longitud infinita en la cinta de memoria separada ...

Joshua Grochow

Sí, la diferencia es que supuse que cada contenido de la cinta es finito y sabemos dónde están los límites. De lo contrario, los TM mortales son solo constantes, mientras escribes.

domotorp