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)
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
No hay comentarios:
Publicar un comentario