Estaba leyendo otra explicación del problema de detención, y me hizo pensar que todos los problemas que he visto como ejemplos involucran secuencias infinitas. Pero nunca uso secuencias infinitas en mis programas, toman demasiado tiempo. Todas las aplicaciones del mundo real tienen límites inferiores y superiores. Incluso los reales no son realmente reales: son aproximaciones almacenadas como 32/64 bits, etc.
Entonces la pregunta es, ¿hay un subconjunto de programas que se puedan determinar si se detienen? ¿Es lo suficientemente bueno para la mayoría de los programas? ¿Puedo construir un conjunto de construcciones de lenguaje que pueda determinar la 'capacidad de detención' de un programa? Estoy seguro de que esto se ha estudiado en algún lugar antes, por lo que cualquier indicador sería apreciado. El lenguaje no estaría completo, pero ¿existe algo así como casi completo que sea lo suficientemente bueno?
Naturalmente, tal construcción tendría que excluir la recursión y los bucles while ilimitados, pero puedo escribir un programa sin esos fácilmente.
La lectura de la entrada estándar como ejemplo tendría que estar limitada, pero eso es bastante fácil: limitaré mi entrada a 10,000,000 de caracteres, etc., dependiendo del dominio del problema.
tia
[Actualizar]
Después de leer los comentarios y las respuestas, tal vez debería repetir mi pregunta.
Para un programa dado en el que todas las entradas están limitadas, ¿puede determinar si el programa se detiene? Si es así, ¿cuáles son las restricciones del idioma y cuáles son los límites del conjunto de entrada? El conjunto máximo de estas construcciones determinaría un lenguaje que puede deducirse para detenerse o no. ¿Hay algún estudio que se haya hecho sobre esto?
[Actualización 2]
Aquí está la respuesta, es sí, desde 1967 en http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf
Minsky ya argumentó en 1967 que el problema de la detención puede resolverse al menos teóricamente para los sistemas de estado finito [4]: “... cualquier máquina de estado finito, si se deja completamente sola, eventualmente caerá en un período perfectamente periódico patrón repetitivo La duración de este patrón repetitivo no puede exceder el número de estados internos de la máquina ... "
(y si te apegas a máquinas de turing finitas, entonces puedes construir un oráculo)
fuente
Respuestas:
El problema no está en la entrada (obviamente, con una entrada ilimitada, puede tener un tiempo de ejecución ilimitado solo para leer la entrada), está en el número de estados internos.
Cuando el número de estados internos está limitado, teóricamente puede resolver el problema de detención en todos los casos (solo emúlelo hasta que llegue a detenerse o la repetición de un estado), cuando no lo es, hay casos en los que no se puede resolver . Pero incluso si el número de estados internos está limitado en la práctica, también es tan grande que los métodos que dependen del límite del número de estados internos son inútiles para probar la finalización de cualquiera de los programas más triviales.
Hay formas más prácticas de verificar la finalización de los programas. Por ejemplo, expréselos en un lenguaje de programación que no tenga recursividad ni goto y cuyas estructuras de bucle tengan un límite en el número de iteraciones que debe especificarse en la entrada del bucle. (Tenga en cuenta que el límite no tiene que estar realmente relacionado con el número efectivo de iteraciones, una forma estándar de probar la terminación de un ciclo es tener una función que demuestre que está disminuyendo estrictamente de una iteración a otra y su condición de entrada asegúrese de que es positivo, podría poner la primera evaluación como su límite).
fuente
En primer lugar, considere lo que sucedería si tuviéramos un detector de detención. Sabemos por el argumento diagonal que existe al menos un programa que causaría que un detector de detención nunca se detenga o dé una respuesta incorrecta. Pero ese es un programa extraño e improbable.
Sin embargo, hay otro argumento de que un detector de detención es imposible, y ese es el argumento más intuitivo de que un detector de detención sería mágico. Suponga que quiere saber si el último teorema de Fermat es verdadero o falso. Simplemente escribe un programa que se detiene si es verdadero y se ejecuta para siempre si es falso, y luego ejecuta el detector de detención en él. No ejecuta el programa , simplemente ejecuta el detector de detención en el programa . Un detector de detención nos permitiría resolver de inmediato una gran cantidad de problemas abiertos en teoría de números simplemente escribiendo programas.
Entonces, ¿puedes escribir un lenguaje de programación que garantice la producción de programas cuya detención siempre se pueda determinar? Seguro. Simplemente no puede tener bucles, condiciones y utilizar arbitrariamente mucho almacenamiento. Si está dispuesto a vivir sin bucles, o sin declaraciones "si", o con una cantidad de almacenamiento estrictamente restringida, entonces, seguro, puede escribir un idioma cuya detención sea siempre determinable.
fuente
Te recomiendo que leas Gödel, Escher, Bach . Es un libro muy divertido e iluminador que, entre otras cosas, toca el teorema de incompletitud de Gödel y el problema de la detención.
Para responder a su pregunta en pocas palabras: el problema de detención es decidible siempre que su programa no contenga un
whilebucle (o cualquiera de sus muchas manifestaciones posibles).fuente
Para cada programa que funciona en una cantidad limitada de memoria (incluido el almacenamiento de todo tipo), se puede resolver el problema de detención; es decir, un programa indecidible está obligado a tomar más y más memoria en la ejecución.
Pero aun así, esta idea no significa que se pueda usar para problemas del mundo real, ya que un programa detenido, que funciona con solo unos pocos kilobytes de memoria, puede demorar fácilmente más que la vida útil restante del universo.
fuente
Para responder (parcialmente) a su pregunta "¿Existe un subconjunto de programas que eviten el problema de detención": sí, de hecho lo hay. Sin embargo, este subconjunto es increíblemente inútil (tenga en cuenta que el subconjunto del que estoy hablando es un subconjunto estricto de los programas que se detienen).
El estudio de la complejidad de los problemas para 'la mayoría de los insumos' se llama complejidad de caso genérico . Defina algún subconjunto de las posibles entradas, demuestre que este subconjunto cubre "la mayoría de las entradas" y proporciona un algoritmo que resuelve el problema de este subconjunto.
Por ejemplo, el problema de detención se puede resolver en tiempo polinómico para la mayoría de las entradas (de hecho, en tiempo lineal, si entiendo el documento correctamente).
Sin embargo, este resultado es bastante inútil debido a tres notas secundarias: en primer lugar, hablamos de las máquinas Turing con una sola cinta, en lugar de los programas informáticos del mundo real en las computadoras del mundo real. Hasta donde yo sé, nadie sabe si lo mismo vale para las computadoras del mundo real (a pesar de que las computadoras del mundo real pueden calcular las mismas funciones que las máquinas de Turing, la cantidad de programas permitidos, su duración y si pueden detenerse completamente diferente).
En segundo lugar, debe tener cuidado con lo que significa "la mayoría de las entradas". Significa que la probabilidad de que un algoritmo aleatorio de 'longitud' n pueda ser verificado por este algoritmo tiende a 1 mientras que n tiende a infinito. En otras palabras, si n es lo suficientemente grande, entonces un algoritmo puede verificar con seguridad un programa aleatorio de longitud n.
¿Qué programas pueden verificarse mediante el enfoque descrito en el documento? Esencialmente, todos los programas que se detienen antes de repetir un estado (donde 'estado' corresponde aproximadamente a una línea de código en un programa).
Aunque casi todos los programas se pueden verificar de esta manera, ninguno de los programas que se pueden verificar de esta manera es muy interesante y, por lo general, no serán diseñados por humanos, por lo que esto no tiene ningún valor práctico.
También indica que la complejidad de casos genéricos probablemente no podrá ayudarnos con el problema de detención, ya que casi todos los programas interesantes son (aparentemente) difíciles de verificar. O, alternativamente, redactado: casi todos los programas no son interesantes, pero son fáciles de verificar.
fuente
Hay, y de hecho hay programas en la vida real que resuelven el problema de la detención de otros problemas todo el tiempo. Son parte del sistema operativo en el que está ejecutando su computadora. La indecidibilidad es una afirmación extraña que solo dice que no existe un programa que funcione para TODOS los demás programas.
Una persona afirmó correctamente que la prueba de detención parece ser el único programa para el que no se puede resolver, ya que se traza infinitamente como un espejo. Esta misma persona también declaró que si hubiera una máquina de detención, sería mágico porque nos diría problemas matemáticos difíciles al decirnos con anticipación si su algoritmo de resolución se detendría.
La suposición en ambos casos es que la máquina de detención no rastrea porque no hay pruebas de que rastree. Sin embargo, en realidad sí rastrea / ejecuta el programa en el que se ejecuta con la entrada dada.
La prueba lógica al menos es simple. Si no necesitara rastrear al menos el primer paso, no necesitaría la entrada junto con el programa en el que se ejecuta. Para hacer uso de la información, tiene que al menos rastrear el primer paso antes de intentar analizar hacia dónde se dirige ese camino.
Los problemas matemáticos difíciles mencionados en la respuesta principal son aquellos en los que no puede avanzar rápidamente para encontrar la respuesta, lo que significa que el problema de detención tendría que continuar rastreando hasta que se reconozca algún patrón.
Por lo tanto, el único argumento práctico para sacar del problema de detención es que una máquina de detención no puede determinar el resultado de un solucionador de problemas optimizado más rápido de lo que el solucionador de problemas puede terminar.
Dar una prueba formal de este razonamiento es más difícil, y aunque creo que podría hacerlo, al intentar explicárselo a alguien, una academia resultará en que arrojen a un simio como un berrinche y se balanceen de la lámpara de araña. Es mejor no discutir con esas personas.
fuente
Aquí está la respuesta, es sí, desde 1967 en http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf
Minsky ya argumentó en 1967 que el problema de la detención puede resolverse al menos teóricamente para los sistemas de estado finito [4]: “... cualquier máquina de estado finito, si se deja completamente sola, eventualmente caerá en un período perfectamente periódico patrón repetitivo La duración de este patrón repetitivo no puede exceder el número de estados internos de la máquina ... "
(y si te apegas a máquinas de turing finitas, entonces puedes construir un oráculo)
Por supuesto, cuánto tiempo lleva esto es otra pregunta
fuente
Sí.
Definir "la mayoría".
Sí.
Definir "casi".
Mucha gente escribe Python sin usar
whilesentencias o recursiones.Muchas personas escriben Java usando solo la
fordeclaración con simple iteradores o contadores que se puede probar trivialmente que terminan; y escriben sin recurrencia.Es bastante fácil de evitar
whiley recurrencia.No.
Um. El problema de detención significa que el programa nunca puede determinar cosas sobre programas tan complejos como él mismo. Puede agregar cualquiera de una gran cantidad de restricciones para superar el problema de detención.
El enfoque estándar para el problema de la detención es permitir las pruebas utilizando un conjunto de formalismos matemáticos "más ricos" que los disponibles en el lenguaje de programación.
Es más fácil extender el sistema de prueba que restringir el idioma. Cualquier restricción conduce a argumentos para el algoritmo único que es difícil de expresar debido a la restricción.
Sí. Se llama "Teoría de grupo". Un conjunto de valores cerrados bajo un conjunto de operaciones. Cosas bastante bien entendidas.
fuente
forbucle es un bucle while, y las personas a menudo ponen cosas más complicadas en el término de la condición que simplementex < 42.forbucle está muy, muy estrictamente restringido para trabajar a través de un iterador.forSin embargo, un bucle más general en Java puede incluir condiciones adicionales que invalidan el uso simple de un iterador.