Decididor (máquina de Turing)

En la teoría de la computabilidad , un decisor es una máquina de Turing que se detiene para cada entrada. ^{[ 1 ]} Un decisor también se denomina máquina de Turing total ^{[ 2 ]} ya que representa una función total .

Debido a que siempre se detiene, dicha máquina puede decidir si una cadena dada pertenece a un lenguaje formal . La clase de lenguajes que pueden ser decididos por tales máquinas es el conjunto de lenguajes recursivos .

Dado un Turing cualquiera, determinar si es un decisor es un problema indecidible . Esta es una variante del problema de la parada , que pregunta si una máquina de Turing se detiene ante una entrada específica.

En la práctica, muchas funciones de interés pueden ser computadas por máquinas que siempre se detienen. Una máquina que utiliza memoria finita para cada entrada puede ser forzada a detenerse para cada entrada restringiendo sus capacidades de control de flujo, de modo que ninguna entrada provoque que la máquina entre en un bucle infinito . Como ejemplo trivial, una máquina que implementa un árbol de decisión finito siempre se detendrá.

Sin embargo, no es necesario que la máquina esté completamente libre de capacidades de bucle para garantizar la parada. Si restringimos los bucles a un tamaño finito predecible (como el bucle FOR en BASIC ), podemos expresar todas las funciones recursivas primitivas (Meyer y Ritchie, 1967). Un ejemplo de tal máquina lo proporciona el lenguaje de programación de juguete PL-{IR A} de Brainerd y Landweber (1974).

Podemos definir un lenguaje de programación que garantice que incluso las funciones más sofisticadas siempre se detengan. Por ejemplo, la función de Ackermann , que no es recursiva primitiva, es, sin embargo, una función totalmente computable mediante un sistema de reescritura de términos con un orden de reducción en sus argumentos (Ohlebusch, 2002, pág.  67).

A pesar de los ejemplos anteriores de lenguajes de programación que garantizan la terminación de los programas, no existe ningún lenguaje de programación que capture exactamente todas las funciones recursivas , es decir, las funciones que puede calcular una máquina de Turing que siempre se detiene. Esto se debe a que la existencia de tal lenguaje de programación sería una contradicción con la no semidecidibilidad del problema de si una máquina de Turing se detiene con cada entrada .

Una máquina de Turing general calculará una función parcial. Se pueden plantear dos preguntas sobre la relación entre las máquinas de Turing parciales y las máquinas de Turing totales:

1. ¿Es posible extender (es decir, ampliar el dominio de cada función parcial computable por una máquina de Turing parcial) para que se convierta en una función totalmente computable?
2. ¿Es posible modificar la definición de máquina de Turing de manera que se pueda encontrar una clase particular de máquinas de Turing totales que calculen todas las funciones computables totales?

La respuesta a cada una de estas preguntas es no.

El siguiente teorema demuestra que las funciones computables por máquinas que siempre se detienen no incluyen extensiones de todas las funciones computables parciales, lo que implica que la primera pregunta anterior tiene una respuesta negativa. Este hecho está estrechamente relacionado con la irresolubilidad algorítmica del problema de la parada .

En efecto, si g fuera una función totalmente computable que extendiera f , entonces g sería computable por alguna máquina de Turing; fijemos e como el índice de dicha máquina. Construya una máquina de Turing M , utilizando el teorema de recursión de Kleene , que en la entrada0 primero simula la máquina con índice e ejecutándose en un índice n _M para M (por lo tanto, la máquina M puede producir un índice de sí misma; este es el papel del teorema de recursión). Por supuesto, esta simulación eventualmente devolverá una respuesta. Luego M suma 1 y termina, de modo que si g ( n _M ) = m entonces el valor de retorno de M es${\displaystyle m+1}$⁠ . Por lo tanto, f ( n _M ), el verdadero valor de retorno de M en la entrada0 , no será igual a g ( n _M ). Por lo tanto, g no extiende f .

La segunda pregunta plantea, en esencia, si existe otro modelo razonable de computación que calcule únicamente funciones totales y calcule todas las funciones computables totales. De manera informal, si existiera tal modelo, cada una de sus computadoras podría ser simulada por una máquina de Turing. Por lo tanto, si este nuevo modelo de computación consistiera en una secuencia${\displaystyle M_{1},M_{2},\ldots }$de máquinas, habría una secuencia recursivamente enumerable${\displaystyle T_{1},\ldots T_{2},\ldots }$de máquinas de Turing que computan funciones totales y de modo que cada función total computable sea computable por una de las máquinas T _i . Esto es imposible, porque se podría construir una máquina total T tal que, con la entrada i, la máquina T devuelva${\displaystyle T_{i}(i)+1\,}$Esta máquina no puede ser equivalente a ninguna máquina T de la lista: supongamos que estuviera en la lista en el índice j . Entonces${\displaystyle T_{j}(j)=T_{j}(j)+1\,}$, una contradicción. Esto demuestra que la segunda pregunta tiene una respuesta negativa.

El problema de decisión de si la máquina de Turing con índice e se detendrá en cada entrada no es decidible. De hecho, este problema está en el nivel${\displaystyle \Pi _{2}^{0}}$de la jerarquía aritmética . Por lo tanto, este problema es estrictamente más difícil que el problema de la parada , que pregunta si la máquina con índice e se detiene con la entrada 0. Intuitivamente, esta diferencia en la irresolubilidad se debe a que cada instancia del problema de la "máquina total" representa infinitas instancias del problema de la parada.

Uno puede estar interesado no solo en si una máquina de Turing es total, sino también en si esto se puede demostrar en un determinado sistema lógico, como la aritmética de Peano de primer orden .

En un sistema de prueba sólido , toda máquina de Turing demostrablemente total es, en efecto, total, pero lo contrario no es cierto: informalmente, para cada sistema de prueba de primer orden suficientemente robusto (incluida la aritmética de Peano), existen máquinas de Turing que se asumen totales, pero que no pueden probarse como tales, a menos que el sistema sea inconsistente (en cuyo caso se puede probar cualquier cosa). La prueba de su totalidad se basa en ciertas suposiciones o requiere otro sistema de prueba.

Dado que se pueden enumerar todas las pruebas en el sistema de pruebas, se puede construir una máquina de Turing con una entrada n que recorra las primeras n pruebas y busque una contradicción. Si la encuentra, entra en un bucle infinito y nunca se detiene; de ​​lo contrario, se detiene. Si el sistema es consistente , la máquina de Turing se detendrá con cada entrada, pero esto no se puede demostrar con un sistema de pruebas suficientemente robusto debido a los teoremas de incompletitud de Gödel .

También se puede crear una máquina de Turing que se detendrá si y solo si el sistema de prueba es inconsistente, y por lo tanto no es total para un sistema consistente pero no se puede demostrar que lo sea: Esta es una máquina de Turing que, independientemente de la entrada, enumera todas las pruebas y se detiene ante una contradicción.

Una máquina de Turing que recorre secuencias de Goodstein y se detiene en cero es total, pero no se puede demostrar como tal en la aritmética de Peano.

• BlooP y FlooP
• Programación funcional total
• Análisis de terminación

• Brainerd, WS, Landweber, LH (1974), Teoría de la computación , Wiley.
• Meyer, AR , Ritchie, DM (1967), La complejidad de los programas de bucle , Proc. of the ACM National Meetings, 465.
• Sipser, M. (2006), Introducción a la teoría de la computación , PWS Publishing Co.
• Kozen, DC (1997), Autómatas y computabilidad , Springer.
• Ohlebusch, E. (2002), Temas avanzados en la reescritura de términos , Springer.