Eu tenho o problema:
Mostre que existe um número real para o qual não existe um programa que seja infinitamente longo e grave os dígitos decimais desse número.
Suponho que isso possa ser resolvido reduzindo-o ao problema da parada, mas não tenho idéia de como fazê-lo.
Também gostaria de receber links para problemas semelhantes para praticar mais.
algorithms
reductions
halting-problem
fresheed
fonte
fonte
Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Espero que alguém melhore minha tradução.Respostas:
Como Sebastian indica, existem apenas (infintamente, mas) muitos programas. Liste-os para criar uma lista de programas. A lista é (infinitamente, mas) contativamente longa. Cada programa gera um número em R. A partir disso, podemos criar uma lista (infinita, mas) contável de números em R. Agora, podemos aplicar o argumento diagonal de Cantor diretamente para provar que ainda deve haver outros números.
A propósito, se o algoritmo tiver argumentos (finitos), você poderá reescrevê-lo como uma lista "mais longa" de programas em que cada programa não possui argumentos.
Com relação ao seu comentário "E se números reais forem permitidos como argumento", a premissa da pergunta está errada: todos os números em R podem ser gerados. Se alguém encontrar um número, digamos 皮, e afirmando que não pode ser calculado, temos o seguinte "algoritmo":
e chame func (皮)
fonte
Na verdade, é muito mais simples. Existe apenas um número contável de algoritmos. No entanto, existem incontáveis números reais. Portanto, se você tentar emparelhá-los, alguns números reais serão deixados em espera.
fonte
fonte
O número é um número infinitamente longo que, após o ponto decimal, codifica de qualquer maneira todas as máquinas de turing que não param. Com esse número, você seria capaz de resolver o problema de parada.
Você pode "pesquisar" a TM no número e executá-la em paralelo. Se a TM parar, ela pára. Caso contrário, você "encontraria seu código no número".
Existem muitas modificações na prova e você poderá reproduzi-las após a primeira lição de complexidade :-)
fonte
Um ponto se move em um caminho pela função y = 2x. Quando a abscissa é um número não computável, não há como o Ponto calcular seu caminho, mas sabemos que ele continua. Portanto, números não computáveis podem existir.
fonte