Máquinas de Turing en Teoría de la Computabilidad
Definición Formal
Una Máquina de Turing (MT) es un modelo matemático de cálculo definido como una 7-tupla:
$$ \Large M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej}) $$
donde:
- /(Q/) es un conjunto finito de estados.
- /(\Sigma/) es el alfabeto de entrada, excluyendo el símbolo de espacio en blanco.
- /(\Gamma/) es el alfabeto de la cinta, con /(\Sigma \subseteq \Gamma/) y un símbolo especial de espacio en blanco /(\sqcup \in \Gamma/).
- /(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}/) es la función de transición.
- /(q_0 \in Q/) es el estado inicial.
- /(q_{acc} \in Q/) es el estado de aceptación.
- /(q_{rej} \in Q/) es el estado de rechazo, distinto de /(q_{acc}/).
Funcionamiento
La máquina opera sobre una cinta infinita en ambas direcciones y sigue estas reglas en cada paso:
- Lee el símbolo actual en la cinta.
- Aplica la función de transición /(\delta/), que cambia de estado, sobrescribe el símbolo en la celda y mueve el cabezal a la izquierda (/(L/)) o derecha (/(R/)).
- Si entra en /(q_{acc}/), acepta la entrada; si entra en /(q_{rej}/), la rechaza.
Clases de Lenguajes Reconocibles
Las Máquinas de Turing permiten clasificar lenguajes en:
- Lenguajes recursivos (R): reconocidos por una MT que siempre detiene su ejecución.
- Lenguajes recursivamente enumerables (RE): reconocidos por una MT que puede no detenerse en algunas entradas.
- Lenguajes no computables: problemas para los cuales no existe ninguna MT que los resuelva, como el problema de la parada.
Variantes de Máquinas de Turing
Algunas extensiones de las MT incluyen:
- MT con múltiples cintas, donde se opera con varias cintas en paralelo.
- MT no deterministas, que pueden tener varias transiciones posibles para un mismo estado y símbolo.
- MT con oráculo, que pueden acceder a respuestas de problemas no computables.
Importancia en la Teoría de la Computabilidad
Las MT son fundamentales en la formalización de la computabilidad, estableciendo los límites de lo que puede ser calculado por un algoritmo. Además, su equivalencia con otros modelos de computación, como las funciones recursivas y la máquina lambda, refuerza su papel como estándar para definir la computabilidad.