El problema de encontrar la primera cifra del número de Graham

Question

Motivación

En este vídeo de la BBC sobre el infinito mencionan El número de Graham . En la segunda parte, Graham menciona que "quizá nadie sepa nunca cuál es [el primer] dígito". Esto me hizo pensar: ¿Sería posible demostrar que (bajo algunos supuestos sobre la velocidad de nuestros ordenadores) nunca podremos determinar el primer dígito?

En lógica tienes resultados de independencia como "No podemos decidir si CA es cierto en ZF ". Pero no podemos esperar este tipo de resultado en este caso, ya que podemos programar fácilmente un ordenador para que nos dé la respuesta. El problema es que no tenemos tiempo suficiente para esperar la respuesta.

En la teoría de la complejidad se demuestran cosas como "ningún programa puede resolver todos los problemas de este conjunto infinito de problemas, rápidamente". Pero en este caso sólo tienes un problema, y es fácil escribir un programa que te dé la respuesta. Simplemente escribe un programa que imprima "1", otro que imprima "2"... y un programa que imprima "9". Ahora tienes un programa que te da la respuesta. El problema es que no sabes cual de los 9 programas es el correcto.

Preguntas

Edita: Ahora he planteado las preguntas de otra manera. Antes preguntaba sobre programas informáticos en lugar de pruebas.

1. ¿Sería posible demostrar que cualquier prueba de lo que es el primer dígito en los números de Grahams, tendría longitud por lo menos $10^{100}$ ?
2. ¿Existen resultados similares? Es decir, ¿conocemos un enunciado decidible P y una prueba que cualquier prueba o refutación de P debe tener longitud $10^{100}$ .
3. O podemos demostrar, que cualquier prueba que una prueba o refutación de P debe tener una longitud de al menos $n$ debe tener a su vez una longitud mínima de $n$ ?

Creo que la respuesta a 3) es no, al menos si todas las pruebas están en el mismo sistema. Una prueba de este tipo demostraría que debe tener una longitud mínima de n para cualquier n.

(Preguntas antiguas:

1. ¿Sería posible demostrar que un ordenador necesitaría al menos decir $10^{100}$ pasos para determinar la primera cifra del número de Grahams?
2. ¿Existen resultados similares? Es decir, ¿conocemos un enunciado decidible P y una prueba de que P no puede decidirse en menos de lo que digamos $10^{100}$ pasos.
3. ¿O podemos demostrar que necesitamos al menos $n$ pasos para demostrar que un enunciado decidible no puede decidirse en menos de $n$ pasos?)

(No estoy seguro de haber etiquetado correctamente. No dudes en volver a etiquetar o sugerir etiquetas mejores).

Answer 1

Fácil: 1. Pero probablemente querías decir base 10, no base 3, ¿verdad? Eso es un poco más difícil...

[Espero no infringir alguna norma del modus operandi al añadir un poco de humor a una respuesta.]

Answer 2

Me parece que la pregunta es realmente sobre la prueba más corta de que el primer dígito del número de Graham es el que es, en lugar del programa más corto que lo calcula. De hecho, si tienes un programa eficiente más una prueba de que el programa es correcto (que descarta tus nueve programas, uno de los cuales es correcto), entonces tienes una prueba corta, y si tienes una prueba corta entonces tienes un programa eficiente que sabes que es correcto (simplemente imprime la respuesta).

Ciertamente, hay resultados que se sabe que son verdaderos en PA pero que sólo tienen pruebas muy largas en PA. Por ejemplo, la prueba de que toda sucesión de Goodstein llega finalmente a cero necesita el axioma del infinito. Pero, en principio, se puede demostrar que cualquier caso particular llega a cero, sólo que la demostración llevaría mucho tiempo. Así que la respuesta a su pregunta 2 es sí si se restringe a PA. Imagino que se conocen resultados similares para otros sistemas axiomáticos. Como dice Gerhard, Harvey Friedman sabe mucho de este tipo de cosas.

Answer 3

Harvey Friedman se ha ocupado de muchos números grandes, así como de cuestiones relativas a su computabilidad. (Véase Enormous Numbers in Real Life.) Le sugiero que le envíe su pregunta por correo electrónico. (También puedes consultar otros posts de Math Overflow sobre el número de Graham).

Gerhard "Ask Me About System Design" Paseman, 2010.04.08

Answer 4

En general, la primera cifra de un número $A$ puede determinarse a partir de la parte fraccionaria de $\log_{10} A$ . En concreto, si $\log_{10} A = n + \gamma$ donde $n = \lfloor \log_{10} A \rfloor$ y $\gamma = \{ \log_{10} A \}$ entonces $A = 10^\gamma 10^n$ y $1 \leq 10^\gamma < 10$ . Por lo tanto, el primer dígito decimal de $A$ es $k$ si $k \leq 10^\gamma < k+1$ o, lo que es lo mismo, si $\log_{10} k \leq \gamma < \log_{10} (k+1)$ .

Tomando el caso especial en el que $A = G$ es el número de Graham, tenemos $G = 3^{3^x}$ para algún número natural $x$ . Entonces $\log_{10} G = 3^x \log_{10} 3$ . Obsérvese que la multiplicación por $3^x$ es lo mismo que desplazar los dígitos de base 3 de un número $x$ lugares a la izquierda. Configuración $\alpha = \log_{10} 3$ el problema se reduce a encontrar los dígitos de base 3 de $\alpha$ Inicio $x$ posiciones después del punto decimal.

Entonces la siguiente conjetura implicaría que es imposible demostrar nada sobre el primer dígito de $G$ a tiempo $o (x)$ :

Conjetura: Dado un número natural $x$ y una secuencia de dígitos de base 3 $z_0, \dots, z_{k-1}$ cualquier prueba en ZFC de la afirmación "La primera $k$ dígitos de base 3 de $\alpha$ Inicio $x$ los decimales no son $z_0 \dots z_{k-1}$ "debe tener la longitud $\Omega\:(n)$ .

Se pueden plantear conjeturas análogas para cualquier otra $b \geq 2$ y sustituyendo $\alpha = \log_{10} 3$ con cualquier otro número irracional conocido. La razón para esperar que tal conjetura se mantenga es que no creo que haya manera de probar nada sobre $x$ dígito de $\alpha$ que es esencialmente diferente del cálculo del $x$ ª cifra con un algoritmo de propósito general, y no creo que existan tales algoritmos sublineales de propósito general. Dado que sí existe un algoritmo de tiempo cuasilineal para calcular los dígitos de $\alpha$ (véase Aritmética informática moderna para más detalles), esta conjetura daría unas estimaciones bastante precisas $\tilde {\Theta}\:(\log \log G)$ pasos para la prueba más corta que determina el primer dígito de $G$ .

Demostrando que no existen algoritmos en tiempo sublineal para calcular la $x$ th de cualquier número irracional natural parece más difícil que el problema P contra NP, que ya está mucho más allá de lo que la informática teórica actual puede lograr, y la conjetura que he expuesto antes probablemente sea aún más difícil. Sin embargo, si alguna vez llegamos al punto en el que sea posible dar límites inferiores precisos sobre los algoritmos más eficientes posibles para la mayoría de los problemas, entonces este problema sería potencialmente solucionable.

Answer 5

En base nueve es 3.