Como provar a existência de um número que não pode ser escrito por nenhum algoritmo?

14

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.

fresheed
fonte
Relevante: math.stackexchange.com/q/1266587/294695
John Coleman
Yuval Filmus forneceu uma resposta interessante que você deve ler com atenção. O problema da parada "é a coisa" que você pode tentar reduzir para o seu problema, e não o contrário (reduza o problema para a parada - como você sugere na sua pergunta).
Quetzalcoatl 14/05
Esta questão poderia ser melhorada, corrigindo a gramática na seção citada? Acho realmente difícil de analisar.
JimmyJames 14/05
@JimmyJames, eu fiz o meu melhor para traduzi-lo a partir de Russian: Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Espero que alguém melhore minha tradução.
Fresheed 14/05/19

Respostas:

18

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":

func(number):
    return number

e chame func (皮)

Albert Hendriks
fonte
17

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.

Sebastian Oberhoff
fonte
9

k1k0 0

Yuval Filmus
fonte
1

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

smrt28
fonte
Isso está intimamente relacionado à constante de Chaitin .
David Richerby
yah, broto muito mais fácil de entender ...
smrt28
-2

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.

Valmir
fonte