Conceptos Fundamentales de la Máquina de Turing y la Teoría de la Computabilidad

Construcción Medular de una Máquina de Turing

Preguntas y Respuestas sobre la Máquina de Turing

• ¿Qué acciones puede realizar la Máquina de Turing en la cinta de entrada?

  • Escribe un símbolo en la cinta.

  • Mueve la cabeza lectora/escritora a la izquierda o a la derecha.

• ¿Qué representa el símbolo “?” en las transiciones?

  • Indica que se realiza la acción de insertar un carácter en la cinta de entrada, donde tal carácter puede ser un elemento del alfabeto o un carácter en blanco.

• ¿Cuántos estados halt puede tener una Máquina de Turing?

  • Los que sean necesarios para que funcione de manera adecuada. Se denota tales estados con la letra h.

• ¿Qué acción realiza la Máquina de Turing al encontrar una palabra no aceptada?

  • Cuando una palabra no es aceptada, la Máquina de Turing nunca llega al estado halt. Además, la Máquina de Turing se queda en un ciclo infinito.

• ¿Cuál es el símbolo para representar un movimiento a la derecha del cabezal de lectura?

  • No se especifica un símbolo en particular en el texto original, pero comúnmente se utiliza la letra R (del inglés Right) para representar un movimiento a la derecha.

• ¿Cuáles son los lenguajes aceptados por una Máquina de Turing?

  • Los lenguajes recursivamente numerables, que son los más complejos y, por ende, también acepta los lenguajes libres de contexto y los regulares según la Jerarquía de Chomsky.

Decidibilidad y Teorías Lógicas

Definiciones Clave

• Teoría Lógica: Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de inferencia y un esquema de derivación. A partir de los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría. El conjunto de teoremas de la teoría forman un lenguaje formal.

• Computabilidad: Acción de ser computable, esto es, dado un determinado problema, existe un algoritmo representable en una computadora que puede hallar su solución; entendiéndose un algoritmo como una secuencia o receta de pasos finitos que solucionan el problema.

• Decidibilidad: En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas. Un sistema lógico es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible.

Ejemplos de Problemas No Computables

1. El problema de la palabra para Grupos: Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo.

2. Décimo problema de Hilbert: Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert trata de encontrar un algoritmo que determine si una ecuación diofántica polinómica dada con coeficientes enteros tiene solución entera. Matiyasevich demostró que no existe dicho algoritmo.

3. Decidibilidad de las teorías lógicas:

   • El cálculo de predicados no es decidible. Esto lo demostraron Church y Turing.

   • La teoría de los números reales es decidible. Esto lo demostró Tarski.

Teoría de la Computabilidad

Es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:

• ¿Qué problemas puede resolver una máquina de Turing?

• ¿Qué otros formalismos equivalen a las máquinas de Turing?

• ¿Qué problemas requieren máquinas más poderosas?

• ¿Qué problemas requieren máquinas menos poderosas?