Máquinas de Turing

• El dispositivo computacional más potente: una máquina de estados finitos con una cinta sin límite dividida en celdas. La cinta actúa como entrada, memoria y salida.
• La máquina está controlada por un programa de instrucciones
• instrucción: condición, acción
  • condición: determinada por el estado y símbolo leído
  • acción: una de las operaciones básicas (reemplazar el símbolo por 0, reemplazar el símbolo por 1, izquierda, derecha) y cambiar al próximo estado
  • Cada instrucción puede codificarse como un número binario
• Máquina de Turing universal
  • Cada máquina de Turing puede representarse como un (muy grande) número binario: poniendo los números binarios de sus instrucciones uno a continuación de otro
  • La máquina universal es una máquina que puede simular las operaciones de cualquier máquina de Turing particular
  • La máquina universal lee datos y después las instrucciones (codificadas como números binarios) de una máquina de Turing particular
  • Las instrucciones de la máquina universal le permiten interpretar las instrucciones de la máquina particular y ejecutarlas sobre los datos
• Algunos resultados de la teoría de la computabilidad
  • Tesis de Church-Turing: la máquina universal de Turing es capaz de computar cualquier función computable
  • Analogía: máquina de Turing - programa de ordenador
    Analogía: máquina universal de Turing - ordenador digital
  • Todo lo que puede computarse en un ordenador digital puede computarse en una máquina de Turing
  • Ejemplo de problema sin solución computable: es imposible diseñar una máquina universal que determine si una máquina de Turing arbitraria, dados unos datos arbitrarios, parará o seguirá por siempre realizando cómputos