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.
| Página siguiente |