Problema de detención

Problema de determinar si un programa determinado terminará de ejecutarse o continuará para siempre

En la teoría de la computabilidad , el problema de la detención es el problema de determinar, a partir de una descripción de un programa de computadora arbitrario y una entrada, si el programa terminará de ejecutarse o continuará ejecutándose para siempre. El problema de detención es indecidible , lo que significa que no existe ningún algoritmo general que resuelva el problema de detención para todos los pares posibles de programa-entrada.

Una parte clave del planteamiento formal del problema es una definición matemática de una computadora y un programa, generalmente a través de una máquina de Turing . La prueba muestra entonces, para cualquier programa f que pueda determinar si los programas se detienen, que un programa "patológico" g , llamado con alguna entrada, puede pasar su propia fuente y su entrada a f y luego hacer específicamente lo contrario de lo que f predice g. servirá. No puede existir ninguna f que maneje este caso, lo que muestra indecidibilidad. Esta prueba es importante para los esfuerzos informáticos prácticos, ya que define una clase de aplicaciones que ninguna invención de programación puede realizar perfectamente.

Fondo

El problema de la detención es un problema de decisión sobre las propiedades de los programas de computadora en un modelo de cálculo fijo de Turing completo , es decir, todos los programas que pueden escribirse en algún lenguaje de programación determinado que sea lo suficientemente general como para ser equivalente a una máquina de Turing. El problema es determinar, dado un programa y una entrada al programa, si el programa finalmente se detendrá cuando se ejecute con esa entrada. En este marco abstracto, no hay limitaciones de recursos en cuanto a la cantidad de memoria o tiempo requerido para la ejecución del programa; puede tardar un tiempo arbitrario y utilizar una cantidad arbitraria de espacio de almacenamiento antes de detenerse. La pregunta es simplemente si el programa dado se detendrá alguna vez ante una entrada en particular.

Por ejemplo, en pseudocódigo , el programa

while (true) continue

no se detiene; más bien, continúa para siempre en un bucle infinito . Por otra parte, el programa

print "Hello, world!"

se detiene.

Si bien decidir si estos programas se detienen es sencillo, los programas más complejos resultan problemáticos. Una solución al problema podría ser ejecutar el programa durante una serie de pasos y comprobar si se detiene. Sin embargo, mientras el programa se esté ejecutando, no se sabe si eventualmente se detendrá o se ejecutará para siempre. Turing demostró que no existe ningún algoritmo que siempre decida correctamente si, para un programa y una entrada arbitrarios determinados, el programa se detiene cuando se ejecuta con esa entrada. La esencia de la prueba de Turing es que se puede hacer que cualquier algoritmo de este tipo produzca resultados contradictorios y, por lo tanto, no puede ser correcto.

Consecuencias de la programación

Algunos bucles infinitos pueden resultar bastante útiles. Por ejemplo, los bucles de eventos suelen codificarse como bucles infinitos. ^[1] Sin embargo, la mayoría de las subrutinas están destinadas a finalizar. ^[2] En particular, en la informática dura en tiempo real , los programadores intentan escribir subrutinas que no solo tengan garantizado su finalización, sino que también lo hagan antes de una fecha límite determinada. ^[3]

A veces, estos programadores utilizan algún lenguaje de programación de propósito general (Turing-completo), pero intentan escribir en un estilo restringido, como MISRA C o SPARK , que facilite demostrar que las subrutinas resultantes finalizan antes de la fecha límite determinada. ^{[ cita necesaria ]}

Otras veces, estos programadores aplican la regla del mínimo poder : utilizan deliberadamente un lenguaje informático que no es completamente Turing completo. Frecuentemente se trata de lenguajes que garantizan el fin de todas las subrutinas, como por ejemplo Coq . ^{[ cita necesaria ]}

Errores comunes

La dificultad del problema de la detención radica en el requisito de que el procedimiento de decisión debe funcionar para todos los programas e insumos. Un programa particular se detiene ante una entrada determinada o no se detiene. Considere un algoritmo que siempre responde "se detiene" y otro que siempre responde "no se detiene". Para cualquier programa y entrada específicos, uno de estos dos algoritmos responde correctamente, aunque nadie sepa cuál. Sin embargo, ninguno de los algoritmos resuelve el problema de la detención en general.

Hay programas ( intérpretes ) que simulan la ejecución de cualquier código fuente que se les proporcione. Dichos programas pueden demostrar que un programa se detiene si este es el caso: el propio intérprete eventualmente detendrá su simulación, lo que demuestra que el programa original se detuvo. Sin embargo, un intérprete no se detendrá si su programa de entrada no se detiene, por lo que este enfoque no puede resolver el problema de detención como se indicó; no responde correctamente "no se detiene" para los programas que no se detienen.

El problema de la detención es teóricamente decidible para autómatas lineales acotados (LBA) o máquinas deterministas con memoria finita. Una máquina con memoria finita tiene un número finito de configuraciones y, por lo tanto, cualquier programa determinista en ella debe eventualmente detener o repetir una configuración anterior: ^[4]

... cualquier máquina de estados finitos, si se la deja completamente sola, eventualmente caerá en un patrón repetitivo perfectamente periódico . La duración de este patrón repetitivo no puede exceder el número de estados internos de la máquina...

Sin embargo, una computadora con un millón de piezas pequeñas, cada una con dos estados, tendría al menos 2 ^1.000.000 de estados posibles: ^[5]

Este es un 1 seguido de unos trescientos mil ceros... Incluso si tal máquina funcionara en las frecuencias de los rayos cósmicos, los eones de la evolución galáctica serían nada comparados con el tiempo de un viaje a través de tal ciclo:

Aunque una máquina puede ser finita, los autómatas finitos "tienen una serie de limitaciones teóricas": ^[5]

... las magnitudes involucradas deberían llevar a uno a sospechar que los teoremas y argumentos basados ​​principalmente en la mera finitud [del] diagrama de estados pueden no tener mucha importancia.

También se puede decidir automáticamente si una máquina no determinista con memoria finita se detiene en ninguna, en algunas o en todas las posibles secuencias de decisiones no deterministas, enumerando estados después de cada posible decisión.

Historia

En abril de 1936, Alonzo Church publicó su prueba de la indecidibilidad de un problema en el cálculo lambda . La prueba de Turing se publicó más tarde, en enero de 1937. Desde entonces, se han descrito muchos otros problemas indecidibles, incluido el problema de la detención que surgió en los años cincuenta.

Línea de tiempo

• 1900 : David Hilbert plantea sus "23 preguntas" (conocidas actualmente como problemas de Hilbert ) en el Segundo Congreso Internacional de Matemáticos en París. "De ellas, la segunda era la de demostrar la coherencia de los ' axiomas de Peano ' de los que, como había demostrado, dependía el rigor de las matemáticas". ( 1900 ) ^[6]
• 1920  – 1921 : Emil Post explora el problema de la detención de los sistemas de etiquetas , considerándolo un candidato a la insolubilidad. ^[7] Su insolubilidad no fue establecida hasta mucho más tarde, por Marvin Minsky . ^[8] ( 1920 ) ( 1921 )
• 1928 : Hilbert reformula su 'Segundo problema' en el Congreso Internacional de Bolonia. ^[9] Planteó tres preguntas: es decir, #1: ¿Estaban completas las matemáticas ? #2: ¿Fueron consistentes las matemáticas ? #3: ¿Eran decidibles las matemáticas ? ^[10] La tercera pregunta se conoce como Entscheidungsproblem (Problema de decisión). ^[11] ( 1928 )
• 1930 : Kurt Gödel anuncia una prueba como respuesta a las dos primeras preguntas de Hilbert de 1928. ^[12] "Al principio él [Hilbert] sólo estaba enojado y frustrado, pero luego comenzó a tratar de abordar el problema de manera constructiva... El propio Gödel sintió—y expresó esa idea en su artículo—que su trabajo no contradecía el de Hilbert. punto de vista formalista" ( 1930 ) ^[13]
• 1931 : Gödel publica "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I" ( 1931 ) ^[14]
• 19 de abril de 1935 : Alonzo Church publica "Un problema irresoluble de la teoría elemental de números", que propone que la noción intuitiva de una función efectivamente calculable puede formalizarse mediante funciones recursivas generales o, de manera equivalente, mediante funciones definibles por lambda . Demuestra que el problema de detención del cálculo lambda (es decir, si una expresión lambda dada tiene una forma normal ) no se puede calcular de manera efectiva. ( 1935-04-19 ) ^[15]
• 1936 : Church publica la primera prueba de que el Entscheidungsproblem es irresoluble, utilizando una noción de cálculo por funciones recursivas . ( 1936 ) ^[dieciséis]
• 7 de octubre de 1936 : Se recibe el artículo de Emil Post "Procesos combinatorios finitos. Formulación I". Post agrega a su "proceso" una instrucción "(C) Detener". Llamó a ese proceso "tipo 1... si el proceso que determina termina para cada problema específico". ( 1936-10-07 ) ^[17]
• Mayo de 1936  - enero de 1937 : el artículo de Alan Turing Sobre números computables con una aplicación al Entscheidungsproblem se imprime en mayo de 1936 y se imprime en enero de 1937. ^[18] Turing demuestra que tres problemas son indecidibles: el problema de la "satisfacción", el " "Impresión" y el Entscheidungsproblem . ^[19] La prueba de Turing difiere de la de Church al introducir la noción de computación por máquina. Este es uno de los "primeros ejemplos de problemas de decisión que resultaron irresolubles". ^{[20] [ página necesaria ]} ( 1936-05 ) ( 1937-01 )
• 1939 : J. Barkley Rosser observa la equivalencia esencial del "método eficaz" definido por Gödel, Church y Turing ( 1939 ) ^[21]
• 1943 : En un artículo, Stephen Kleene afirma que "Al establecer una teoría algorítmica completa, lo que hacemos es describir un procedimiento... cuyo procedimiento termina necesariamente y de tal manera que del resultado podamos leer una respuesta definitiva: 'Sí'. ' o 'No' a la pregunta: '¿Es verdadero el valor del predicado?'". ( 1943 )
• 1952 : Kleene incluye una discusión sobre la insolubilidad del problema de detención para las máquinas de Turing y lo reformula en términos de máquinas que "eventualmente se detienen", es decir, se detienen: "... no existe ningún algoritmo para decidir si una máquina determinada, cuando arranca desde cualquier situación dada, eventualmente se detiene ". ( 1952 ) ^[22]
• 1952 : Martin Davis utiliza el término "problema de detención" en una serie de conferencias en el Laboratorio de Sistemas de Control de la Universidad de Illinois en 1952. Es probable que este sea el primer uso del término. ( 1952 ) ^[23]

Origen del problema de detención

Muchos artículos y libros de texto remiten la definición y prueba de la indecidibilidad del problema de la detención al artículo de Turing de 1936. Sin embargo, esto no es correcto. ^{[19] [24]} Turing no utilizó los términos "detener" o "detenerse" en ninguno de sus trabajos publicados, incluido su artículo de 1936. ^[25] Una búsqueda en la literatura académica de 1936 a 1958 mostró que el primer material publicado que utilizó el término "problema de detención" fue Rogers (1957). Sin embargo, Rogers dice que tenía a su disposición un borrador de Davis (1958), ^[19] y Martin Davis afirma en la introducción que "el experto tal vez encuentre alguna novedad en la disposición y tratamiento de los temas", ^[26] por lo que el La terminología debe atribuirse a Davis. ^{[19] [24]} Davis declaró en una carta que se había estado refiriendo al problema de la detención desde 1952. ^[23] El uso en el libro de Davis es el siguiente: ^[27]

"[...] deseamos determinar si [una máquina de Turing] Z, si se coloca en un estado inicial determinado, eventualmente se detendrá o no. A este problema lo llamamos el problema de la detención de Z. [...]

Teorema 2.2 Existe una máquina de Turing cuyo problema de detención es recursivamente irresoluble .

Un problema relacionado es el problema de impresión de una máquina de Turing simple Z con respecto a un símbolo Si _" .

Un posible precursor de la formulación de Davis es la declaración de Kleene de 1952, que difiere sólo en la redacción: ^{[19] [22]}

No existe ningún algoritmo para decidir si una máquina determinada, cuando se arranca desde una situación determinada, finalmente se detiene.

El problema de la detención es equivalente de Turing tanto al problema de impresión de Davis ("¿una máquina de Turing que parte de un estado dado imprime alguna vez un símbolo dado?") como al problema de impresión considerado en el artículo de Turing de 1936 ("¿una máquina de Turing que parte de un estado en blanco?" ¿Alguna vez la cinta ha impreso un símbolo determinado?"). Sin embargo, la equivalencia de Turing es bastante vaga y no significa que los dos problemas sean iguales. Hay máquinas que imprimen pero no se detienen, y que se detienen pero no imprimen. Los problemas de impresión y detención abordan cuestiones diferentes y presentan importantes diferencias conceptuales y técnicas. Por lo tanto, Davis simplemente estaba siendo modesto cuando dijo: ^[19]

También podría mencionarse que Turing fue el primero en comprobar la insolubilidad de esencialmente estos problemas.

Formalización

En su prueba original, Turing formalizó el concepto de algoritmo al introducir las máquinas de Turing . Sin embargo, el resultado no es de ninguna manera específico para ellos; se aplica igualmente a cualquier otro modelo de computación que sea equivalente en su poder computacional a las máquinas de Turing, como los algoritmos de Markov , el cálculo Lambda , los sistemas Post , las máquinas de registro o los sistemas de etiquetas .

Lo importante es que la formalización permita una asignación directa de algoritmos a algún tipo de datos sobre el que el algoritmo pueda operar. Por ejemplo, si el formalismo permite que los algoritmos definan funciones sobre cadenas (como las máquinas de Turing), entonces debería haber una asignación de estos algoritmos a cadenas, y si el formalismo permite que los algoritmos definan funciones sobre números naturales (como las funciones computables ), entonces debería haber ser un mapeo de algoritmos a números naturales. La asignación a cadenas suele ser la más sencilla, pero las cadenas sobre un alfabeto con n caracteres también se pueden asignar a números interpretándolos como números en un sistema de numeración n -ario .

Representación como conjunto

La representación convencional de los problemas de decisión es el conjunto de objetos que poseen la propiedad en cuestión. El conjunto de parada

K = {( yo , x ) | el programa i se detiene cuando se ejecuta en la entrada x }

representa el problema de la detención.

Este conjunto es recursivamente enumerable , lo que significa que hay una función computable que enumera todos los pares ( i ,  x ) que contiene. Sin embargo, el complemento de este conjunto no es recursivamente enumerable. ^[28]

Hay muchas formulaciones equivalentes del problema de la detención; cualquier conjunto cuyo grado de Turing sea igual al del problema de detención es una formulación de este tipo. Ejemplos de tales conjuntos incluyen:

• { yo | El programa que finalmente se detiene cuando lo ejecuto con la entrada 0}
• { yo | hay una entrada x tal que el programa i finalmente se detiene cuando se ejecuta con la entrada x }.

Concepto de prueba

Christopher Strachey esbozó una prueba por contradicción de que el problema de la detención no tiene solución. ^{[29] [30]} La prueba procede de la siguiente manera: Supongamos que existe una función computable total se detiene(f) que devuelve verdadero si la subrutina f se detiene (cuando se ejecuta sin entradas) y devuelve falso en caso contrario. Ahora considere la siguiente subrutina:

def  g ():  si  se detiene ( g ):  loop_forever ()

halts(g) debe devolver verdadero o falso, porque se supuso que halts era total . Si halts(g) devuelve verdadero, entonces g llamará a loop_forever y nunca se detendrá, lo cual es una contradicción. Si halts(g) devuelve false, entonces g se detendrá, porque no llamará a loop_forever ; Esto también es una contradicción. En general, g hace lo contrario de lo que halts dice que g debería hacer, por lo que halts(g) no puede devolver un valor de verdad que sea coherente con si g se detiene o no. Por lo tanto, la suposición inicial de que las paradas es una función total computable debe ser falsa.

Bosquejo de prueba rigurosa.

El concepto anterior muestra el método general de prueba, pero la función computable se detiene no toma directamente una subrutina como argumento; en su lugar, toma el código fuente de un programa. Además, la definición de g es autorreferencial . Una prueba rigurosa aborda estas cuestiones. El objetivo general es mostrar que no existe una función computable total que decida si un programa arbitrario i se detiene ante una entrada arbitraria x ; es decir, la siguiente función h (para "se detiene") no es computable: ^[31]

${\displaystyle h(i,x)={\begin{cases}1&{\text{if }}{\text{ program }}i{\text{ halts on input }}x,\\0&{\text{otherwise.}}\end{cases}}}$

Aquí el programa i se refiere al iésimo programa en una enumeración de todos los programas de un modelo de cálculo fijo de Turing completo .

Valores posibles para una función computable total f dispuesta en una matriz 2D. Las celdas naranjas son la diagonal. Los valores de f ( i , i ) y g ( i ) se muestran en la parte inferior; U indica que la función g no está definida para un valor de entrada particular.

La prueba procede estableciendo directamente que ninguna función computable total con dos argumentos puede ser la función requerida h . Como en el esquema del concepto, dada cualquier función binaria computable total f , la siguiente función parcial g también es computable mediante algún programa e :

${\displaystyle g(i)={\begin{cases}0&{\text{if }}f(i,i)=0,\\{\text{undefined}}&{\text{otherwise.}}\end{cases}}}$

La verificación de que g es computable se basa en las siguientes construcciones (o sus equivalentes):

• subprogramas computables (el programa que calcula f es un subprograma en el programa e ),
• duplicación de valores (el programa e calcula las entradas i , i para f a partir de la entrada i para g ),
• ramificación condicional (el programa e selecciona entre dos resultados dependiendo del valor que calcula para f ( i , i )),
• no producir un resultado definido (por ejemplo, haciendo un bucle para siempre),
• devolviendo un valor de 0.

El siguiente pseudocódigo para e ilustra una forma sencilla de calcular g :

procedimiento e ( i ) : si f ( i , i ) == 0 entonces devuelve 0 , de lo contrario se repite para siempre            

Debido a que g es parcialmente computable, debe haber un programa e que calcule g , suponiendo que el modelo de cálculo es completo de Turing. Este programa es uno de todos los programas en los que está definida la función de parada h . El siguiente paso de la prueba muestra que h ( e , e ) no tendrá el mismo valor que f ( e , e ).

De la definición de g se deduce que debe cumplirse exactamente uno de los dos casos siguientes:

• f ( e , e ) = 0 y entonces g ( e ) = 0. En este caso el programa e se detiene en la entrada e , entonces h ( e , e ) = 1.
• f ( e , e ) ≠ 0 y entonces g ( e ) no está definido. En este caso, el programa e no se detiene en la entrada e , por lo que h ( e , e ) = 0.

En cualquier caso, f no puede ser la misma función que h . Debido a que f era una función computable total arbitraria con dos argumentos, todas esas funciones deben diferir de h .

Esta prueba es análoga al argumento diagonal de Cantor . Se puede visualizar una matriz bidimensional con una columna y una fila para cada número natural, como se indica en la tabla anterior. El valor de f ( i , j ) se coloca en la columna i , fila j . Debido a que se supone que f es una función computable total, cualquier elemento de la matriz se puede calcular usando f . La construcción de la función g se puede visualizar usando la diagonal principal de esta matriz. Si la matriz tiene un 0 en la posición ( i , i ), entonces g ( i ) es 0. De lo contrario, g ( i ) no está definido. La contradicción proviene del hecho de que hay alguna columna e de la matriz correspondiente a g . Ahora supongamos que f era la función de detención h , si g ( e ) está definida ( g ( e ) = 0 en este caso), g ( e ) se detiene, por lo que f ( e,e ) = 1. Pero g ( e ) = 0 solo cuando f ( e,e ) = 0, lo que contradice f ( e,e ) = 1. De manera similar, si g ( e ) no está definido, entonces detener la función f ( e,e ) = 0, lo que conduce a g ( e ) = 0 bajo la construcción de g . Esto contradice la suposición de que g ( e ) no está definido. En ambos casos surge la contradicción. Por lo tanto, cualquier función computable arbitraria f no puede ser la función de parada h .

Teoría de la computabilidad

Un método típico para demostrar que un problema es indecidible es reducir el problema de detención a . Por ejemplo, no puede haber un algoritmo general que decida si una afirmación dada sobre los números naturales es verdadera o falsa. La razón de esto es que la proposición que establece que un determinado programa se detendrá dada una determinada entrada se puede convertir en una afirmación equivalente sobre los números naturales. Si un algoritmo pudiera encontrar el valor de verdad de cada enunciado sobre números naturales, ciertamente podría encontrar el valor de verdad de éste; pero eso determinaría si el programa original se detiene. ${\displaystyle P}$ ${\displaystyle P}$

El teorema de Rice generaliza el teorema de que el problema de la detención no tiene solución. Afirma que para cualquier propiedad no trivial, no existe un procedimiento de decisión general que, para todos los programas, decida si la función parcial implementada por el programa de entrada tiene esa propiedad. (Una función parcial es una función que no siempre produce un resultado, por lo que se utiliza para modelar programas que pueden producir resultados o no detenerse). Por ejemplo, la propiedad "detenerse para la entrada 0" es indecidible. Aquí, "no trivial" significa que el conjunto de funciones parciales que satisfacen la propiedad no es el conjunto vacío ni el conjunto de todas las funciones parciales. Por ejemplo, "se detiene o no se detiene en la entrada 0" es claramente cierto para todas las funciones parciales, por lo que es una propiedad trivial y puede decidirse mediante un algoritmo que simplemente informa "verdadero". Además, este teorema es válido sólo para las propiedades de la función parcial implementada por el programa; El teorema de Rice no se aplica a las propiedades del programa en sí. Por ejemplo, "detenerse en la entrada 0 dentro de 100 pasos" no es una propiedad de la función parcial que implementa el programa; es una propiedad del programa que implementa la función parcial y es muy decidible.

Gregory Chaitin ha definido una probabilidad de detención , representada por el símbolo Ω , un tipo de número real que informalmente se dice que representa la probabilidad de que un programa producido aleatoriamente se detenga. Estos números tienen el mismo grado de Turing que el problema de la detención. Es un número normal y trascendental que se puede definir pero no se puede calcular por completo . Esto significa que se puede demostrar que no existe ningún algoritmo que produzca los dígitos de Ω, aunque sus primeros dígitos se pueden calcular en casos simples.

Dado que la respuesta negativa al problema de la detención muestra que hay problemas que no pueden resolverse con una máquina de Turing, la tesis de Church-Turing limita lo que puede lograr cualquier máquina que implemente métodos eficaces . Sin embargo, no todas las máquinas concebibles por la imaginación humana están sujetas a la tesis de Church-Turing (por ejemplo, las máquinas oráculo ). Es una cuestión abierta si puede haber procesos físicos deterministas reales que, a largo plazo, eludan la simulación por una máquina de Turing y, en particular, si dicho proceso hipotético podría aprovecharse de manera útil en forma de una máquina calculadora (una hipercomputadora ). Esto podría resolver, entre otras cosas, el problema de la detención de una máquina de Turing. También queda abierta la cuestión de si dichos procesos físicos desconocidos intervienen en el funcionamiento del cerebro humano y si los seres humanos pueden resolver el problema de la detención. ^[32]

Aproximaciones

La prueba de Turing muestra que no puede haber ningún método mecánico general (es decir, una máquina de Turing o un programa en algún modelo de cálculo equivalente ) para determinar si los algoritmos se detienen. Sin embargo, cada caso individual del problema de la detención tiene una respuesta definitiva, que puede o no ser prácticamente computable. Dado un algoritmo y una entrada específicos, a menudo se puede demostrar que se detiene o no y, de hecho, los informáticos suelen hacer precisamente eso como parte de una prueba de corrección . Hay algunas heurísticas que se pueden utilizar de forma automatizada para intentar construir una prueba, lo que con frecuencia tiene éxito en programas típicos. Este campo de investigación se conoce como análisis de terminación automatizado .

Se han establecido algunos resultados sobre el rendimiento teórico de la heurística de detener problemas, en particular la fracción de programas de un tamaño determinado que pueden clasificarse correctamente mediante un algoritmo recursivo. Estos resultados no dan números precisos porque las fracciones no son computables y también dependen en gran medida de la elección de la codificación del programa utilizada para determinar el "tamaño". Por ejemplo, considere clasificar los programas por su número de estados y utilizar un modelo de cálculo específico de "cinta semiinfinita de Turing" que genera errores (sin detenerse) si el programa se ejecuta en el lado izquierdo de la cinta. Luego , sobre programas elegidos uniformemente por número de estados. Pero este resultado es en cierto sentido "trivial" porque estos programas decidibles son simplemente los que se caen de la cinta, y la heurística es simplemente predecir que no se detendrá debido a un error. Así, un detalle aparentemente irrelevante, a saber, el tratamiento de los programas con errores, puede convertirse en el factor decisivo para determinar la fracción de programas. ^[33] ${\displaystyle \lim _{n\to \infty }P(x\,{\text{halts is decidable}}\mid x\,{\text{has}}\,n\,{\text{states}})=1}$ ${\displaystyle x}$

Para evitar estos problemas, se han desarrollado varias nociones restringidas del "tamaño" de un programa. Una numeración densa de Gödel asigna números a programas de modo que cada función computable ocurre una fracción positiva en cada secuencia de índices de 1 a n, es decir, una Gödelización φ es densa si y sólo para todos , existe una tal que . Por ejemplo, una numeración que asigna índices a programas no triviales y todos los demás índices el estado de error no es denso, pero existe una numeración densa de Gödel de programas Brainfuck sintácticamente correctos . ^[34] Una numeración densa de Gödel se llama óptima si, para cualquier otra numeración de Gödel , existe una función recursiva total 1-1 y una constante tal que para todos , y . Esta condición asegura que todos los programas tengan índices no mucho mayores que sus índices en cualquier otra numeración de Gödel. Las numeraciones óptimas de Gödel se construyen numerando las entradas de una máquina de Turing universal . ^[35] Una tercera noción de tamaño utiliza máquinas universales que operan en cadenas binarias y mide la longitud de la cadena necesaria para describir el programa de entrada. Una máquina universal U es una máquina para la cual entre todas las demás máquinas V existe una función total computable h tal que . Una máquina óptima es una máquina universal que alcanza el límite de invariancia de complejidad de Kolmogorov , es decir, para cada máquina V , existe c tal que para todas las salidas x , si un programa V de longitud n genera x , entonces existe un programa U de como máximo, generando x . ^[36] ${\displaystyle i}$ ${\displaystyle c>0}$ ${\displaystyle \liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c}$ ${\displaystyle 2^{n}}$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle i}$ ${\displaystyle \alpha _{i}=\phi _{f(i)}}$ ${\displaystyle f(i)\leq ci}$ ${\displaystyle V(x)=U(h(x))}$ ${\displaystyle n+c}$

Consideramos funciones computables parciales (algoritmos) . Para cada uno, consideramos la fracción de errores entre todos los programas de tamaño métrico como máximo , contando cada programa que no termina, produce una respuesta de "no sé", o produce una respuesta incorrecta, es decir, se detiene y genera , o no parada y salidas . El comportamiento se puede describir de la siguiente manera, para Gödelizaciones densas y máquinas óptimas: ^{[34] [36]} ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle \epsilon _{n}(A)}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle A(x)}$DOES_NOT_HALT ${\displaystyle x}$ ${\displaystyle A(x)}$HALTS

• Para cada algoritmo , ${\displaystyle A}$ ${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$
• Existe tal que para cada algoritmo , ${\displaystyle \epsilon >0}$ ${\displaystyle A}$ ${\displaystyle \limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon }$
• ${\displaystyle \inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0}$. Sin embargo, esto incluye algoritmos que producen respuestas incorrectas.
• Si consideramos sólo algoritmos "honestos" que pueden no estar definidos pero que nunca producen respuestas incorrectas, entonces, dependiendo de la métrica, puede ser o no 0. En particular, es 0 para las máquinas universales con total izquierdo, pero para las máquinas efectivamente óptimas es mayor. que 0. ^[36] ${\displaystyle \inf _{A\,{\textrm {honest}}}\liminf _{n\to \infty }\epsilon _{n}(A)}$

La naturaleza compleja de estos límites se debe al comportamiento oscilatorio de . Rara vez aparecen nuevas variedades de programas que vienen en "bloques" arbitrariamente grandes y una fracción de repeticiones en constante crecimiento. Si los bloques de nuevas variedades se incluyen en su totalidad, la tasa de error es al menos , pero entre bloques la fracción de repeticiones categorizadas correctamente puede ser arbitrariamente alta. En particular, una heurística de "recuento" que simplemente recuerda las primeras N entradas y reconoce sus equivalentes permite alcanzar una tasa de error arbitrariamente baja con una frecuencia infinita. ^[34] ${\displaystyle \epsilon _{n}(A)}$ ${\displaystyle \epsilon }$

Teoremas de incompletitud de Gödel

Los conceptos planteados por los teoremas de incompletitud de Gödel son muy similares a los planteados por el problema de la detención, y las demostraciones son bastante similares. De hecho, una forma más débil del primer teorema de incompletitud es una consecuencia fácil de la indecidibilidad del problema de la detención. Esta forma más débil difiere del enunciado estándar del teorema de incompletitud al afirmar que una axiomatización de los números naturales que sea completa y sólida es imposible. La parte "sólida" es el debilitamiento: significa que requerimos que el sistema axiomático en cuestión demuestre sólo afirmaciones verdaderas sobre los números naturales. Dado que solidez implica coherencia , esta forma más débil puede verse como un corolario de la forma fuerte. Es importante observar que el enunciado de la forma estándar del primer teorema de incompletitud de Gödel no se preocupa en absoluto por el valor de verdad de un enunciado, sino que sólo se refiere a la cuestión de si es posible encontrarlo mediante una demostración matemática .

La forma más débil del teorema se puede demostrar a partir de la indecidibilidad del problema de detención de la siguiente manera. ^[37] Supongamos que tenemos una axiomatización sólida (y por lo tanto consistente) y completa de todos los enunciados verdaderos de lógica de primer orden sobre los números naturales . Luego podemos construir un algoritmo que enumere todas estas declaraciones. Esto significa que existe un algoritmo N ( n ) que, dado un número natural n , calcula un enunciado lógico verdadero de primer orden sobre números naturales, y que para todos los enunciados verdaderos, existe al menos un n tal que N ( n ) produce esa afirmación. Ahora supongamos que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que este enunciado se puede expresar con un enunciado lógico de primer orden, digamos H ( a , i ). Dado que la axiomatización es completa, se deduce que o hay un n tal que N ( n ) = H ( a , i ) o hay un n ′ tal que N ( n ′ ) = ¬ H ( a , i ). Entonces, si iteramos sobre todo n hasta encontrar H ( a , i ) o su negación, siempre nos detendremos y, además, la respuesta que nos dé será verdadera (por solidez). Esto significa que nos da un algoritmo para decidir el problema de detención. Como sabemos que no puede existir tal algoritmo, se deduce que la suposición de que existe una axiomatización consistente y completa de todos los enunciados verdaderos de la lógica de primer orden sobre los números naturales debe ser falsa.

Generalización

En los libros de texto de computabilidad se pueden encontrar muchas variantes del problema de la detención. ^[38] Por lo general, estos problemas son RE-completos y describen conjuntos de complejidad en la jerarquía aritmética , al igual que el problema de detención estándar. Por tanto, las variantes son indecidibles y el problema de detención estándar se reduce a cada variante y viceversa. Sin embargo, algunas variantes tienen un mayor grado de insolubilidad y no pueden reducirse al problema de detención estándar. Los siguientes dos ejemplos son comunes. ${\displaystyle \Sigma _{1}^{0}}$

Detener todas las entradas

El problema de detención universal , también conocido (en teoría de la recursividad ) como totalidad , es el problema de determinar si un programa de computadora dado se detendrá para cada entrada (el nombre totalidad proviene de la pregunta equivalente de si la función calculada es total ). Este problema no sólo es indecidible, como lo es el problema de la detención, sino que además es altamente indecidible. En términos de jerarquía aritmética , es completo. ^[39] ${\displaystyle \Pi _{2}^{0}}$

Esto significa, en particular, que ni siquiera con un oráculo se puede decidir el problema de la detención.

Reconocer soluciones parciales

Hay muchos programas que, para algunas entradas, devuelven una respuesta correcta al problema de detención, mientras que para otras entradas no devuelven ninguna respuesta. Sin embargo, el problema "dado el programa p , ¿es un solucionador de detención parcial" (en el sentido descrito) es al menos tan difícil como el problema de detención? Para ver esto, supongamos que existe un algoritmo PHSR ("reconocedor de resolución de detención parcial") para hacerlo. Luego se puede utilizar para resolver el problema de detención, de la siguiente manera: Para probar si el programa de entrada x se detiene en y , construya un programa p que en la entrada ( x , y ) informe verdadero y diverja en todas las demás entradas. Luego pruebe p con PHSR.

El argumento anterior es una reducción del problema de detención al reconocimiento de PHS y, de la misma manera, también se pueden reducir problemas más difíciles, como detener todas las entradas , lo que implica que el reconocimiento de PHS no solo es indecidible, sino que está más alto en la jerarquía aritmética , específicamente -completo. ${\displaystyle \Pi _{2}^{0}}$

Computación con pérdida

Una máquina de Turing con pérdidas es una máquina de Turing en la que parte de la cinta puede desaparecer de forma no determinista. El problema de la detención es decidible para una máquina de Turing con pérdidas pero recursiva no primitiva . ^[40]

máquinas oráculo

Una máquina con un oráculo para el problema de la detención puede determinar si determinadas máquinas de Turing se detendrán ante determinadas entradas, pero no pueden determinar, en general, si se detendrán máquinas equivalentes a ellas mismas.

Ver también

• castor ocupado
• Teorema de incompletitud de Gödel
• Controversia Brouwer-Hilbert
• Complejidad de Kolmogorov
• Problema de P versus NP
• Análisis de terminación
• Tiempo de ejecución en el peor de los casos

Notas

1. McConnell, Steve (2004). Código completo (2ª ed.). Educación Pearson. pag. 374.ISBN​ 9780735636972.
2. Huang, Han-Way (2009). HCS12 / 9S12: Introducción a la interfaz de software y hardware. pag. 197. ... si el programa se atasca en un determinado bucle, ... descubre qué está mal.
3. Simón, David E. (1999). Introducción al software integrado. pag. 253. Por lo tanto, para sistemas estrictos en tiempo real, es importante escribir subrutinas que siempre se ejecuten en la misma cantidad de tiempo o que tengan un peor caso claramente identificable.
4. Minsky 1967, pag. 24. cursiva en el original
5. Minsky 1967, pág. 25.
6. Hodges 1983, pág. 83; Comentario de Davis en Davis 1965, p. 108
7. Problemas absolutamente irresolubles y proposiciones relativamente indecidibles: relato de una anticipación , reimpreso en Davis 1965, págs. 340–433
8. Minsky 1967.
9. Reid 1996, págs. 188-189.
10. Hodges 1983, pág. 91.
11. Hodges 1983, pág. 91; Penrose 1989, pág. 34.
12. Reid 1996, pág. 198.
13. Reid 1996, pág. 199.
14. reimpreso en Davis 1965, p. 5ff
15. Iglesia 1936.
16. Una nota sobre el Entscheidungsproblem , reimpreso en Davis 1965, p. 110
17. Davis 1965, pág. 289 y sigs.
18. reimpreso en Davis 1965, p. 115
19. Lucas 2021.
20. Kleine 1952.
21. Rosser, "Exposición informal de las pruebas del teorema de Gödel y del teorema de Church", reimpreso en Davis 1965, p. 223
22. Kleene 1952, pág. 382.
23. de Davis a Copeland, 12 de diciembre de 2001, nota al pie 61 en Copeland 2004, p. 40
24. Copeland 2004, pág. 40.
25. Búsqueda textual de las obras completas de Turing: Good (1992), Gandy & Yates (2001), Ince (1992), Saunders (1992). De manera similar, Hodges (1983) no incluye la palabra "detención" ni las palabras "problema de detención" en su índice.
26. Davis 1958, págs. vii-viii.
27. Davis 1958, págs. 70–71.
28. Moore y Mertens 2011, págs. 236-237.
29. Strachey, C. (1 de enero de 1965). "Un programa imposible". La revista informática . 7 (4): 313. doi : 10.1093/comjnl/7.4.313 .
30. Luz del día, Edgar G. (16 de abril de 2021). "El problema de la detención y el enfoque teórico del lenguaje de la seguridad: elogios y críticas de un historiador técnico" (PDF) . Computabilidad . 10 (2): 141-158. doi :10.3233/COM-180217. S2CID  233329507 . Consultado el 26 de agosto de 2021 .
31. Penrose 1989, págs. 57–63.
32. Copeland 2004, pag. 15.
33. Hamkins, Joel David; Miasnikov, Alexei (1 de octubre de 2006). "El problema de la detención se puede decidir con un conjunto de probabilidad asintótica uno" (PDF) . Revista de lógica formal de Notre Dame . 47 (4). doi :10.1305/ndjfl/1168352664. S2CID  15005164 . Consultado el 5 de noviembre de 2022 .
34. Köhler, Sven; Schindelhauer, cristiano; Ziegler, Martín (2005). "Sobre la aproximación de los problemas de detención del mundo real". Fundamentos de la teoría de la computación . Apuntes de conferencias sobre informática. vol. 3623, págs. 454–466. doi :10.1007/11537311_40. ISBN 978-3-540-28193-1.
35. Lynch, Nancy (octubre de 1974). «Aproximaciones al problema de la detención» (PDF) . Revista de Ciencias de la Computación y de Sistemas . 9 (2): 143-150. doi :10.1016/S0022-0000(74)80003-6.
36. Bienvenu, Laurent; Desfontaines, Damián; Shen, Alexander (5 de abril de 2016). "Revisión de algoritmos genéricos para detener problemas y máquinas óptimas". Métodos lógicos en informática . 12 (2): 1. arXiv : 1505.00731 . doi :10.2168/LMCS-12(2:1)2016. S2CID  14763862.
37. Aaronson, Scott (21 de julio de 2011). "Teorema de Rosser mediante máquinas de Turing". Optimizado para Shtetl . Consultado el 2 de noviembre de 2022 .
38. por ejemplo, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft & Ullman 1979, Börger 1989
39. Borger 1989, pág. 121.
40. Abdulla y Jonsson 1996, pág. 92.

Referencias

• Iglesia, Alonso (1936). "Un problema irresoluble de la teoría de números elemental". Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi :10.2307/2371045. JSTOR  2371045.
• Copeland, B. Jack, ed. (2004). El Turing esencial: escritos fundamentales sobre informática, lógica, filosofía, inteligencia artificial y vida artificial, además de los secretos de Enigma . Oxford: Prensa de Clarendon. ISBN 0-19-825079-7.
• Davis, Martín (1965). Los indecidibles, artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press.. El artículo de Turing ocupa el tercer lugar en este volumen. Los artículos incluyen los de Godel, Church, Rosser, Kleene y Post.
• Davis, Martín (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill..
• Rogers, Hartley (Jr.) (1957). Teoría de funciones recursivas y computabilidad efectiva. Instituto de Tecnología de Massachusetts.
• Kleene, Stephen Cole (1952). Introducción a las metamatemáticas . Holanda del Norte. ISBN 0923891579.. El capítulo XIII ("Funciones computables") incluye una discusión sobre la irresolublebilidad del problema de detención de las máquinas de Turing. Alejándose de la terminología de Turing sobre máquinas sin círculos que no se detienen, Kleene se refiere en cambio a máquinas que "se detienen", es decir, se detienen.
• Lucas, Salvador (junio de 2021). "Los orígenes del problema de la detención". Revista de métodos lógicos y algebraicos en programación . 121 : 100687. doi : 10.1016/j.jlamp.2021.100687. hdl : 10251/189460 . S2CID  235396831.
• Minsky, Marvin (1967). Computación: máquinas finitas e infinitas . Englewood Cliffs, Nueva Jersey: Prentice-Hall. ISBN 0131655639.. Consulte el capítulo 8, Sección 8.2 "Insolubilidad del problema de detención".
• Moore, Cristopher ; Mertens, Stephan (2011). La naturaleza de la computación. Prensa de la Universidad de Oxford. doi :10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2.
• Reid, Constanza (1996). Hilberto . Nueva York: Copérnico. ISBN 0387946748.. Publicado por primera vez en 1970, una fascinante historia de las matemáticas y la física alemanas desde la década de 1880 hasta la de 1930. En sus páginas aparecen cientos de nombres familiares para matemáticos, físicos e ingenieros. Quizás empañado por referencias no abiertas y pocas notas a pie de página: Reid afirma que sus fuentes fueron numerosas entrevistas con quienes conocieron personalmente a Hilbert, y las cartas y artículos de Hilbert.
• Sipser, Michael (2006). "Sección 4.2: El problema de la detención" . Introducción a la Teoría de la Computación (Segunda ed.). Publicación PWS. págs. 173–182. ISBN 0-534-94728-X.
• Turing, AM (1937). "Sobre números computables, con una aplicación al problema de Entscheidungs". Actas de la Sociedad Matemática de Londres . Wiley. T2-42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. ISSN  0024-6115. S2CID  73712.^{[ enlace muerto permanente ]} , Turing, AM (1938). "Sobre números computables, con una aplicación al Entscheidungsproblem. Una corrección". Actas de la Sociedad Matemática de Londres . Wiley. T2-43 (1): 544–546. doi :10.1112/plms/s2-43.6.544. ISSN  0024-6115.^{[ enlace muerto permanente ]} Este es el documento trascendental en el que Turing define las máquinas de Turing , formula el problema de la detención y muestra que (al igual que el Entscheidungsproblem ) no tiene solución.
• Penrose, Roger (1989). La nueva mente del emperador: sobre las computadoras, las mentes y las leyes de la física (reimpresión corregida de 1990, edición). Oxford: Prensa de la Universidad de Oxford. ISBN 0192861980.. Cfr. Capítulo 2, "Algoritmos y máquinas de Turing". Una presentación demasiado complicada (consulte el artículo de Davis para obtener un modelo mejor), pero una presentación exhaustiva de las máquinas de Turing y el problema de la detención, y el cálculo Lambda de Church.
• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Addison-Wesley. ISBN 81-7808-347-7.. Consulte el Capítulo 7 "Máquinas de Turing". Un libro centrado en la interpretación automática de "lenguajes", NP-Completitud, etc.
• Hodges, Andrés (1983). Alan Turing: el enigma . Nueva York: Simon y Schuster. ISBN 0-671-49207-1.. Cf. Capítulo "El Espíritu de la Verdad" para una historia que conduce a su prueba y una discusión sobre ella.
• Börger, Egon (1989). Computabilidad, complejidad, lógica . Ámsterdam: Holanda Septentrional. ISBN 008088704X.
• Abdulla, Parosh Aziz; Jonsson, Bengt (1996). "Verificación de programas con canales no confiables". Información y Computación . 127 (2): 91-101. doi : 10.1006/inco.1996.0053 .
• Obras completas de AM Turing
  • Bien, Irving John, ed. (1992). Matemática pura. Holanda del Norte. ISBN 978-0-444-88059-8.
  • Gandy, RO; Yates, CEM, eds. (5 de diciembre de 2001). Lógica Matemática. Elsevier. ISBN 978-0-08-053592-0.
  • Ince, DC, ed. (1992). Inteligencia mecánica. Holanda del Norte. ISBN 978-0-444-88058-1.
  • Saunders, PT, ed. (26 de noviembre de 1992). Morfogénesis. Elsevier. ISBN 978-0-08-093405-1.

Otras lecturas

• c2: Problema de detención
• Alfred North Whitehead y Bertrand Russell , Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: el problema de las paradojas, los autores discuten el problema de que un conjunto no sea un objeto en ninguna de sus "funciones determinantes", en en particular "Introducción, Capítulo 1 p. 24 "... dificultades que surgen en la lógica formal", y Capítulo 2.I. "El principio del círculo vicioso" p. 37ff, y Capítulo 2.VIII. "Las Contradicciones " pág. 60 y siguientes.
• Martin Davis , "What is a computation", en Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Un pequeño artículo maravilloso, quizás el mejor jamás escrito sobre las máquinas de Turing para quienes no son especialistas. Davis reduce la máquina de Turing a un modelo mucho más simple basado en el modelo de cálculo de Post. Analiza la prueba de Chaitin . Incluye pequeñas biografías de Emil Post , Julia Robinson .
• Edward Beltrami, ¿Qué es el azar? Azar y orden en las matemáticas y la vida , Copernicus: Springer-Verlag, Nueva York, 1999. Lectura agradable y amable para los no especialistas con inclinaciones matemáticas, que pone cosas más difíciles al final. Tiene un modelo de máquina de Turing. Analiza las contribuciones de Chaitin .
• Ernest Nagel y James R. Newman , Godel's Proof , New York University Press, 1958. Magnífico escrito sobre un tema muy difícil. Para los no especialistas con inclinaciones matemáticas. Analiza la prueba de Gentzen en las páginas 96–97 y notas a pie de página. Los apéndices analizan brevemente los axiomas de Peano e introducen suavemente a los lectores en la lógica formal.
• Daras, Nicolás J.; Rassias, Temístocles M. (2018). Análisis y matemáticas discretas modernas: con aplicaciones en criptografía, sistemas de información y modelado . Cham, Suiza. ISBN 978-3319743240.{{cite book}}: CS1 maint: location missing publisher (link). La Sección 1 del Capítulo 3 contiene una descripción de calidad del problema de detención, una prueba por contradicción y una representación gráfica útil del problema de detención.
• Taylor Booth , Teoría de máquinas secuenciales y autómatas , Wiley, Nueva York, 1967. Cf. Capítulo 9, Máquinas de Turing. Libro difícil, destinado a ingenieros eléctricos y especialistas técnicos. Analiza la recursividad, la recursividad parcial con referencia a las máquinas de Turing, y el problema de detención. Tiene un modelo de la Máquina de Turing . Las referencias al final del Capítulo 9 recogen la mayoría de los libros más antiguos (es decir, de 1952 a 1967, incluidos los autores Martin Davis, FC Hennie, H. Hermes, SC Kleene, M. Minsky, T. Rado) y varios artículos técnicos. Consulte la nota en Programas Busy-Beaver.
• Los programas Busy Beaver se describen en Scientific American, agosto de 1984, también marzo de 1985, pág. 23. Una referencia en Booth los atribuye a Rado, T. (1962), On non-comutablefunctions, Bell Systems Tech. J. 41. Booth también define el problema del castor ocupado de Rado en los problemas 3, 4, 5, 6 del capítulo 9, p. 396.
• David Bolter, El hombre de Turing: la cultura occidental en la era de la informática , The University of North Carolina Press, Chapel Hill, 1984. Para el lector general. Puede estar anticuado. Tiene otro modelo (muy simple) de Máquina de Turing.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, Sobre la aproximación de los problemas de detención del mundo real , páginas 454-466 (2005) ISBN 3540281932 Springer Lecture Notes in Computer Science volumen 3623: La indecidibilidad del problema de detención significa que no todos los casos se pueden responder correctamente ; ¿Pero tal vez "algunos", "muchos" o "la mayoría" puedan hacerlo? Por un lado, la respuesta constante "sí" será infinitamente correcta y también infinitamente incorrecta. Para que la pregunta sea razonable, considere la densidad de casos que pueden resolverse. Esto depende significativamente del sistema de programación considerado. 
• Limitaciones lógicas de la ética de las máquinas, con consecuencias para las armas autónomas letales: artículo analizado en: ¿El problema de la detención significa que no habrá robots morales?

enlaces externos

• Descubriendo al espía del bucle: una prueba poética de la indecidibilidad del problema de la detención
• película animada: una animación que explica la prueba de la indecidibilidad del problema de la detención
• Una demostración de dos minutos del segundo teorema más importante del segundo milenio: una demostración en sólo 13 líneas