Reingenieria

Definición Formal
Una máquina de Turing es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichosestados. 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 luegodesplazar 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.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

Dónde:
• es un conjunto finito de estados.
• es un conjunto finito de símbolosdistinto 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 detransición, donde es un movimiento a la izquierda y 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 como símbolo de "no movimiento" en un paso de cómputo.
Máquinas De Turing
Son máquinas teóricas capaces de aceptar lenguajes generados porgramáticas, estructuradas por frases. Una máquina de Turing tiene una cabeza de lectura/escritura que avanza bidireccionalmente por una cinta infinita por la derecha.
 Entrada: contenido inicial de la cinta.
 Salida: contenido final de la cinta.
Símbolos de cinta:
 Símbolos de entrada: Σ
 Símbolos de cinta: Γ ⊇ Σ
Transiciones: δ(p,x) = (q,y) donde:
 p,q: estados
 x ∈ Σ : símbolo de entrada y ∈ Γ ∪ {L,R} : símbolo de cinta o desplazamiento
En una transición, la máquina de Turing lee un símbolo de la cinta, cambia de estado y escribe un símbolo o efectúa un desplazamiento a izquierda o derecha.
Ejemplo de diagrama de transiciones

¬





Proceso de reconocimiento de una cadena:
 Se parte del estado inicial, y la cinta contiene símbolos de entrada.
 Se efectúan lastransiciones pertinentes según la función de transición.
 Si la cabeza lectora rebasa el extremo izquierdo de la cinta, la cadena es rechazada y el proceso termina (terminación anormal).
 Si la máquina alcanza el estado de parada, la cadena es aceptada.
MT: M(S,Σ,Γ,δ,i,h)
 S: conjunto finito de estados.
 Σ: alfabeto de entrada.
 Γ: alfabeto de símbolos de cinta.
 δ: función detransición (determinista): S x Γ → S x (Γ∪{L,R}).
 i: estado inicial.
 h: estado de aceptación o de parada.
En general, las máquinas de Turing son deterministas.
Tesis De Turing
El poder computacional de una máquina de Turing es tan grande como el de cualquier sistema computacional posible.
Combinación De Máquinas De Turing
Pasos:
1. Eliminar la característica de inicio de los estados inicialesde todas las máquinas, excepto de la primera.
2. Eliminar la característica de parada de todas las máquinas, e incluir un nuevo estado de parada.
3. Para cada estado de parada p y para cada x ∈ Γ:
a) Si la nueva máquina se debe detener al llegar a p con x, añadir un arco x/x de p al nuevo estado de parada.
b) Si al llegar al estado p con el símbolo actual x la máquina compuesta debe...