Hace años, escribí un ensayo titulado ¿Quién puede nombrar el número más grande? que planteaba el siguiente reto:
Tienes quince segundos. Utilizando la notación matemática estándar, palabras en inglés, o ambas, nombra un único número entero -no un infinito- en una ficha en blanco. Sea lo suficientemente preciso como para que cualquier matemático moderno razonable pueda determinar exactamente el número que ha nombrado, consultando únicamente su tarjeta y, si es necesario, la bibliografía publicada.
El ensayo continuó discutiendo los sistemas para nombrar números cada vez más enormes de manera concisa---incluyendo el Función Ackermann El Función Busy Beaver y generalizaciones superrecursivas de Busy Beaver.
Recientemente (a través de Eliezer Yudkowsky), ha llegado a mis oídos la afirmación de que hay formas de definir de forma concisa números mucho más grandes que incluso los números superrecursivos de Busy Beaver, utilizando la teoría de conjuntos. (Véase, por ejemplo esta página de Agustín Rayo, que propone una definición basada en la teoría de conjuntos de segundo orden). Sin embargo, que estas definiciones funcionen o no parece depender de algunas cuestiones muy delicadas sobre la definibilidad en la teoría de conjuntos.
Así pues, tengo una pregunta específica sobre las secuencias de números enteros de crecimiento rápido que están "bien definidas", según entiendo el término. Pero primero, permítanme aclarar algunas reglas básicas: Me parecen bien las secuencias de enteros cuyos valores son indemostrables a partir de (digamos) los axiomas de ZFC, como lo son los números de Busy Beaver suficientemente grandes. Sin embargo, lo más importante es que los valores de la secuencia deben no dependen de cualquier creencia controvertida sobre los conjuntos transfinitos. Así, por ejemplo, la "definición"
n := 1 si CH es verdadero, 2 si CH es falso
tiene sentido en el lenguaje de ZFC, pero no sería aceptable para mis propósitos. Incluso un formalista -alguien que considera que la CH, la AC, los axiomas de gran cardinalidad, etc. no tienen valores de verdad definidos- debería estar de acuerdo en que hemos elegido un específico número entero positivo.
Permítanme ahora describir los números más grandes que sé nombrar, en consonancia con las reglas anteriores, y entonces tal vez puedan ustedes hacer saltar mis números por los aires.
Dada una máquina de Turing M, sea S(M) el número de pasos realizados por M en una cinta inicialmente vacía, o 0 si M funciona eternamente. Entonces recordemos que BB(n), o el n th El número Busy Beaver, se define como el máximo de S(M) sobre todas las máquinas de Turing de n estados M. Es fácil ver que BB(n) crece más rápido que cualquier función computable. Pero para nuestros propósitos, ¡BB(n) es insignificante! Así que definamos $BB_1(n)$ para ser el análogo de BB(n), para máquinas de Turing equipadas con un oráculo que calcula $BB_0(n):=BB(n)$ . Asimismo, para todos los enteros positivos k, sea $BB_k$ sea la función Busy Beaver para las máquinas de Turing que están equipadas con un oráculo para $BB_{k-1}$ . No es difícil ver que $BB_k$ crece más rápido que cualquier función computable con un $BB_{k-1}$ oráculo.
Pero podemos ir más allá: dejemos que $BB_{\omega}$ sea la función Busy Beaver para máquinas de Turing equipadas con un oráculo que calcula $BB_k(n)$ dado (k,n) como entrada. Entonces dejemos que $BB_{\omega+1}$ sea la función Busy Beaver para máquinas de Turing con un oráculo para $BB_{\omega}$ y así sucesivamente. Está claro que podemos continuar de esta manera a través de todos los ordinales computables --- es decir, aquellos ordinales contables $\alpha$ para el que existe una forma de describir cualquier $\beta < \alpha$ utilizando un número finito de símbolos, junto con una máquina de Turing que decide si $\beta < \beta'$ con las descripciones de cada uno.
A continuación, dejemos que $\alpha(n)$ sea el mayor ordinal computable que puede definir (en el sentido anterior) una máquina de Turing con a lo sumo n estados. Entonces podemos definir
$f(n) := BB_{\alpha(n)}(n),$
que crece más rápido que $BB_{\alpha}$ para cualquier ordinal computable fijo $\alpha$ .
A diferentes manera de definir los números enormes es la siguiente. Dado un predicado $\phi$ en el lenguaje de ZFC, con una variable libre, digamos que $\phi$ "define" un entero positivo m si m es el único entero positivo que satisface $\phi$ y el valor de $m$ es el mismo en todos los modelos de ZFC.
Entonces sea z(n) el mayor número definido por cualquier predicado con n símbolos o menos.
Una cuestión que surge inmediatamente es la relación entre f(n) y z(n). No piense en es difícil demostrar que existe una constante c tal que $f(n) < z(n+c)$ para todo n (¡corríjanme si me equivoco!) Pero, ¿y en la otra dirección? ¿Crece z(n) más rápido que cualquier función definible en términos de máquinas de Turing, o podemos encontrar una función similar a f(n) que domine a z(n)? ¿Y hay otras formas de especificar números grandes que dominen a ambos?
Actualización (8/5): Después de leer los primeros comentarios, se me ocurrió que la motivación de esta pregunta podría no tener sentido para ti, si no reconoces una distinción entre aquellas cuestiones matemáticas que son "en última instancia sobre procesos finitos" (por ejemplo: si una máquina de Turing dada se detiene o no se detiene; los valores de los números de Beaver superrecursivos; la mayoría de las otras cuestiones matemáticas), y las que no lo son (por ejemplo: CH, AC, la existencia de grandes cardinales). Las primeras considero que tienen una respuesta definitiva, independientemente de la comprobabilidad de la respuesta en cualquier sistema formal como ZFC. (Si dudas de que exista un hecho sobre si una determinada máquina de Turing se detiene o corre eternamente, entonces también podrías dudar de que exista un hecho sobre si una determinada afirmación es o no demostrable en ZFC). Por el contrario, en el caso de cuestiones como CH y AC, se puede debatir si significa algo discutir su verdad independientemente de su demostrabilidad en algún sistema formal.
En esta pregunta, me refiero a las secuencias de números enteros que son "definibles en última instancia en términos de procesos finitos" y que, por lo tanto, se puede considerar que toman valores definidos, independientemente de las creencias de uno sobre cuestiones de teoría de conjuntos. Por supuesto, "definible en última instancia en términos de procesos finitos" es un término vago. Pero se pueden enumerar muchas afirmaciones que ciertamente satisfacen el criterio (por ejemplo: cualquier cosa expresable en términos de máquinas de Turing y si se detienen), y otras que ciertamente no lo hacen (por ejemplo: CH y AC). Una gran parte de lo que estoy preguntando aquí es hasta dónde se extienden los límites de lo "definible en términos de procesos finitos".
Sí, es posible que mi pregunta degenere en desacuerdos filosóficos. Pero a priori Pero también es posible que alguien pueda dar una secuencia que todo el mundo esté de acuerdo en que es "definible en términos de procesos finitos", y que eche por tierra mi f(n) y z(n). Esto último constituiría una respuesta completamente satisfactoria a la pregunta.
Actualización (8/6): Ahora se ha demostrado de forma satisfactoria que z (tal y como la definí) se ve superada por f. La razón es que z se define cuantificando sobre todo modelos de ZFC. Pero por el Teorema de Completitud, esto significa que z también puede definirse "sintácticamente", en términos de demostrabilidad en ZFC. En particular, podemos calcular z utilizando un oráculo para el $BB_1$ (¿o posiblemente incluso la función BB?), definiendo una máquina de Turing que enumere todos los enteros positivos m así como todas las pruebas ZFC de que el predicado $\phi$ escoge m.
Así que gracias no quería prejuzgar las cosas, pero esta es realmente la respuesta que esperaba. Por si no ha quedado claro, me interesan los números grandes no tanto por sí mismos, sino como una forma concreta de comparar el poder expresivo de diferentes sistemas notacionales. Y tengo la fuerte intuición de que las máquinas de Turing son un sistema notacional "máximamente expresivo", al menos para aquellos números que cumplen mi criterio de estar "definidos en última instancia en términos de procesos finitos" (así que, en particular, son independientes de la verdad o falsedad de afirmaciones como CH). Si uno podría utilizar ZFC para definir secuencias de números enteros que hagan saltar por los aires mi secuencia f(n) (y que lo hagan de forma independiente del modelo), eso sería un serio desafío a mi intuición.
Así que permítanme reenfocar la pregunta: ¿es correcta mi intuición, o hay alguna forma más inteligente de utilizar ZFC para definir una secuencia de números enteros que haga volar a f(n)?
En realidad, una propuesta para utilizar ZFC para al menos coincide con la tasa de crecimiento de f se me ocurre ahora. Recordemos que definimos la secuencia z maximizando sobre todos los modelos M de ZFC. Sin embargo, esta definición se encontró con problemas, relacionados con los "modelos que se odian a sí mismos" que contienen enteros no estándar que codifican las pruebas de Not(Con(ZFC)). Así que en su lugar, dado un modelo M de ZFC y un entero positivo k, llamemos a M "k-verdadero" si cada $\Pi_k$ La sentencia aritmética S es verdadera en M si y sólo si S es semánticamente verdadera (es decir, verdadera para los enteros estándar). (En este caso, un $\Pi_k$ La oración aritmética es una oración con k cuantificadores alternados, todos los cuales abarcan sólo números enteros).
Ahora, definamos la función
$z_k(n)$
exactamente igual que z(n), salvo que ahora sólo tomamos el máximo sobre aquellos modelos M de ZFC que son k-verdaderos.
Esto está por demostrar, pero mi adivinar es que $z_k(n)$ debería crecer más o menos como $BB_{k+c}(n)$ Entonces, para obtener secuencias de crecimiento más rápido, se podría reforzar el requisito de k-verdad, para requerir que los modelos de ZFC sobre los que se maximiza estén de acuerdo con lo que es semánticamente verdadero, incluso para oraciones sobre números enteros que se definen usando varios ordinales computables. Pero mediante este tipo de dispositivos, parece claro que se puede coincide con f, pero no la hace desaparecer y, de hecho, parece más sencillo olvidarse de ZFC y hablar directamente de las máquinas de Turing.
