Preguntas sobre el problema de detención que consiste en decidir si un programa determinado se detiene en una entrada determinada.
No entiendo por qué el problema de detención se usa con tanta frecuencia para descartar la posibilidad de determinar si un programa se detiene. La Wikipedia [artículo] [1] explica correctamente que una máquina determinista con memoria finita detendrá o repetirá un estado anterior. Puede usar el...
Sabemos que el problema de detención (en máquinas de Turing) es indecidible para las máquinas de Turing. ¿Hay alguna investigación sobre qué tan bien la mente humana puede manejar este problema, posiblemente ayudado por las máquinas de Turing o las computadoras de uso general? Nota : Obviamente,...
Alan Turing propuso un modelo para una máquina (Turing Machine, TM) que computa (números, funciones, etc.) y demostró el Teorema de detención . Un TM es un concepto abstracto de una máquina (o motor si lo desea). El teorema de detención es un resultado imposible. Un Carnot Engine (CE) es un...
Entiendo la prueba de la indecidibilidad del problema de detención (dada, por ejemplo, en el libro de texto de Papadimitriou), basada en la diagonalización. Si bien la prueba es convincente (entiendo cada paso), no es intuitiva para mí en el sentido de que no veo cómo alguien la derivaría,...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no. ¿Cuáles son los ejemplos más simples (más pequeños) conocidos de tales
Es bastante simple entender por qué el problema de detención es indecidible para los programas impuros (es decir, aquellos que tienen E / S y / o estados dependientes del estado global de la máquina); pero intuitivamente, parece que la interrupción de un programa puro en una computadora ideal sería...
Estaba viendo las " Cinco etapas de aceptar las matemáticas constructivas " de Andrej Bauer y dice que hay dos tipos de prueba por contradicción (o dos cosas que los matemáticos llaman prueba por contradicción): Suponga que es falso ... bla, bla, bla, contradicción. Por lo tanto, es...
Como agujeros negros en informática. Solo podemos saber que existen, pero cuando tengamos uno de ellos, nunca sabremos que es uno de
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . "Alan Turing demostró en 1936 que no puede existir un algoritmo general para resolver el problema de...
Una máquina de Turing que vuelve a un estado encontrado anteriormente con su cabeza de lectura / escritura en la misma celda de la misma cinta será atrapada en un bucle. Tal máquina no se detiene. ¿Alguien puede dar un ejemplo de una máquina que nunca se detiene y que no
Recientemente escuché una analogía interesante que afirma que la prueba de Turing de la indecidibilidad del problema de detención es muy similar a la paradoja de barbero de Russell. Así que me pregunté: los matemáticos finalmente lograron hacer que la teoría de conjuntos sea coherente al pasar de...
Según tengo entendido, la prueba de que detener el problema no es computable, este problema no es computable porque si tenemos un programa P (x) que calcula si el programa x se detiene o no, tenemos una paradoja al dar P como entrada al mismo P, que tiene: P (P), tratando de decidir si P se detiene...
¿Sería posible que un entorno de tiempo de ejecución detecte bucles infinitos y posteriormente detenga el proceso asociado, o la implementación de dicha lógica sería equivalente a resolver el problema de detención? A los efectos de esta pregunta, defino un "bucle infinito" para que signifique una...
La definición principal de Turing machine (TM), al menos en mi propio libro de texto de referencia (Hopcroft + Ullman 1979) es determinista. Por lo tanto, mi propia comprensión del problema de detención es principalmente para TM determinista, aunque soy consciente de que puede considerarse para...
¿Existe una máquina de Turing que se detiene en todas las entradas pero esa propiedad no es demostrable por alguna razón? Me pregunto si esta pregunta ha sido estudiada. Tenga en cuenta que "no demostrable" podría significar un sistema de prueba "limitado" (que en el sentido débil piensa que la...
Hay tiempos espaciales relativistas (por ejemplo, tiempos espaciales MH; ver Hogarth 1994) donde una línea mundial de duración infinita puede estar contenida en el pasado de un observador finito. Esto significa que un observador normal puede tener acceso a un número infinito de pasos de...
Tengo el problema Demuestre que existe un número real para el que no existe ningún programa que se ejecute infinitamente largo y escriba los dígitos decimales de ese número. Supongo que se puede resolver reduciéndolo al problema de detención, pero no tengo idea de cómo hacerlo. También...
He leído en Wikipedia y algunos otros textos que El problema de detención es [...] decidible para autómatas lineales (LBA) [y] máquinas deterministas con memoria finita. Pero antes se escribe que el problema de detención es un problema indecidible y, por lo tanto, TM no puede resolverlo. Dado...
Tengo problemas para entender el problema de Turing. Su prueba asume que existe una máquina mágica que podría determinar si una computadora se detendría o realizaría un bucle para siempre para una entrada determinada. Luego conectamos otra máquina que invierte la salida y tenemos una contradicción...