viernes, 24 de febrero de 2012

Máquinas de Turing



La máquina de Turing fue ideada por Alan Turing como una herramienta para resolver la decibilidad de los problemas matemáticos. Fue el primer modelo formal de computador, y con él se demostró que hay problemas que no son resolubles mediante un ordenador.

Ésta, a priori, sencilla máquina, es capaz de realizar complejos cálculos tales como los realizables por un ordenador cualquiera.

En su implementación, la máquina de turing se sirve de una cinta infinita donde va leyendo y escribiendo caracteres usando un cabezal, transicionando a su vez por diversos estados del autómata asociado hasta llegar o no a un estado final.

Usos de la Máquina de Turing:

- Complejidad Computacional


El modelo se compone de dos alfabetos, uno de entrada y otro de salida, además de un carácter especial llamado blanco (b), un conjunto de estados finitos y otro de transiciones entre estados.

Se representa como (Q, Σ, s, b, F, Γ, ∂):

- Q es un conjunto finito de estados.
- Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
- Γ es un estado finito de símbolos de cinta, denominado alfabeto de cinta (Σ ⊆ Γ).
- s pertenece Q es el estado inicial.
- b pertenece Γ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
- F ⊆ Q es el conjunto de estados finales de aceptación.
- ∂ : Q x Γ → Q x Γ x {L, R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.


Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S como símbolo de "no movimiento" en un paso de cómputo.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

No hay comentarios:

Publicar un comentario en la entrada