A previsão (no limite) de seqüências computáveis ​​é tão difícil quanto o problema de parada?

10

Pergunta : A previsão (conforme definida abaixo) de seqüências computáveis ​​é tão difícil quanto o problema de parada?

Elaboração : "Predizer" significa prever com sucesso, o que significa cometer apenas erros finitos na tarefa de tentar prever o n-ésimo bit da sequência com acesso aos n-1 bits anteriores (iniciando no primeiro bit e passando pelo seqüência computável infinita inteira).

Existe um argumento simples de diagonalização (devido a Legg 2006) que, para qualquer preditor de máquina de Turing p, existe uma sequência computável na qual ele comete infinitos erros. (Construa uma sequência que tenha como enésimo termo o oposto do que p prevê, dados os termos n-1 anteriores na sequência.) Portanto, não há preditor computável que prediz todas as sequências computáveis. Um oráculo de parada permitiria a construção de tal preditor. Mas você pode mostrar que ter um preditor desse tipo permite resolver o problema da parada?

Mais elaboração

Definição (Legg)
Um preditor p é uma máquina de Turing que tenta prever o n-ésimo bit de uma sequência S com acesso aos n-1 bits anteriores. Se a previsão não corresponder ao n-ésimo bit da sequência, chamamos isso de um erro . Diremos que p prevê S se p cometer muitos erros finitos em S. Em outras palavras, p prevê S se houver algum número M na sequência st para cada m> M, p predizer corretamente o m-ésimo bit de S acesso aos primeiros bits m-1.

Formalmente, poderíamos definir uma máquina preditora como tendo três fitas. A sequência é inserida como entrada bit a bit em uma fita, as previsões para o próximo bit são feitas em uma segunda fita (a máquina só pode se mover através dessa fita) e, em seguida, há uma fita de trabalho na qual a máquina pode se mover nas duas direções.

Resultados simples
Pela definição acima, há um preditor que prevê todos os números racionais. (Use a enumeração zig-zag padrão dos racionais. Comece prevendo o primeiro racional da lista, se houver algum erro, vá para o próximo racional.) Por um argumento semelhante, há um preditor que tem acesso a N, é capaz de prever todas as seqüências de complexidade de Kolomogorov menores ou iguais a N. (Execute todas as máquinas de N bits em paralelo e faça a previsão da máquina que parar primeiro Você pode apenas cometer erros finitos).

Citação Shane Legg 2006 http://www.vetta.org/documents/IDSIA-12-06-1.pdf (não o autor deste post)


fonte

Respostas:

11

Na verdade, isso é mais fácil do que resolver o problema da parada.

f:NNg:NNng(n)f(n)

φeeNN{0,1}

fp

p(a0,,ak1)ak{0,1}a0,,akφt(0),,φt(k)tkf(k)f(k)tak=0

qφqkt=qakfφqs(n)=φq(n)

Bjørn Kjos-Hanssen
fonte