Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página30/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   ...   23   24   25   26   27   28   29   30   31



B B s2 B B1



B s1 s2 B D



B B s1 s2 B



B s1 s1 s2 # B D

B # s1 s1 s2 # s1 B D



B B # s1 s1 s2 # s1 B F


B B B s1 s1 s2 B s1 s1 B E

La técnica de pensar en la cinta de una máquina de Turing como descomponible en varias pistas paralelas tiene numerosos usos. Por ejemplo, se podría usar para simular máquinas de Turing con múltiples cintas y cabezas de lectura independientes para cada una de ellas. Si tenemos una máquina con k cintas, se puede considerar una máquina de turing con 2k pistas. En ellas se contienen los símbolos de las k cintas, y para cada una de las k cintas, habrá una pista que contendrá la posición de la cabeza de lectura-escritura en dicha cinta (por ejemplo esta pista puede tener todos los símbolos blancos, menos en la casilla activa, en la que contendrá un uno) . De esta forma, se puede simular una máquina con k cintas mediante una máquina de Turing con una sola cinta.



Ejercicios

1. Dar una definición formal de máquinas de Turing con tres cintas: una de lectura para la entrada, otra de escritura para la salida, y otra cinta de trabajo. Dar una definición de calculabilidad que sea apropiada y demostrar la equivalencia con la calculabilidad de las máquinas de Turing ordinarias.

2. Hacer lo mismo para una máquina de Turing con una cinta de entrada, una de salida y k cintas de trabajo.

3. Consideremos que el lenguaje POST-TURING sea aumentado con las instrucciones UP y DOWN de forma que pueda trabajar con una cinta bidimensional infinita en las cuatro direcciones. Dar una definición apropiada de lo que significa que una función sea calculada en este lenguaje y demostrar que estas funciones son parcialmente calculables.



1   ...   23   24   25   26   27   28   29   30   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal