Monografias.com > Uncategorized
Descargar Imprimir Comentar Ver trabajos relacionados

Máquinas de Turing (página 3)




Enviado por Pablo Turmero



Partes: 1, 2, 3

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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-

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Partes: 1, 2, 3
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter