Modelar la Máquina de Turing

La máquina de Turing es un dispositivo informático el cual consiste en un cabezal de lectura y escritura , lo que mejor conocemos hoy en día con el nombre de escáner y de una cinta de papel que atraviesa la máquina. Esta cinta se encontraba divida en cuadrados, y cada uno de ellos tenía al mismo tiempo un símbolo. Esta cinta era la encargada del almacenamiento de la máquina, y era una especie de vehículo de entrada y salida, además de funcionar como memoria de trabajo para almacenar los resultados de los pasos intermedios del cálculo

Características:

• La entrada que tiene la cinta antes de que comience el cálculo debe consistir en un número finito de símbolos.
• La cinta de la máquina tiene una de longitud ilimitada.
• El cabezal de lectura y escritura puede ser programable.
• La máquina de Turing es capaz de hacer seis tipos de operaciones fundamentales: leer, escribir, mover hacia la izquierda, mover hacia la derecha, cambiar de estado y detenerse.
• Tiene la capacidad de computar cualquier cosa que cualquier computadora moderna pueda calcular.
• Está formada por un alfabeto de entrada y uno de salida y por un símbolo especial llamado blanco.

¿Cómo funciona?

La máquina de Turing funciona por medio de un control finito, una cabeza lectora y una cinta por en la cual puede haber diferentes caracteres, y en la cual se encuentra la palabra de entrada. Hacia el lado derecho la cinta tiene una longitud que es el lugar donde se llenan los espacios con el carácter blanco el cual es representado por la letra “t”. Hacia su lado izquierdo pasa lo contrario pues la cinta no es infinita razón por la cual hay un cuadro de la cinta que es el extremo izquierdo. Además, tiene una cabeza que se mueve hacia la izquierda y derecha, por lo que tiene la capacidad de pasar en ciclos repetidos sobre un mismo segmento de la cinta.

La máquina está conformada por un alfabeto de entrada y uno de salida, por un símbolo especial conocido con el nombre de blanco el cual normalmente se representa por medio de una b, Δ o 0, por un grupo de estados finitos y por un conjunto de transiciones entre estos estados.

Su funcionamiento se fundamenta en la transición, la cual se encarga de recibir un estado inicial y una cadena de caracteres los cuales pertenecen al alfabeto de entrada. A partir de ese momento la máquina empieza a leer una celda de la cinta, borrando el símbolo, y escribiendo el nuevo símbolo que pertenece al alfabeto de salida para luego avanza a la izquierda o a la derecha, un tiempo a la vez y repitiendo el proceso según se indique en la función de transición. Al final del proceso se detiene en un estado de aceptación, representando así la salida.

Ejemplos:

• Una cadena de X seguida de una cadena de Y. Ambas de la misma longitud.
• {X^n Y^n, n>0}
• Estado inicial de la cinta: 000111#
• Transiciones:
  • 0 0 X r 1
  • 1 0 0 r 1
  • 1 Y Y r 1
  • 2 X X r 0
  • 3 Y Y r 3
  • 0 Y Y r 3
  • 1 1 Y l 2
  • 2 0 0 l 2
  • 2 Y Y l 2
  • 3 # # r 4
  • 4 * * r halt

Ejercicio de modelado 1: Propuesta 16/11/2024 9:00