Definición Formal

                                     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 dichos estados. 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.

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

M = (Q, Σ, Γ, 8, 6, F, δ),

donde:

• Qes 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 (Σ (Γ).

⚫s EQ es el estado inicial.

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

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

• δ: Q × → Q× × {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. Existe 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.