Nombrar sucintamente los grandes números: ZFC frente a Busy-Beaver

Question

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.

Answer 1

Creo que tu pregunta no es tan precisa como la planteas.

En primer lugar, permítame señalar que usted no ha definido realmente una función $z$ en el sentido de dar un primer orden de primer orden en la teoría de conjuntos, y se puede probar que no se puede hacer debido al teorema de Tarski sobre la no definibilidad de la verdad. Simplemente no tenemos forma de expresar la relación x es definible en el lenguaje habitual de primer orden de la teoría de conjuntos. Más concretamente:

Teorema. Si ZFC es consistente, entonces hay modelos de ZFC en los que la colección de números naturales definibles no es un conjunto o incluso una clase.

Prueba. Si V es un modelo de ZFC, entonces dejemos que $M$ sea un interno ultrapoder de $V$ por un ultrafiltro no principal en $\omega$ . Así, los números naturales de $M$ no son estándar en relación con $V$ . Los elementos definibles de $M$ están todos contenidas dentro del rango del mapa de ultrapoderes, que en los números naturales es una parte acotada de los números naturales de $M$ . Así, $M$ no puede tener esta colección de objetos como un conjunto o clase, ya que revelaría a $M$ que sus números naturales están mal fundados, contradiciendo que $M$ satisface la ZFC. QED

En este modelo, su definición de $z$ no es de primer orden. Podría tener sentido tratar su función $z$ Sin embargo, en como una función definida externamente, definida fuera del modelo el modelo (como a través de la lógica de segundo orden). En este caso, $z(n)$ sólo implica definiciones estándar o metateóricas, y surgen otros problemas.

Teorema. Si ZFC es consistente, entonces hay un modelo de ZFC en el que $z(n)$ está limitada por una función constante.

Prueba. Si ZFC es consistente, entonces también lo es $ZFC+\neg Con(ZFC)$ . Sea $V$ sea cualquier modelo de esta teoría, de modo que no hay modelos de ZFC allí, y la segunda parte de la definición de $z$ se vuelve vacuo, por lo que se reduce a su definible en $V$ primera parte. Sea $M$ ser un ultrapoder interno ultrapoder de $V$ por un ultrafiltro en $\omega$ . Así, $M$ no es estándar en relación con $V$ . Pero la función $z$ , definido externamente, utiliza sólo definiciones estándar, y los elementos definibles de $M$ todos se encuentran en el rango de la mapa de ultrapoderes. Si $N$ es cualquier $V$ -elemento no estándar de $M$ entonces todo elemento definible de $M$ está por debajo de $N$ y así que $z(n)\lt N$ por cada $n$ sur $M$ . QED

Teorema. Si ZFC es consistente, entonces hay un modelo de ZFC en el que $f(n)\lt z(10000)$ para todo número natural n en la metateoría.

Prueba. Si ZFC es consistente, entonces también lo es $ZFC+\neg Con(ZFC)+GCH$ . Sea $V$ sea un modelo contable de $ZFC+\neg Con(ZFC)+GCH$ . Desde $V$ no tiene modelos de ZFC, de nuevo la segunda parte de su definición es vacía, y se reduce a la definición en $V$ parte. Dejemos que $M$ sea de nuevo un ultrapoder interno de $V$ por un ultrafiltro en $\omega$ , y que $N$ ser un $V$ -número natural no estándar de $M$ . Cada elemento definible de $M$ está en el rango de la mapa de la ultrapotencia, y por lo tanto por debajo de $N$ . En particular, para todo número natural metateórico $n$ tenemos $f(n)\lt N$ sur $M$ ya que $f(n)$ es definible. Ahora, dejemos que $M[G]$ sea una extensión forzada en la que el continuo tiene tamaño $\aleph_N^M$ . Así, $N$ es definible en $M[G]$ mediante una fórmula relativamente corta; digamos que 10000 símbolos (pero yo no he contado). Como el forzamiento no afecta a la existencia de modelos ZFC o cálculos Turing entre $M$ y $M[G]$ se deduce que $f(n)\lt z(10000)$ sur $M[G]$ para cualquier número natural de $V$ . QED

Teorema. Si ZFC es consistente, entonces hay un modelo de ZFC con una constante de número natural $c$ en el que $z(n)\lt f(c)$ para todos los números naturales metateóricos $n$ .

Prueba. Utilice el modelo $M$ (o $M[G]$ ) como en el caso anterior. Esta vez dejemos que $c$ sea cualquier $V$ -número natural no estándar de $M$ . Dado que los elementos definibles de $M$ se encuentran en el rango del mapa mapa de ultrapoderes, se deduce que cada z(n), para metateórico $n$ se incluye en el $V$ -estándar elementos de $M$ que son todos menores que $c$ . Pero $M$ tiene fácilmente $c\leq f(c)$ y así $z(n)\lt f(c)$ para todos estos $n$ . QED

Answer 2

Esto es básicamente un comentario pero es demasiado largo para eso. Espero que tal vez pueda ayudar a explicar a Scott por qué hay un problema con su "definición" de " $\phi$ define $m$ ."

El problema fundamental es que no está claro qué significa para $m$ para "satisfacer $\phi$ ". Ciertamente, podemos tomar la fórmula $\phi$ e insertar sintácticamente $m$ para producir una fórmula $\phi(m)$ . Pero el mero hecho de producir $\phi(m)$ no determina si " $m$ satisface $\phi$ ." Si $m$ satisface $\phi$ depende de si $\phi(m)$ es cierto . Y no está claro qué significa esto.

Cuando digo que no está claro lo que significa, no estoy diciendo que no conozcamos ningún algoritmo para determinar la verdad. Si ése fuera el único problema, un matemático clásico no tendría nada de qué quejarse. El problema es peor que eso. No sabemos ni siquiera qué significa la palabra "verdadero". significa aquí. Aquí es donde entra el teorema de Tarski. Ni siquiera podemos definir la palabra "verdadero" utilizando medios matemáticos ordinarios. Si pudiéramos, entonces podríamos formalizar esa definición en ZFC, al igual que podemos formalizar todo el discurso matemático ordinario, y eso no es posible.

Tal vez un ejemplo concreto ayude. Dejemos que $\phi(x)$ ser " $x=1$ y hay un cardinal estrictamente entre $\aleph_0$ y $2^{\aleph_0}$ ." ¿El 1 satisface $\phi$ ?

Ahora bien, este problema no es insuperable. Hay formas de intentar definir la verdad. Pero es un asunto sutil y hay que ser explícito y cuidadoso. Sin eso, no tenemos una definición clara de lo que significa para $m$ para satisfacer $\phi$ y por lo tanto no tenemos una definición clara de lo que significa para $\phi$ para definir $m$ .

Answer 3

Parece que la posición filosófica que das por sentada se acerca a la posición llamada "predicativismo" defendida por matemáticos como Poincarè y Weyl, y cuyos límites han sido delineados con mayor precisión por Solomon Feferman. A grandes rasgos, la posición de Feferman es que la noción de "conjunto arbitrario" no está lo suficientemente bien definida como para que enunciados como AC y CH adquieran valores definidos. Por lo tanto, deberíamos limitar nuestra atención a los números naturales y a cualquier cuestión que esté "implícita" en nuestro concepto de los números naturales; por ejemplo, hablar dentro de la Aritmética de Peano (PA) tiene sentido, pero también lo tiene hablar de la verdad de las cadenas PA, y hablar de la verdad de las cadenas que hablan de la verdad de las cadenas PA, etc. En su sistema, las preguntas sobre las funciones de Busy Beaver $BB_\alpha$ tienen valores definidos siempre que $\alpha$ es un ordinal menor que $\Gamma_0$ , donde $\Gamma_0$ es el ordinal de Feferman-Schutte.

Podría ser posible extender la predicatividad a algunos ordinales mayores que $\Gamma_0$ sin perder la "definición de la verdad"; por ejemplo, esto es argumentado por Nik Weaver . Pero creo que extender al primer ordinal no recursivo (es decir, el ordinal de Church-Kleene), que está implícito en la función $f(n) = BB_{\alpha(n)}(n)$ definida en la OP, es problemática. Esto se debe a que la noción de "ordinalidad" no es una noción que sea "definible en última instancia en términos de procesos finitos", en tus términos. Para ser más específicos, recordemos que un ordinal computable es una ordenación computable de $\mathbb N$ con la propiedad de que todo subconjunto no vacío de $\mathbb N$ tiene un elemento mínimo con respecto a esta ordenación. La noción de ordenación computable está ciertamente bien definida, pero la propiedad de ordinalidad depende de la cuantificación universal sobre el ámbito de los subconjuntos de los números enteros. Según Feferman, dicha cuantificación está mal definida porque "el concepto de la totalidad de subconjuntos arbitrarios de $\mathbb N$ es esencialmente infradeterminado o vago" -- porque los conjuntos se introducen mediante definiciones, y ningún sistema formal para describir cómo definimos las cosas puede capturar todas las diferentes maneras en que podemos definirlas.

Ahora bien, usted puede estar en desacuerdo con Feferman en este punto, tal vez siendo escéptico sólo de las totalidades definidas que consisten en todos los subconjuntos de $\mathbb R$ o tipos superiores. En cuyo caso creo que sería una nueva posición filosófica, y valdría la pena ampliar los límites exactos de este sistema y la motivación de esos límites.

Por otro lado, sin aceptar la noción de una totalidad de subconjuntos de $\mathbb N$ En este sentido, se puede aceptar filosóficamente la noción de ordinalidad como algo que describe la "buena definición" de los conceptos, es decir, se dice que un ordenamiento de los enteros es ordinal si cualquier definición recursiva (en un lenguaje formal particular) de una función $f:\mathbb N\to\mathbb N$ de la forma $$ f(n) = F(f\upharpoonleft \{m : m < n\}) $$ determina una función total bien definida $f:\mathbb N\to\mathbb N$ . Pero esto plantea la cuestión de si el concepto de "bien definido" es realmente un concepto bien definido. Ciertamente, un argumento diagonal puede causar problemas si pretendemos significar lo mismo con los dos usos de la frase "bien definido" en la frase anterior. Además, la dependencia de este concepto del lenguaje formal utilizado para la cuantificación universal sobre $F$ también puede ser problemático. (No se puede cuantificar sobre todos los lenguajes formales por la misma razón que no se puede cuantificar sobre todos los conjuntos). Pero tal vez estas cuestiones filosóficas no sean demasiado problemáticas, en cuyo caso la cuestión de si un determinado ordenamiento de los números naturales es o no un buen ordenamiento tiene siempre un valor de verdad definido.

Pero en cualquier caso, me parece que si se acepta la noción de "bien definido" descrita anteriormente, entonces ya no se está hablando de aquellas cosas que son "definibles en última instancia en términos de procesos finitos", sino que se han introducido nuevas nociones y se está hablando de ellas.

Así que en conclusión, no creo que la entrada $f(n) = BB_{\alpha(n)}(n)$ que se ha dado en el post original cumple con las reglas del concurso establecidas en el post original.

........

También he pasado algún tiempo pensando en la pregunta principal de este post, es decir, ¿cuál es la mejor estrategia para ganar un concurso de números más grandes? Después de estudiar una serie de casos (que espero escribir en algún momento), he llegado a la conclusión de que sólo hay tres tipos de concursos de números más grandes:

1. Aquellos en los que gana quien tiene el papel (ligeramente) más grande para escribir.
2. Aquellos en los que gana quien tiene más fe en los grandes axiomas cardinales (verdaderos).
3. Los que no están bien definidos como concursos matemáticos, sino que se plantean cuestiones filosóficas.

El primer tipo de concurso puede juzgarse normalmente en un plazo razonable, mientras que el segundo tipo de concurso puede juzgarse a menudo en un plazo irrazonable. El tercer tipo no se puede juzgar en absoluto.

El ejemplo más sencillo es el Concurso del Castor Ocupado: Dada una cantidad (razonablemente grande) de $n$ el reto es escribir una máquina de Turing en $n$ símbolos, y el ganador es el que tiene el mayor tiempo de ejecución (y por lo tanto es la mejor aproximación a $BB(n)$ ). La estrategia óptima es ésta:

1. Elige un axioma cardinal grande $\kappa$ que crees que es $\omega$ -consistente.

2. Introduzca el siguiente programa en el concurso:

   Por cada $\sigma\leq 3\uparrow\uparrow\uparrow 3$ (

   Para cada máquina de Turing $m$ del número de Gödel $\leq 3\uparrow\uparrow\uparrow 3$ (

   Si $\sigma$ es el número de Gödel de una prueba en $ZFC+\kappa$ que $m$ se detiene(

   Ejecutar $m$ )))

Esencialmente, lo que hace esta estrategia es "ejecutar todas las estrategias que tu oponente pueda estar utilizando y que puedas demostrar que se detienen". Si tu oponente es lo suficientemente honesto como para no presentar ninguna entrada que no crea que se detendrá, y no cree ninguna declaración matemática que no pueda ser probada en un sistema formal de fuerza de consistencia $\leq ZFC+\kappa$ Entonces ganarás. Así que este es un concurso de tipo 2.

Una modificación obvia de este concurso sería permitir sólo las entradas que se detengan de forma demostrable dentro de algún sistema formal, por ejemplo. $\Sigma = PA$ . (La prueba de detención debe presentarse con la entrada, ya que de otro modo el requisito es trivial, ya que todo programa que se detiene, se detiene de forma demostrable en PA). Entonces la mejor estrategia es fijar un gran $n$ considerar el sistema formal $\Sigma(n)$ que es lo mismo que PA, excepto que sólo las declaraciones de con $\leq n$ se permiten cuantificadores anidados en las pruebas de los teoremas. Entonces $\Sigma(n)$ se puede demostrar que $\omega$ -consistente en PA, aunque la longitud de la prueba de $\omega$ -la consistencia aumenta a medida que $n\to\infty$ . Así que sólo tienes que reemplazar $ZFC+\kappa$ por $\Sigma(n)$ en la estrategia anterior; ahora esa estrategia se detiene de forma demostrable dentro de PA. Así que mientras su $n$ es mayor que el de tu oponente $n$ Entonces, tú ganas. Así que este es un concurso de tipo 1.

La publicación original parece ser un concurso de números más grandes del tipo 3...

Answer 4

Esto no es una respuesta, pero es demasiado largo para un comentario.

No creo que los ordinales computables estén suficientemente bien definidos para la función $f(n)$ para trabajar. Supongamos que me das un mapeo del sistema { $0,1$ } $^* $ en los ordinales computables. Te daré un sistema, que es tu sistema junto con un nuevo símbolo, $2$ que representa el ordinal más pequeño que no se puede definir en el sistema. Entonces puedo mapear los números { $0,1,2$ } $^* $ de nuevo en { $0,1$ } $^*$ mi sistema llega a un ordinal computable que no está definido en tu sistema, e incluso lo define con longitud 2.

Así que los ordinales computables son un concepto que tiene sentido, pero es imposible tener una única codificación que te dé todos ellos. Por lo tanto, no veo cómo su función $f$ que se define con la frase

A continuación, dejemos que $\alpha(n)$ sea el mayor ordinal computable que puede definirse (en el sentido anterior) por una máquina de Turing con un máximo de $n$ estados.

obras. Deberías ser capaz de conseguir una máquina de Turing con un oráculo que corresponda a cualquier ordinal computable, pero ahí se acaba todo.

Answer 5

Tengo otra pregunta que es demasiado larga para que quepa en un comentario: ¿cómo sabes siquiera que $f(n)$ está aumentando?

Si tienes dos máquinas de Turing $M$ y $M'$ que realizan el mismo ordinal $\alpha$ no hay ninguna garantía (por lo que veo) de que $BB_\alpha^M(n) = BB_\alpha^{M'}(n)$ porque (si $\alpha > \omega$ ) la máquina de Turing que calcula $BB_\alpha^M$ debe utilizar la codificación definida por $M$ para indexar en ordinales menores que $\alpha$ . Con $M$ y $M'$ puede que ni siquiera exista un mapa computable a partir del índice generado por $M$ al índice generado por $M'$ . Se puede calcular este mapa utilizando $BB_\alpha^M$ pero no veo cómo hacerlo. Así, $BB_\alpha(n)$ no parece estar bien definido; es necesario especificar la codificación en ordinales menores que $\alpha$ para que esté bien definida. Por lo tanto, aunque $\alpha > \beta$ no está claro que $BB^M_\alpha(n)$ crece más rápido que $BB^{M'}_\beta(n)$ . Es posible que haya algunos ordinales computables en los que la función índice sea tan complicada que no se pueda utilizar para calcular nada útil.

Debería poder solucionar esto definiendo $f(n)$ para ser $BB_\alpha^M(n)$ para la máquina de Turing $M$ con $n$ estados para que $BB_\alpha^M(n)$ toma el valor máximo sobre todas esas máquinas de Turing.

ACTUALIZACIÓN: y ahora tengo lo que puede ser una respuesta a la pregunta de Scott. ¿Hay alguna razón para tener la máquina de Turing $M$ que define el oráculo para $\alpha$ ser una máquina Turing de vainilla. ¿No podrías dejar que tenga acceso a un oráculo para BB, también. De esta manera, se pueden definir clases utilizando máquinas como $T_\alpha^{M_\beta^{M'}}$ . Ahora, deja que $f(n)$ sea el valor máximo de $BB_\alpha^M(n)$ donde $M$ es una máquina definida de esta manera recursiva utilizando $n$ símbolos.

Pregunta: ¿se pueden definir así ordinales que sean estrictamente mayores que cualquier ordinal computable? ¿O esto sólo define la misma clase de ordinales de formas mucho más complicadas?