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 agradecería enlaces a problemas similares para practicar más.
algorithms
reductions
halting-problem
refrescar
fuente
fuente
Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Espero que alguien mejore mi traducción.Respuestas:
Como indica Sebastian, solo hay (infinitamente) innumerables programas. Enumerarlos para crear una lista de programas. La lista es (infinitamente pero) contablemente larga. Cada programa genera un número en R. A partir de eso, podemos crear una lista de números (infinita pero) contable en R. Ahora podemos aplicar el argumento diagonal de Cantor directamente para demostrar que todavía debe haber otros números.
Por cierto, si el algoritmo tiene argumentos (finitos), puede volver a escribir eso como una lista "más larga" de programas donde cada programa no tiene ningún argumento.
Con respecto a su comentario "¿Qué pasa si se permiten números reales como argumento?", Entonces la premisa de la pregunta es incorrecta: todos los números en R pueden generarse. Si alguien encuentra un número, diga 皮 y afirma que no se puede calcular, tenemos el siguiente "algoritmo":
y llamar a func (皮)
fuente
En realidad es mucho más simple. Solo hay un número contable de algoritmos. Sin embargo, hay innumerables números reales. Entonces, si intentas emparejarlos, algunos números reales quedarán pendientes.
fuente
fuente
El número es un número infinitamente largo que después del punto decimal codifica de todos modos todas las máquinas de Turing que no se detienen. Con este número, podrá resolver el problema de detención.
Puede "buscar" el TM en el número y ejecutarlo en paralelo. Si TM se detiene, se detiene. Si no, "encontrará su código en el número".
Hay muchas modificaciones de la prueba y debería poder reproducirlas después de la primera lección de complejidad :-)
fuente
Un punto se mueve en una ruta por la función y = 2x. Cuando la abscisa es un número no computable, no hay forma de que el Punto calcule su camino, pero sabemos que continúa. Por lo tanto, los números no computables pueden existir en absoluto.
fuente