En la teoría de la computabilidad , una máquina que siempre se detiene , también llamada decisor [1] o máquina de Turing total , [2] es una máquina de Turing que eventualmente se detiene con cada entrada.
Debido a que siempre se detiene, dicha máquina puede decidir si una cadena dada es miembro de un lenguaje formal . La clase de lenguajes que pueden decidir tales máquinas es exactamente el conjunto de lenguajes recursivos . Sin embargo, el problema de la detención , determinar si una máquina de Turing arbitraria se detiene en una entrada determinada, es en sí mismo un problema indecidible .
Funciones computables por máquinas de Turing totales
En la práctica, muchas funciones de interés son computables por máquinas que siempre se detienen. Una máquina que usa solo memoria finita en cualquier entrada en particular puede ser forzada a detenerse para cada entrada restringiendo sus capacidades de control de flujo para que ninguna entrada haga que la máquina entre en un bucle infinito . Como ejemplo trivial, una máquina que implemente un árbol de decisión final siempre se detendrá.
Sin embargo, no se requiere que la máquina esté completamente libre de capacidades de bucle para garantizar la detención. Si restringimos los bucles para que sean de 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 una máquina de este tipo lo proporciona el lenguaje de programación de juguetes PL- {GOTO} de Brainerd y Landweber (1974).
Podemos definir además un lenguaje de programación en el que podemos asegurarnos de que las funciones aún 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 que se puede calcular 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 el total de funciones recursivas , es decir, las funciones que pueden ser calculadas por una máquina de Turing que siempre se detiene. Esto se debe a que la existencia de dicho lenguaje de programación sería una contradicción con la no semidecidibilidad del problema de si una máquina de Turing se detiene en cada entrada.
Relación con las máquinas de Turing parciales
Una máquina de Turing general calculará una función parcial. Se pueden hacer dos preguntas sobre la relación entre las máquinas de Turing parciales y las máquinas de Turing totales:
- ¿Puede toda función parcial computable por una máquina de Turing parcial extenderse (es decir, ampliar su dominio) para convertirse en una función computable total?
- ¿Es posible cambiar la definición de una máquina de Turing de modo que se pueda encontrar una clase particular de máquinas de Turing totales, calculando todas las funciones computables 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á íntimamente relacionado con la insolubilidad algorítmica del problema de la detención .
- Teorema. Hay 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 entrada 0 con la salida m no tiene extensión a una función computable total.
De hecho, si g fuera una función computable total que se extienda a f, entonces g sería computable por alguna máquina de Turing; fije e como índice de dicha máquina. Construya una máquina de Turing M , usando el teorema de recursividad de Kleene , que en la entrada 0 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 recursividad) . Por supuesto, esta simulación eventualmente devolverá una respuesta. Defina M de modo que si g ( n M ) = m, entonces el valor de retorno de M es m + 1 . Por lo tanto, f ( n M ), el verdadero valor de retorno de M en la entrada 0 , no será igual a g ( n M ). Por tanto, g no se extiende a f .
La segunda pregunta pregunta, en esencia, si existe otro modelo de cálculo razonable que calcule solo 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 tanto, si este nuevo modelo de cálculo consistiera en una secuenciade máquinas, habría una secuencia recursivamente enumerablede máquinas de Turing que calculan funciones totales y de modo que cada función calculable total es calculable por una de las máquinas T i . Esto es imposible, porque una máquinapodrí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: suponga que estuviera en la lista en el índice j . Luego, 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 conjunto de índices de las máquinas de Turing totales.
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á a nivelde la jerarquía aritmética . Por lo tanto, este problema es estrictamente más difícil que el problema de detención , que pregunta si la máquina con índice e se detiene en la entrada 0 . Intuitivamente, esta diferencia en la insolubilidad se debe a que cada instancia del problema de la "máquina total" representa un número infinito de instancias del problema de Detención.
Ver también: Análisis de terminación .
Probabilidad
Uno puede estar interesado no solo en si una máquina de Turing es total, sino también en si esto se puede probar en un determinado sistema lógico, como la aritmética de Peano de primer orden .
En un sistema de prueba de sonido , cada máquina de Turing demostrablemente total es de hecho total, pero lo contrario no es cierto: informalmente, para cada sistema de prueba de primer orden que es lo suficientemente fuerte (incluida la aritmética de Peano), hay máquinas de Turing que se supone que son total, pero no se puede probar como tal, a menos que el sistema sea inconsistente (en cuyo caso se puede probar cualquier cosa). La prueba de su totalidad se basa en algunos supuestos o requiere otro sistema de prueba.
Por lo tanto, como se pueden enumerar todas las pruebas en el sistema de pruebas, se puede construir una máquina de Turing en la entrada n que pase por las primeras n pruebas y busque una contradicción. Si encuentra uno, 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á en cada entrada, pero no se puede probar esto en un sistema de prueba 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 solo si el sistema de prueba es inconsistente y, por lo tanto, no es total para un sistema consistente, pero no se puede probar 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 pasa por secuencias de Goodstein y se detiene en cero es total, pero no se puede probar como tal en la aritmética de Peano.
Ver también
Referencias
- 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. de las Reuniones Nacionales de la ACM, 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 reescritura de términos , Springer.