Números naturais não comparáveis

11

O "nome do jogo com o maior número" pede a dois jogadores que anotem um número secretamente, e o vencedor é a pessoa que anotou o número maior. O jogo geralmente permite que os jogadores anotem as funções avaliadas em um ponto, então 2222 também seria aceitável.

O valor da função Busy Beaver, BB(x) , não pode ser determinado (no ZFC, ou em qualquer sistema axiomático consistente e razoável) para valores grandes de x . Em particular, BB(104) não pode ser determinado de acordo com este artigo . No entanto, isso não significa que não possamos comparar valores da função Busy Beaver. Por exemplo, podemos provar que BB(x) é estritamente monotônico .

Vamos supor que permitimos que os jogadores anotem expressões envolvendo composições de funções elementares, números naturais e a função Busy Beaver. Existem duas expressões que os dois jogadores podem escrever para que possamos provar no ZFC que determinar o vencedor no ZFC é impossível (supondo que o ZFC seja consistente)?

Edição: Originalmente, esta pergunta dizia "... combinações arbitrárias de funções computáveis, números naturais e a função Busy Beaver".

Se deixarmos f(x) assumir o valor de 3 se BB(x)> [algo incrivelmente grande e inexprimível neste site] e 7 se não for, então f(104) e 6 são incomparáveis.

Isso não me satisfaz, principalmente porque f não é uma função razoável para alguém usar neste jogo. No entanto, não vejo como expressar minha intuição sobre isso, então restringi a pergunta para evitar funções fragmentadas.

Stella Biderman
fonte
1
A indecidibilidade de ser estendida para, digamos, bits individuais? Nesse caso, basta comparar o terceiro bit menos significativo de B B ( 10 4 ) com o oitavo bit menos significativo. BB(104)BB(104)
Mhum
2
@mhum perguntas como essa são complicadas porque o valor de é realmente dependente da codificação. Existem codificações para as quais B B ( x ) é sempre par, por exemplo. Meu entendimento é que todas as perguntas nesse sentido são trivialmente computáveis ​​ou abertas, dependendo da codificação. BB(x)BB(x)
Stella Biderman
1
De acordo com a resposta neste post: cstheory.stackexchange.com/questions/9652/... , parece que BB é realmente estritamente monotônica
Avi Tal
A arte de jogar esses jogos é dobrar as regras, então não acho que seja importante dizer que alguma função não é razoável. Se jogássemos o jogo, eu definitivamente acertaria você com a função mais repugnante que eu possa pensar (e eu sou um lógico).
Andrej Bauer

Respostas:

9

B(m)>n
mnB

BΦ ΦB¬ Φ

ΦB(mi)=ni1ik

i=1k(B(mi)ni)2>0
(*)i=1kB(mi)2+ni2>i=1k2B(mi)ni

mini

Bjørn Kjos-Hanssen
fonte
1
n,m
5
n0=B(7910)B(7910)n0