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 .
Como siempre se detiene, una máquina de este tipo puede decidir si una cadena dada es miembro de un lenguaje formal . La clase de lenguajes que pueden decidir estas máquinas es el conjunto de lenguajes recursivos .
Dada una máquina de Turing arbitraria, determinar si es un decisor es un problema indecidible . Se trata de una variante del problema de la detención , que pregunta si una máquina de Turing se detiene ante una entrada específica.
En la práctica, muchas funciones de interés son computables por máquinas que siempre se detienen. Una máquina que utiliza solo memoria finita en cualquier entrada particular puede verse obligada a detenerse para cada entrada restringiendo sus capacidades de control de flujo de modo que ninguna entrada haga 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 detención. Si restringimos los bucles a un tamaño predeciblemente finito (como el bucle FOR en BASIC ), podemos expresar todas las funciones recursivas primitivas (Meyer y Ritchie, 1967). Un ejemplo de una máquina de este tipo lo proporciona el lenguaje de programación de juguete PL-{GOTO} de Brainerd y Landweber (1974).
Podemos definir además un lenguaje de programación en el que podemos asegurar 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 computable total 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 la totalidad de 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 un lenguaje de programación de este tipo sería una contradicción con la no semidecidibilidad del problema de si una máquina de Turing se detiene en 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:
La respuesta a cada una de estas preguntas es no.
El siguiente teorema muestra 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 imposibilidad de solución algorítmica del problema de la detención .
Teorema : Existen funciones parciales computables de Turing que no tienen extensión a una función computable de Turing total. En particular, la función parcial f definida de modo que f ( n ) = m si y solo si la máquina de Turing con índice n se detiene en la entrada0 con salida m no tiene extensión a una función computable total.
De hecho, si g fuera una función computable total que extendiera f, entonces g sería computable por alguna máquina de Turing; fijemos e como el índice de dicha máquina. Construyamos una máquina de Turing M , utilizando el teorema de recursión de Kleene , que en la entrada0 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 suposición, esta simulación eventualmente devolverá una respuesta. Defina M [ aclarar ] de modo que si g ( n M ) = m entonces el valor de retorno de M es . 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 pregunta, en esencia, si hay otro modelo razonable de computación que calcule sólo funciones totales y calcule todas las funciones computables totales. Informalmente, si tal modelo existiera, 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 de máquinas, habría una secuencia recursivamente enumerable de máquinas de Turing que calculan funciones totales y, por lo tanto, cada función computable total es computable por una de las máquinas T i . Esto es imposible, porque una máquina T podría construirse de manera que en la entrada i la máquina T devuelva . Esta máquina no puede ser equivalente a ninguna máquina T en la lista: supongamos que estuviera en la lista en el índice j . Entonces , que no devuelve un resultado entero. Por lo tanto, no puede ser total, pero la función por construcción debe ser total (si las funciones totales son recursivamente enumerables, entonces esta función puede construirse), lo cual es una contradicción. Esto muestra 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 de la jerarquía aritmética . Por lo tanto, este problema es estrictamente más difícil que el problema de la detención , que pregunta si la máquina con índice e se detiene en la entrada 0. Intuitivamente, esta diferencia en la imposibilidad de solución se debe a que cada instancia del problema de la "máquina total" representa infinitas instancias del problema de la detención.
A uno puede interesarle no sólo si una máquina de Turing es total, sino también si esto puede probarse en un determinado sistema lógico, como la aritmética de Peano de primer orden .
En un sistema de pruebas sólidas , toda máquina de Turing demostrablemente total es, en efecto, total, pero lo inverso no es cierto: informalmente, por cada sistema de pruebas de primer orden que sea lo suficientemente sólido (incluida la aritmética de Peano), hay máquinas de Turing que se supone que son totales, pero no se puede demostrar que lo sean, a menos que el sistema sea inconsistente (en cuyo caso se puede demostrar cualquier cosa). La prueba de su totalidad se basa en algunos supuestos o requiere otro sistema de pruebas.
Así, como se pueden enumerar todas las pruebas en el sistema de pruebas, se puede construir una máquina de Turing con la entrada n que recorra las primeras n pruebas y busque una contradicción. Si encuentra una, 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 no se puede demostrar esto en un sistema de pruebas lo suficientemente fuerte debido a los teoremas de incompletitud de Gödel .
También se puede crear una máquina de Turing que se detendrá si y sólo si el sistema de pruebas es inconsistente y, por lo tanto, no es total para un sistema consistente pero no se puede demostrar como tal: Esta es una máquina de Turing que, independientemente de la entrada, enumera todas las pruebas y se detiene en una contradicción.
Una máquina de Turing que recorre secuencias de Goodstein y se detiene en cero es total, pero no puede demostrarse como tal en la aritmética de Peano.
