Nombres naturels non comparables

Le "nom du jeu le plus grand nombre" demande à deux joueurs d'écrire un numéro secrètement, et le gagnant est la personne qui a écrit le plus grand nombre. Le jeu permet généralement aux joueurs d'écrire des fonctions évaluées à un moment donné, donc serait également une chose acceptable à noter. $2^{2^{2^{2}}}$

La valeur de la fonction Busy Beaver, , ne peut pas être déterminée (dans ZFC, ou tout système axiomatique cohérent raisonnable) pour de grandes valeurs de . En particulier, ne peut pas être déterminé selon cet article . Cependant, cela ne signifie pas que nous ne pouvons pas comparer les valeurs de la fonction Busy Beaver. Par exemple, nous pouvons prouver que est strictement monotone . $BB(x)$ $x$ $BB(10^4)$ $BB(x)$

Supposons que nous permettons aux joueurs d'écrire des expressions impliquant des compositions de fonctions élémentaires, de nombres naturels et de la fonction Busy Beaver. Y a-t-il deux expressions que les deux joueurs peuvent écrire, comme nous pouvons prouver dans ZFC qu'il est impossible de déterminer le vainqueur dans ZFC (en supposant que ZFC soit cohérent)?

EDIT: À l'origine, cette question disait «... des combinaisons arbitraires de fonctions calculables, de nombres naturels et de la fonction Busy Beaver».

Si nous laissons prendre la valeur si [quelque chose de grossièrement impie et inexprimable sur ce site] et sinon, alors et sont incomparables. $f(x)$ $3$ $BB(x) >$ $7$ $f(10^4)$ $6$

Cela ne me satisfait pas, en grande partie parce que $f$ n'est pas une fonction raisonnable à utiliser dans ce jeu. Cependant, je ne vois pas comment exprimer mon intuition à ce sujet, j'ai donc limité la question pour éviter les fonctions par morceaux.

computability undecidability Stella Biderman
la source

L'indécidabilité de

peut-elle être étendue, disons, à des bits individuels? Si c'est le cas, il vous suffira de comparer le 3e bit le moins significatif de

avec le 8e bit le moins significatif.

B B (10^{4})

$BB(10^4)$

B B (10^{4})

$BB(10^4)$

mhum

Les questions @mhum comme celle-ci sont délicates car la valeur de

dépend en fait du codage. Il existe des codages pour lesquels

est toujours pair, par exemple. Je crois comprendre que toutes les questions dans ce sens sont soit faciles à calculer, soit ouvertes, selon le codage.

B B (x)

$BB(x)$

B B (x)

$BB(x)$

Stella Biderman

Selon la réponse dans ce post: cstheory.stackexchange.com/questions/9652/… , il semble que BB soit en effet strictement monotone

Avi Tal

L'art de jouer à de tels jeux consiste à contourner les règles, donc je ne pense pas qu'il soit important de dire qu'une fonction est déraisonnable. Si nous devions jouer au jeu, je vous frapperais certainement avec la fonction la plus dégoûtante à laquelle je puisse penser (et je suis un logicien).

Andrej Bauer

Quand vous dites "indécidable", je suppose que vous voulez dire qu'il est indépendant d'une théorie telle que ZFC. Il y aura des instructions comme (pour les nombres naturels , ) qui ne sont pas décidées par ZFC, en supposant que ZFC est cohérent. Parce que sinon, nous pourrions calculer la fonction simplement en recherchant des preuves dans ZFC de telles déclarations.

B (m) > n

$B(m)>n$

m

$m$

n

$n$

B

$B$

Puisque est Turing complet, il existe une machine de Turing avec Con (ZFC) $B$ $\Phi$ $\iff$ accepte avec l'oracle (sur l'entrée 0, disons) et Con (ZFC) $\Phi$ $B$ $\neg$ $\iff$ rejette. $\Phi$

Supposons maintenant que Con (ZFC) soit vrai, nous savons que accepte et qu'il y a une collection de faits , qui a été utilisé dans le calcul (nous pouvons le configurer de sorte que le l'accès Oracle fonctionne de cette manière). Alors est faux, mais ce fait n'est pas prouvable dans ZFC, sinon ZFC prouverait sa propre cohérence. Bien sûr, cela peut être réécrit comme $\Phi$ $B(m_i)=n_i$ $1\le i\le k$

\sum_{je = 1}^{k} (B (m_{je}) - n_{je})^{2} > 0

$\sum_{i=1}^k (B(m_i)-n_i)^2>0$

et donc sans doute (*) fournit uneréponseOuià votre question.

\begin{matrix} (*) & \sum_{je = 1}^{k} B (m_{je})^{2} + n_{je}^{2} > \sum_{je = 1}^{k} 2 B (m_{je}) n_{je} \end{matrix}

$\sum_{i=1}^k B(m_i)^2+n_i^2>\sum_{i=1}^k 2B(m_i)n_i\tag{*}$

Cependant, je ne pense pas que nous puissions comprendre quels sont ces nombres , , car les requêtes sont adaptatives (ce qui est demandé dépend des réponses aux questions précédentes, et nous ne connaissons pas ces réponses). $m_i$ $n_i$

Bjørn Kjos-Hanssen
la source

n, m

$n,m$

n_{0} = B (7910)

$n_0=B(7910)$

B (7910) \leq n_{0}

$B(7910)\le n_0$

Nombres naturels non comparables

Réponses: