*Máquinas Turing

Materia: Laboratorio
Hora: Jueves V1

Hola a todos, en esta entrada aunque un poco tarde les hablare sobre las Máquinas Turing.

Las Máquinas Turing son modelos computacionales que se utilizan para la lectura y escritura de una entrada llamada cinta.

Está formado por :

• Un alfabeto de entrada
• Un alfabeto de salida
• Un símbolo llamado blanco
• Un conjunto de estados finitos
• Un conjunto de transiciones entre dichos estados

Cuando una máquina de turing tiene una sola cinta puede ser  definida como tupla    donde:

•  es un conjunto finito de estados.
•  es un conjunto finito de símbolos diferentes del espacio en blanco, y éste es denominado alfabeto de máquina o de entrada.
•  es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta ().
•  es el estado inicial.
•  es el símbolo denominado blanco, y es el único que se puede repetir infinitas veces.
•  es el conjunto de estados finales de aceptación.
• es la denominada función de transición.

Funcionamiento de la Máquina de Turing

La Máquina de Turing tiene una cabezal lector/escritor y tiene una cinta infinita en la que el cabezal lee el contenido, borra el contenido leido y escribe un nuevo valor. Al momento de realizar las operaciones se tiene que checar que sólo se puede avanzar el cabezal lector/escritor hacia la derecha y hacia la izquierda. 

 Esto se determina con una tabla de la siguiente forma :                      

•  (estado, valor) (nuevo estado, nuevo valor, dirección)

Donde la tabla toma como parámetro el estado actual de la máquina y e carácter leido de la cinta, y con esto da la dirección al cabezal para moverse, el nuevo estado de la máquina y el valor a ser escrito de la cinta.

En este caso el elemento que actúa como la memoria es la cinta la cual se divide en espacios llamados celdas, donde se escriben o leen diferentes símbolos. Desde el inicio todas las celdas contienen el famoso símbolo especial llamado "blanco".







                                       





* Video sobre Máquinas Turing


Aquí les dejo un  vídeo en donde te explican todo sobre las Máquinas Turing y también explican un ejemplo, espero que les sirva :). Saludos