Números naturales no comparables

El "nombre del juego de mayor número" le pide a dos jugadores que escriban un número en secreto, y el ganador es la persona que anotó el número mayor. El juego comúnmente permite a los jugadores escribir funciones evaluadas en un punto, por lo que también sería una cosa aceptable para escribir. $2^{2^{2^{2}}}$

El valor de la función Busy Beaver, , no se puede determinar (en ZFC o en cualquier sistema axiomático razonablemente consistente) para valores grandes de . En particular, no puede determinarse según este documento . Sin embargo, esto no significa que no podamos comparar valores de la función Busy Beaver. Por ejemplo, podemos demostrar que es estrictamente monótono . $BB(x)$ $x$ $BB(10^4)$ $BB(x)$

Supongamos que permitimos a los jugadores escribir expresiones que involucren composiciones de funciones elementales, números naturales y la función Busy Beaver. ¿Hay dos expresiones que los dos jugadores pueden escribir para que podamos probar en ZFC que determinar el ganador en ZFC es imposible (suponiendo que ZFC sea consistente)?

EDITAR: Originalmente esta pregunta decía "... combinaciones arbitrarias de funciones computables, números naturales y la función Busy Beaver".

Si dejamos que tome el valor de si [algo impío grande e inexpresable en este sitio web] y si no lo es, entonces y son incomparables. $f(x)$ $3$ $BB(x) >$ $7$ $f(10^4)$ $6$

Esto no me satisface, en gran parte porque no es una función razonable para que alguien la use en este juego. Sin embargo, no veo cómo expresar mi intuición sobre esto, por lo que he restringido la pregunta para evitar funciones por partes. $f$

computability undecidability Stella Biderman
fuente

¿Se puede extender la indecidibilidad de a, digamos, bits individuales? Si es así, entonces solo tendría que hacer algo como comparar el tercer bit menos significativo de con el octavo bit menos significativo.

B B (10^{4})

$BB(10^4)$

B B (10^{4})

$BB(10^4)$

mhum

Las preguntas de @mhum como esa son complicadas porque el valor de realidad depende de la codificación. Hay codificaciones para las cuales siempre es par, por ejemplo. Tengo entendido que todas las preguntas a lo largo de esas líneas son trivialmente computables o abiertas, dependiendo de la codificación.

B B (x)

$BB(x)$

B B (x)

$BB(x)$

Stella Biderman

De acuerdo con la respuesta en esta publicación: cstheory.stackexchange.com/questions/9652/… , parece que BB es realmente estrictamente monótono

Avi Tal

El arte de jugar tales juegos es doblar las reglas, así que no creo que cuente decir que alguna función no es razonable. Si jugáramos el juego, definitivamente te golpearía con la función más desagradable que se me ocurra (y soy un lógico).

Andrej Bauer

Respuestas:

Cuando dices "indecidible", supongo que quieres decir que es independiente de una teoría como ZFC. Habrá declaraciones como (para números naturales , ) que ZFC no decide, suponiendo que ZFC sea consistente. Porque de lo contrario podríamos calcular la función simplemente buscando pruebas en ZFC de tales declaraciones.

B (m) > n

$B(m)>n$

m

$m$

n

$n$

B

$B$

Dado que es Turing completo, hay alguna máquina de Turing con Con (ZFC) acepta con oracle (en la entrada 0, por ejemplo) y Con (ZFC) rechaza. $B$ $\Phi$ $\iff$ $\Phi$ $B$ $\neg$ $\iff$ $\Phi$

Ahora, suponiendo que en realidad Con (ZFC) sea cierto, sabemos que acepta y hay una colección de hechos , que se utilizó en el cálculo (podemos configurarlo de modo que el acceso al oráculo funciona de esta manera). Entonces es falso, pero este hecho no es demostrable en ZFC, de lo contrario ZFC demostraría su propia consistencia. Por supuesto, esto se puede reescribir como y así podría decirse ( *) proporciona una respuesta afirmativa a su pregunta. $\Phi$ $B(m_i)=n_i$ $1\le i\le k$

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

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

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

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

Sin embargo, no creo que podamos averiguar cuáles son estos números , , porque las consultas son adaptativas (lo que se pregunta depende de las respuestas a las preguntas anteriores, y no sabemos esas respuestas). $m_i$ $n_i$

Bjørn Kjos-Hanssen
fuente

Esta es una excelente prueba de existencia de lo que estoy buscando. Sin embargo, estoy específicamente después de un ejemplo real de tal ecuación, con algún tipo de expresión que podríamos escribir para . También tiene razón acerca de que mi uso de "indecidible" es incorrecto, he modificado mi pregunta.

n, m

$n,m$

Stella Biderman

@StellaBiderman sí y de todos modos si entonces la declaración es independiente de ZFC por el resultado de Aaronson y Yedidia en arxiv.org/abs/1605.04343

n_{0} = B (7910)

$n_0=B(7910)$

B (7910) \leq n_{0}

$B(7910)\le n_0$

Bjørn Kjos-Hanssen