MAQUINAS TURING

Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida de la misma.

HISTORIA

Este concepto fue introducido por Alan Turing, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decibles, osea si hay un método definido que se pueda aplicarse a cualquier sentencia matemática y nos diga si es cierta o no. Turing ideo un modelo formal de computador, la maquina de Turing y demostró que existian problemas que una maquina no podía resolver.

FUNCIONAMIENTO

Este modelo esta conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamada blanco, normalmente b,  Δ), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

Su funcionamiento se basa en la función de transición que recibe un estado inicial y una cadena de caracteres pertenecientes al alfabeto de entrada, luego va leyendo una celda de la cinta, borrando el símbolo, y escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha, repitiendo lo que indique la función transición.

Una maquina turing con una sola cinta puede ser definida como 7-tupla   donde:

•  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 conjunto finito de símbolos de cinta, denominado alfabeto de cinta. ()

•  es el estado inicial.

• es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.

•  es el conjunto de estados finales de aceptación.

• es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.

Aquí les dejo un vídeo acerca de la historia de las maquinas turing y Alan turing

Espero que les sirve:)