Máquinas de Turing (página 3)

Partes: 1, 2, 3

EJERCICIO
[SUBMÁQUINA]
Dar una máquina de Turing con submáquinas y otra máquina de Turing sin submáquinas que emule a la primera.
Se puede aplicar el mismo procedimiento a cualquier máquina de Turing con submáquinas? Debería estar claro cómo generalizar la construcción a cualquier otra MdT con submáquinas.

EJERCICIO
[VARIAS CINTAS]
Describir el funcionamiento de una MdT con varias cintas.
Dar un ejemplo de una MdT que utilice dos cintas y otra MdT normal que emule a la primera. Debería estar claro cómo generalizar la construcción a cualquier otra MdT con varias cintas.

EJERCICIOS
[CINTA LIMITADA] Dar un ejemplo de una MdT con cinta limitada por la izquierda y otra MdT normal que la emule. Debería estar claro cómo generalizar la construcción a cualquier otra MdT con cinta limitada por la izquierda.
[SÍMBOLOS] Dar un ejemplo de una MdT con 3 símbolos y otra con 2 símbolos que la emule. Debería estar claro cómo generalizar la construcción a cualquier otra MdT con más de 3 símbolos.

Codificación de MdT
Las máquinas de Turing se pueden codificar codificando cada transición y concatenando los resultados con separadores.
De esta forma se define un lenguaje de programación en el que hay tres variables: El estado de la máquina y las dos partes en que se divide la cinta.

Ejemplo de codificación de MdT y de sus estados instantáneos
EstIni.EstFin
;Trans,…
:Cinta1EstadoCinta2
0.24
;0a1a+,0b4a-,1a2a+,1b0a-,2a3a+,2b1a-,3a4a+,3b2a-,4a0a+,4b3a-
:aa2bab
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 3
(Gp:) aa+
(Gp:) aa+
(Gp:) aa+
(Gp:) aa+
(Gp:) aa+
(Gp:) ba-
(Gp:) ba-
(Gp:) ba-
(Gp:) ba-
(Gp:) ba-

Máquina de Turing universal
Hay máquinas de Turing capaces de emular el funcionamiento de otras cualesquiera a partir de su codificación.
(Gp:) 1
(Gp:) ?BuscaTransición
(Gp:) ?AplicaTransición
(Gp:) 2
(Gp:) :Comprueba
(Gp:) 0

Cuestión
Comparar lo anterior con la emulación de programas.

EJERCICIO
[BUSCA TRANSICIÓN] Escribir la submáquina BuscaTransición de la MTU
[APLICA TRANSICIÓN] Escribir la submáquina AplicaTransición de la MTU
[COMPRUEBA] Escribir la submáquina Comprueba de la MTU

EJERCICIOS
[EMULA DETERMINISTA] Dar una MdT indeterminista y otra MdT determinista que emula su funcionamiento.
[MTU DETERMINISTA] Dar una MdT determinista que emule el funcionamiento de una MdT arbitraria, determinista o no

Problema de la parada
Dada una MdT M y una palabra w, ¿llega M a un estado de parada a partir de w?
Solución del problema: Sería
MdT que, al ejecutarse sobre una codificación de M + w, se para si y sólo si M no lo hace a partir de w.
No tiene solución.
Demostración: Análoga al caso de programas.

EJERCICIO
[PARA PARA 1] Suponiendo que el problema de la parada tuviera solución, escribir una MdT, PP, que utilice a la anterior como submáquina que, al ejecutarse sobre la codificación de otra MdT M + una palabra w, se pare en el estado 0 si M lo hace sobre w, y en ese caso deje sobre la cinta el valor calculado por M, y se pare en el estado 1 si M no lo hace sobre w.