viernes, 5 de noviembre de 2010

*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   M=(Q, \Sigma, \Gamma, s, b, F, \delta)\, donde:

  • Q \, es un conjunto finito de estados.
  • \Sigma \, es un conjunto finito de símbolos diferentes del espacio en blanco, y éste es denominado alfabeto de máquina o de entrada.
  • \Gamma \, es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (\Sigma \subseteq\Gamma \,).
  • s \in Q es el estado inicial.
  • b \in \Gamma es el símbolo denominado blanco, y es el único que se puede repetir infinitas veces.
  • F \subseteq Q es el conjunto de estados finales de aceptación.
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}\,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


1 comentario: