stringtranslate.com

Problema de parada

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 resultar muy ú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á por caer 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

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 ( ix ) 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:

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]

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 :

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

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 deduce que debe cumplirse exactamente uno de los dos casos siguientes:

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 afirma 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.

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]

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]

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]DOES_NOT_HALTHALTS

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]

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.

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]

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, también se pueden reducir problemas más difíciles como la detención en todas las entradas , 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.

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

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. ^Ab 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. ^abcdef 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. ^ desde 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. ^ desde 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. ^ abc 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. ^ abc 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

Lectura adicional

Enlaces externos