Problema de parada

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

En 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 informático arbitrario y una entrada, si el programa terminará de ejecutarse o continuará ejecutándose para siempre. El problema de la detención es indecidible , lo que significa que no existe un algoritmo general que resuelva el problema de la detención para todos los pares programa-entrada posibles. El problema surge a menudo en los debates sobre computabilidad , ya que demuestra que algunas funciones son matemáticamente definibles pero no computables .

Una parte clave del enunciado formal del problema es una definición matemática de un ordenador y un programa, normalmente 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 existe un programa "patológico" g para el cual f realiza una determinación incorrecta. Específicamente, g es el programa que, cuando se lo llama con alguna entrada, pasa su propia fuente y su entrada a f y hace lo opuesto de lo que f predice que g hará. El comportamiento de f en g muestra indecidibilidad ya que significa que ningún programa f resolverá el problema de la detención en todos los casos posibles.

Fondo

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

Por ejemplo, en pseudocódigo , el programa

while (true) continue

no se detiene, sino que continúa eternamente en un bucle infinito . Por otro lado, el programa

print "Hello, world!"

se detiene.

Si bien decidir si estos programas se detienen es simple, los programas más complejos resultan problemáticos. Una forma de abordar el problema podría ser ejecutar el programa durante una cierta cantidad de pasos y verificar si se detiene. Sin embargo, mientras el programa esté ejecutándose, no se sabe si finalmente 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 dados, el programa se detiene cuando se ejecuta con esa entrada. La esencia de la prueba de Turing es que cualquier algoritmo de este tipo puede generar resultados contradictorios y, por lo tanto, no puede ser correcto.

Consecuencias de programación

Algunos bucles infinitos pueden ser bastante útiles. Por ejemplo, los bucles de eventos suelen codificarse como bucles infinitos. ^[1] Sin embargo, la mayoría de las subrutinas están pensadas para finalizar. ^[2] En particular, en la informática en tiempo real , los programadores intentan escribir subrutinas que no solo estén garantizadas para finalizar, sino que también estén garantizadas para finalizar 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 facilita demostrar que las subrutinas resultantes finalizan antes de la fecha límite establecida. ^{[ cita requerida ]}

En otras ocasiones, estos programadores aplican la regla del mínimo poder : utilizan deliberadamente un lenguaje informático que no es del todo Turing-completo. Con frecuencia, se trata de lenguajes que garantizan que todas las subrutinas finalicen, como Coq . ^{[ cita requerida ]}

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 y entradas. Un programa en particular se detiene en una entrada dada o no se detiene. Consideremos 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 pueda saber cuál. Sin embargo, ninguno de los dos algoritmos resuelve el problema de la detención en general.

Existen 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 ha planteado; no responde con éxito a "no se detiene" para 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 detenerse o repetir una configuración previa: ^[4]

... cualquier máquina de estados finitos, si se deja que actúe por sí sola, acabará cayendo en un patrón repetitivo perfectamente periódico . La duración de este patrón repetitivo no puede superar el número de estados internos de la máquina...

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

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

Aunque una máquina puede ser finita, y 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, algunas o todas las secuencias posibles de decisiones no deterministas, enumerando estados después de cada decisión posible.

Historia

En abril de 1936, Alonzo Church publicó su demostración de la indecidibilidad de un problema de cálculo lambda . La demostración 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 parada que surgió en la década de 1950.

Cronología

• 1900 : David Hilbert plantea sus "23 cuestiones" (hoy conocidas como problemas de Hilbert ) en el Segundo Congreso Internacional de Matemáticos en París. "De éstas, la segunda era la de demostrar la consistencia 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 para sistemas de etiquetas , considerándolo como un candidato a la irresolubilidad. ^[7] Su irresolubilidad 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: a saber: #1: ¿Eran las matemáticas completas ? #2: ¿Eran las matemáticas consistentes ? #3: ¿Eran las matemáticas decidibles ? ^[10] La tercera pregunta se conoce como el 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 lidiar constructivamente con el problema... El propio Gödel sintió -y expresó el pensamiento en su artículo- que su trabajo no contradecía el punto de vista formalista de Hilbert" ( 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 insoluble de la teoría elemental de números", en el que propone que la noción intuitiva de una función efectivamente calculable puede formalizarse mediante las funciones recursivas generales o, equivalentemente, mediante las 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 es efectivamente calculable. ( 19 de abril de 1935 ) ^[15]
• 1936 : Church publica la primera prueba de que el problema de Entscheidung es irresoluble, utilizando una noción de cálculo mediante funciones recursivas . ( 1936 ) ^[16]
• 7 de octubre de 1936 : Se recibe el artículo de Emil Post "Procesos combinatorios finitos. Formulación I". Post añade a su "proceso" una instrucción "(C) Detener". Denomina a este proceso "tipo 1... si el proceso que determina termina para cada problema específico". ( 07-10-1936 ) ^[17]
• Mayo de 1936  – enero de 1937 : El artículo de Alan Turing, On Computable Numbers With an Application to the Entscheidungsproblem, se publica en mayo de 1936 y llega a la imprenta en enero de 1937. ^[18] Turing demuestra que tres problemas son indecidibles: el problema de la "satisfacción", el problema de la "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 se demostraron irresolubles". ^{[20] [ página necesaria ]} ( 1936-05 ) ( 1937-01 )
• 1939 : J. Barkley Rosser observa la equivalencia esencial del "método efectivo" 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... procedimiento que necesariamente termina y de tal manera que a partir del resultado podemos 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 imposibilidad de resolver el 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 hay un algoritmo para decidir si una máquina dada, cuando se inicia desde una 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 de este término. ( 1952 ) ^[23]

Origen del problema de la parada

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

"[...] queremos determinar si [una máquina de Turing] Z, si se la coloca en un estado inicial dado, acabará deteniéndose. 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 para una máquina de Turing simple Z con respecto a un símbolo S _i ".

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, al arrancar desde una situación determinada, acabará deteniéndose.

El problema de la detención es equivalente de Turing tanto al problema de impresión de Davis ("¿acaso 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 ("¿acaso una máquina de Turing que parte de una cinta en blanco imprime alguna vez un símbolo dado?"). Sin embargo, la equivalencia de Turing es bastante vaga y no significa que los dos problemas sean el mismo. Hay máquinas que imprimen pero no se detienen, y máquinas que se detienen pero no imprimen. Los problemas de impresión y de 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 se podría mencionar que la irresolubilidad de esencialmente estos problemas fue obtenida por primera vez por Turing.

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 en modo alguno específico de ellas; se aplica igualmente a cualquier otro modelo de computación que sea equivalente en su potencia computacional a las máquinas de Turing, como los algoritmos de Markov , el cálculo lambda , los sistemas Post , las máquinas de registros 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 una asignación 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ándolas como números en un sistema de numeración n -ario .

Representación como un 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 detención

K = {( i , 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]

Existen muchas formulaciones equivalentes del problema de la detención; cualquier conjunto cuyo grado de Turing sea igual al del problema de la detención es una de esas formulaciones. Algunos ejemplos de estos conjuntos son:

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

Concepto de prueba

Christopher Strachey describió una prueba por contradicción de que el problema de la detención no es solucionable. ^{[29] [30]} La prueba se desarrolla de la siguiente manera: supongamos que existe una función computable total halts(f) que devuelve verdadero si la subrutina f se detiene (cuando se ejecuta sin entradas) y devuelve falso en caso contrario. Ahora consideremos 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 falso, entonces g se detendrá, porque no llamará a loop_forever ; esto también es una contradicción. En general, g hace lo opuesto de lo que halts dice que g debe hacer, por lo que halts(g) no puede devolver un valor de verdad que sea consistente con si g se detiene. Por lo tanto, la suposición inicial de que halts es una función computable total debe ser falsa.

Bosquejo de una prueba rigurosa

El concepto anterior muestra el método general de la prueba, pero la función computable halts 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 demostrar 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 "halts") 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 Turing-completo fijo de computación.

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 por 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 indefinido),
• 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 bucle indefinido            

Como g es parcialmente computable, debe haber un programa e que calcule g , suponiendo que el modelo de cálculo es Turing-completo. Este programa es uno de todos los programas en los que está definida la función de detención 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 desprende que debe cumplirse exactamente uno de los dos casos siguientes:

• f ( e , e ) = 0 y por lo tanto g ( e ) = 0. En este caso, el programa e se detiene en la entrada e , por lo que h ( e , e ) = 1.
• f ( e , e ) ≠ 0 y por lo tanto 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 . Como f es una función computable total arbitraria con dos argumentos, todas esas funciones deben ser diferentes 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 . Como se supone que f es una función computable total, cualquier elemento de la matriz se puede calcular utilizando f . La construcción de la función g se puede visualizar utilizando 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 que corresponde a g en sí. 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, contradiciendo f ( e,e ) = 1. De manera similar, si g ( e ) no está definida, entonces la función de detención f ( e,e ) = 0, lo que lleva a g ( e ) = 0 bajo la construcción de g . Esto contradice el supuesto de que g ( e ) no está definida. En ambos casos surge una contradicción. Por lo tanto, cualquier función computable arbitraria f no puede ser la función de detención 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 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 números naturales. Si un algoritmo pudiera encontrar el valor de verdad de cada afirmación sobre números naturales, ciertamente podría encontrar el valor de verdad de esta; 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 es irresoluble. 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 puede producir un resultado, y por lo tanto 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 ni 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 se puede decidir mediante un algoritmo que simplemente informa "verdadero". Además, este teorema solo se cumple 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 implementada por 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 un 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 ser resueltos por una máquina de Turing, la tesis de Church-Turing limita lo que puede ser logrado por cualquier máquina que implemente métodos efectivos . Sin embargo, no todas las máquinas concebibles para la imaginación humana están sujetas a la tesis de Church-Turing (por ejemplo, las máquinas oráculo ). Es una pregunta 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 cualquier proceso hipotético de ese tipo podría ser aprovechado de manera útil en la forma de una máquina calculadora (una hipercomputadora ) que pudiera resolver el problema de la detención para una máquina de Turing, entre otras cosas. También es una pregunta abierta si tales procesos físicos desconocidos están involucrados en el funcionamiento del cerebro humano , y si los humanos pueden resolver el problema de la detención. ^[32]

Aproximaciones

La prueba de Turing muestra que no puede haber un método mecánico general (es decir, una máquina de Turing o un programa en algún modelo equivalente de computación ) para determinar si los algoritmos se detienen. Sin embargo, cada instancia individual del problema de la detención tiene una respuesta definitiva, que puede o no ser computable en la práctica. Dado un algoritmo y una entrada específicos, a menudo se puede demostrar que se detiene o no, y de hecho los científicos informáticos a menudo hacen exactamente 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, que con frecuencia tienen é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 las heurísticas de problemas de detención, en particular la fracción de programas de un tamaño determinado que pueden clasificarse correctamente mediante un algoritmo recursivo. Estos resultados no dan cifras precisas porque las fracciones no se pueden calcular 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 la clasificación de programas por su número de estados y el uso de un modelo específico de "cinta semi-infinita de Turing" de cálculo que comete errores (sin detenerse) si el programa se ejecuta por 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án debido a un error. Por lo tanto, un detalle aparentemente irrelevante, a saber, el tratamiento de los programas con errores, puede resultar ser 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 tales 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 solo si para todo , existe un 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 densa, 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 , hay una función recursiva total 1-1 y una constante tal que para todo , 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 sobre 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 para cada otra máquina V existe una función computable total 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 V -programa de longitud n genera x , entonces existe un U -programa de longitud máxima que genera 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 una de ellas, consideramos la fracción de errores entre todos los programas de tamaño métrico como máximo , contando cada programa para el que no termina, produce una respuesta de "no sé" o produce una respuesta incorrecta, es decir, se detiene y genera , o no se detiene y genera . El comportamiento puede describirse 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 , . En palabras, cualquier algoritmo tiene una tasa de error mínima positiva, incluso cuando el tamaño del problema se vuelve extremadamente grande. ${\displaystyle A}$ ${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$
• Existe tal que para cada algoritmo , . En palabras, hay una tasa de error positiva para la cual cualquier algoritmo tendrá un rendimiento peor que esa tasa de error arbitrariamente a menudo, incluso si el tamaño del problema crece indefinidamente. ${\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}$En otras palabras, existe una secuencia de algoritmos tal que la tasa de error se acerca arbitrariamente a cero para una secuencia específica de tamaños crecientes. Sin embargo, este resultado permite secuencias de algoritmos que producen respuestas incorrectas.
• Si consideramos sólo algoritmos "honestos" que pueden no estar definidos pero nunca producir respuestas incorrectas, entonces, dependiendo de la métrica, puede ser o no 0. En particular, es 0 para máquinas universales con total izquierdo, pero para 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 . Hay nuevas variedades de programas que aparecen con poca frecuencia y que vienen en "bloques" arbitrariamente grandes, y una fracción de repeticiones en constante crecimiento. Si los bloques de nuevas variedades están completamente incluidos, la tasa de error es al menos , pero entre bloques la fracción de repeticiones correctamente categorizadas puede ser arbitrariamente alta. En particular, una heurística de "conteo" 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 solo afirmaciones verdaderas sobre los números naturales. Dado que la solidez implica consistencia , 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 solo se ocupa de la cuestión de si es posible encontrarlo mediante una demostración matemática .

La forma más débil del teorema puede demostrarse 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 lógicos de primer orden verdaderos sobre los números naturales . Entonces podemos construir un algoritmo que enumera todos estos enunciados. Esto significa que hay un algoritmo N ( n ) que, dado un número natural n , calcula un enunciado lógico de primer orden verdadero sobre los números naturales, y que para todos los enunciados verdaderos, hay al menos un n tal que N ( n ) produce ese enunciado. Ahora supongamos que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que este enunciado puede expresarse con un enunciado lógico de primer orden, digamos H ( a , i ). Como la axiomatización es completa, se deduce que o bien hay un n tal que N ( n ) = H ( a , i ) o bien hay un n ′ tal que N ( n ′ ) = ¬ H ( a , i ). Así que si iteramos sobre todos los n hasta que encontremos 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 la detención. Como sabemos que no puede haber tal algoritmo, se deduce que la suposición de que existe una axiomatización consistente y completa de todas las afirmaciones lógicas de primer orden verdaderas 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 detención. ^[38] Normalmente, 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 lo 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 se pueden reducir al problema de detención estándar. Los dos ejemplos siguientes son comunes. ${\displaystyle \Sigma _{1}^{0}}$

Detención en todas las entradas

El problema de detención universal , también conocido (en la teoría de la recursión ) como totalidad , es el problema de determinar si un programa informático 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 solo es indecidible, como lo es el problema de la detención, sino que es altamente indecidible. En términos de la 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.

Reconociendo 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 solucionador de detención parcial") para hacer eso. 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, problemas más difíciles como la detención en todas las entradas también se pueden reducir, lo que implica que el reconocimiento de PHS no solo es indecidible, sino que está más arriba en la jerarquía aritmética , específicamente es -completo. ${\displaystyle \Pi _{2}^{0}}$

Computación con pérdida

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

Máquinas Oracle

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 puede determinar, en general, si máquinas equivalentes a ella se detendrán.

Véase también

• Castor ocupado
• Teorema de incompletitud de Gödel
• La controversia entre Brouwer y Hilbert
• Complejidad de Kolmogorov
• Problema 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.). Pearson Education. pág. 374. ISBN 9780735636972.
2. Huang, Han-Way (2009). HCS12/9S12: Introducción a la interconexión de software y hardware. p. 197. ... si el programa se queda atascado en un bucle determinado, ... averiguar qué es lo que está mal.
3. Simon, David E. (1999). An Embedded Software Primer. p. 253. Por lo tanto, para los sistemas de tiempo real estricto, 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, p. 24. cursiva en el original.
5. Minsky 1967, pág. 25.
6. Hodges 1983, pág. 83; comentario de Davis en Davis 1965, pág. 108
7. Problemas absolutamente irresolubles y proposiciones relativamente indecidibles: relato de una anticipación , reimpreso en Davis 1965, pp. 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ág. 5ff
15. Iglesia 1936.
16. Una nota sobre el problema de la entscheidung , reimpresa en Davis 1965, pág. 110
17. Davis 1965, pág. 289 y siguientes.
18. reimpreso en Davis 1965, pág. 115
19. Lucas 2021.
20. Kleene 1952.
21. Rosser, "Exposición informal de las pruebas del teorema de Gödel y del teorema de Church", reimpreso en Davis 1965, pág. 223
22. Kleene 1952, pág. 382.
23. Carta de Davis a Copeland, 12 de diciembre de 2001, nota 61 en Copeland 2004, pág. 40
24. Copeland 2004, pág. 40.
25. Búsqueda textual en 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". The Computer Journal . 7 (4): 313. doi : 10.1093/comjnl/7.4.313 .
30. Daylight, 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, pág. 15.
33. Hamkins, Joel David; Miasnikov, Alexei (1 de octubre de 2006). "El problema de la detención es decidible en un conjunto de probabilidad asintótica uno" (PDF) . Notre Dame Journal of Formal Logic . 47 (4). doi :10.1305/ndjfl/1168352664. S2CID  15005164 . Consultado el 5 de noviembre de 2022 .
34. Köhler, Sven; Schindelhauer, Christian; Ziegler, Martin (2005). "Sobre la aproximación de problemas de detención en el mundo real". Fundamentos de la teoría de la computación . Apuntes de clase en 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. Bienvenido, Laurent; Desfontaines, Damien; Shen, Alexander (5 de abril de 2016). "Algoritmos genéricos para el problema de detención y máquinas óptimas revisitadas". 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 a través de máquinas de Turing". Shtetl-Optimized . Consultado el 2 de noviembre de 2022 .
38. por ejemplo, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft y Ullman 1979, Börger 1989
39. Börger 1989, pág. 121.
40. Abdulla y Jonsson 1996, pág. 92.

Referencias

• Church, Alonzo (1936). "Un problema irresoluble de la teoría elemental de números". American Journal of Mathematics . 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: Clarendon Press. ISBN 0-19-825079-7.
• Davis, Martin (1965). Lo indecidible. Documentos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press.El artículo de Turing es el número 3 de este volumen. Entre los artículos se incluyen los de Godel, Church, Rosser, Kleene y Post.
• Davis, Martin (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill..
• Rogers, Hartley (Jr.) (1957). Teoría de funciones recursivas y computabilidad efectiva. Instituto Tecnológico de Massachusetts.
• Kleene, Stephen Cole (1952). Introducción a las metamatemáticas . Holanda Septentrional. ISBN 0923891579.El capítulo XIII ("Funciones computables") incluye un análisis de la imposibilidad de resolver el problema de la detención para las máquinas de Turing. En un cambio con respecto a la terminología de Turing de máquinas sin detención sin círculo, Kleene se refiere en cambio a máquinas que "se detienen", es decir, que 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, NJ: Prentice-Hall. ISBN 0131655639.. Véase el capítulo 8, Sección 8.2 "Insolubilidad del problema de la detención".
• Moore, Cristopher ; Mertens, Stephan (2011). La naturaleza de la computación. Oxford University Press. doi :10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2.
• Reid, Constance (1996). Hilbert . Nueva York: Copernicus. ISBN 0387946748.Publicada 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. Tal vez se vea empañada por la falta de referencias explícitas y las pocas notas a pie de página: Reid afirma que sus fuentes fueron numerosas entrevistas con personas que conocieron personalmente a Hilbert, y sus cartas y artículos.
• Sipser, Michael (2006). "Sección 4.2: El problema de la detención" . Introducción a la teoría de la computación (segunda edición). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X.
• Turing, AM (1937). "Sobre números computables, con una aplicación al problema de Entscheidung". Actas de la London Mathematical Society . s2-42 (1). Wiley: 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 problema de Entscheidung. Una corrección". Actas de la London Mathematical Society . s2-43 (1). Wiley: 544–546. doi :10.1112/plms/s2-43.6.544. ISSN  0024-6115.^{[ enlace muerto permanente ]} Este es el artículo trascendental en el que Turing define las máquinas de Turing , formula el problema de detención y demuestra que éste (así como el Entscheidungsproblem ) es irresoluble.
• Penrose, Roger (1989). La nueva mente del emperador: sobre computadoras, mentes y leyes de la física (edición corregida de 1990). Oxford: Oxford University Press. ISBN 0192861980.. Véase el capítulo 2, "Algoritmos y máquinas de Turing". Una presentación demasiado complicada (véase el artículo de Davis para un modelo mejor), pero una presentación completa 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 de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 81-7808-347-7.Véase el capítulo 7, "Máquinas de Turing". Un libro centrado en la interpretación de "lenguajes" por parte de las máquinas, la NP-Completitud, etc.
• Hodges, Andrew (1983). Alan Turing: el enigma . Nueva York: Simon and Schuster. ISBN 0-671-49207-1.. Cf. Capítulo "El Espíritu de la Verdad" para una historia que conduce a su prueba y un análisis de la misma.
• 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
  • Good, Irving John, ed. (1992). Matemáticas puras. 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.

Lectura adicional

• c2:Problema de detención
• Alfred North Whitehead y Bertrand Russell , Principia Mathematica to *56, Cambridge at the University Press, 1962. Con respecto al problema de las paradojas, los autores discuten el problema de que un conjunto no sea un objeto en ninguna de sus "funciones determinantes", en particular "Introducción, Cap. 1 p. 24 "...dificultades que surgen en la lógica formal", y Cap. 2.I. "El principio del círculo vicioso" p. 37ff, y Cap. 2.VIII. "Las contradicciones" p. 60ff.
• Martin Davis , "What is a computation", en Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Un artículo breve y maravilloso, quizás el mejor que se haya escrito jamás sobre las máquinas de Turing para los no 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 y Julia Robinson .
• Edward Beltrami, ¿Qué es el azar? El azar y el orden en las matemáticas y en la vida , Copernicus: Springer-Verlag, Nueva York, 1999. Una lectura agradable y amena para los no especialistas con inclinaciones matemáticas; deja las cosas más difíciles al final. Incluye 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. Un texto maravilloso 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 en las notas a pie de página. Los apéndices analizan brevemente los axiomas de Peano y presentan con delicadeza a los lectores la lógica formal.
• Daras, Nicholas J.; Rassias, Themistocles M. (2018). Matemática discreta moderna y análisis: con aplicaciones en criptografía, sistemas de información y modelado . Cham, Suiza. ISBN 978-3319743240.{{cite book}}: CS1 maint: location missing publisher (link)El Capítulo 3 Sección 1 contiene una descripción de calidad del problema de la parada, una prueba por contradicción y una representación gráfica útil del problema de la parada.
• Taylor Booth , Sequential Machines and Automata Theory , Wiley, Nueva York, 1967. Véase el capítulo 9, Turing Machines. Libro difícil, destinado a ingenieros eléctricos y especialistas técnicos. Analiza la recursión, la recursión parcial con referencia a las máquinas de Turing y el problema de la detención. Contiene un modelo de máquina de Turing . Las referencias al final del capítulo 9 abarcan 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. Véase la nota en Busy-Beaver Programs.
• 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-computable functions, Bell Systems Tech. J. 41. Booth también define el problema Busy Beaver de Rado en los problemas 3, 4, 5, 6 del capítulo 9, pág. 396.
• David Bolter, Turing's Man: Western Culture in the Computer Age , The University of North Carolina Press, Chapel Hill, 1984. Para el lector general. Puede que esté desactualizado. Contiene otro modelo (muy simple) de máquina de Turing.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, On approximating real-world halting problems , pp.454-466 (2005) ISBN 3540281932 Springer Lecture Notes in Computer Science volumen 3623: La indecidibilidad del problema de la detención significa que no todas las instancias pueden responderse correctamente; pero tal vez "algunas", "muchas" o "la mayoría" sí. Por un lado, la respuesta constante "sí" será correcta infinitamente a menudo, y errónea también infinitamente a menudo. Para que la pregunta sea razonable, considere la densidad de las instancias que se pueden resolver. Esto resulta depender significativamente del sistema de programación en consideración. 
• Limitaciones lógicas a 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 hay 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 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
• haltingproblem.org - vídeos y documentos populares que explican el problema de la detención.