¿Cuál es el de más rápido crecimiento total computable función se puede describir en unas pocas líneas?

Question

¿Cuál es el de más rápido crecimiento total computable función se puede describir en unas pocas líneas? Bueno, no necesariamente el más rápido - me gustaría saber hasta qué punto un ingenioso matemático puede ir con sólo un par de líneas, y lo sistemático de los enfoques existentes para ello.

Cómo más se puede ir si tenemos la restricción de la computabilidad se levanta?

Answer 1

La mayoría de rápido crecimiento de funciones se construyen mediante un esquema recursivo análoga a la bien conocida función de Ackermann - es decir, en varias ocasiones se itera una función y, a continuación, diagonalizes. Por lo tanto la iteración, además de los rendimientos de la multiplicación, que reiteró los rendimientos de la exponenciación, que iterada rendimientos tetration, etc. Diagonalizing el resultado secuencia de funciones se obtiene un crecimiento más rápido de la función de Ackermann - que sí puede ser, sucesivamente, se itera, diagonalized, etc. Paul du Bois-Reymond descubierto diagonalización en las tasas de crecimiento de las funciones (las"órdenes de infinito") en 1875, mucho antes de que el Cantor mejor conocido redescubrimiento (1891), empleado para mostrar $|2^S| > |S|$.

Prueba teóricos uso análogo esquemas recursivos para la construcción de los sistemas de notación para los números ordinales - que se emplean para medir la fuerza de la lógica de los sistemas. Las funciones y los números anotados por tales medios (ya sea finito o infinito) tremendamente enano aquellos que se producen en la mayoría de todas las otras ramas de las matemáticas. Por lo tanto le recomiendo que consulte la literatura en el ordinal de los sistemas de notación.

A continuación están algunas de exposición referencias sobre temas relacionados (a partir de una antigua lesión.matemáticas post).

[Ruc] Rucker, Rudy. El infinito y La Mente, 1995, 342 pp. Princeton U. Pr.

[Spe] Spencer, Joel. Los grandes números y no demostrable teoremas, Amer. De matemáticas. Mensual, Diciembre De 1983, 669-675.

[Smo] Smorynski, Craig (los tres trabajos se reproducen en [HFR])
Algunos de rápido crecimiento de las funciones, de las Matemáticas. Intelligencer, 2 de 1980, 149-154.
Las Variedades Arbóreas Experiencia, Matemáticas. Intelligencer, 4 de 1982, 182-188.
"Gran" Noticia " de Arquímedes a Friedman, Avisos de Amer. De matemáticas. Soc. 30 de 1983, 251-256.

[Kol] Kolata, Gina. ¿El teorema de Gödel de la materia de matemáticas? La ciencia 218 11/19/1982, 779-780; reimpreso en [HFR]

[Sim] Simpson, Stephen G. Improbable teoremas y de rápido crecimiento de funciones, Contemp. De matemáticas. 65 1987, 359-394.

[HFR] Harrington, L. A. et.al. (editores) Harvey Friedman Investigación sobre los Fundamentos de la Matemática, Elsevier 1985.

Answer 2

Para un buen crecimiento rápido de la función, considere lo siguiente:

Dado árboles arraigados $S$ $T$ cuyos vértices son etiquetados de $\{1,2,\cdots,k\}$, definir una brecha de incrustación como una etiqueta de la preservación de la incrustación $h$ $S$ a $T$ que satisface la siguiente: dados $u$, $v$ los vértices de $S$ tal que $v$ es el hijo de $u$. Para cualquier vértice $w$ $T$ que reside entre la $h(u)$ y $h(v)$, $l(w) \ge l(h(v))$.

Dada esta definición, definir $ETree(k)$ a ser el más largo de la secuencia de $T_i$ de los árboles de raíces etiquetado de $\{1,2,\cdots,k\}$ tal que $T_i$ no tiene más de $i$ vértices, y para el no $i < j$ es que hay una brecha de incrustación de $T_i$ a $T_j$.

La anterior construcción es debido a Harvey Friedman. Él demostró que no es tal secuencia podría ser infinito (es decir, que arraigados etiquetado de los árboles están bien cuasi-ordenado en virtud de la brecha de incrustación de objetos), y se deduce de Koenig del Árbol Lema de que hay una larga secuencia de este.

La función de $ETree(k)$ crece muy rápido. Crece a la tasa de $F_{\psi_{\Omega_1} (\Omega_\omega)} (k)$. (Buscar el rápido crecimiento de la jerarquía.)

También se puede obtener de crecimiento extremadamente rápido de funciones mediante ordinal jerarquías. Deje $I(a)$ $a$'th débilmente inacessible cardenal. Considere lo siguiente: (aquí se $a,b,c,d,e$ son ordinales, $\phi$ es el Veblen función, $C_n(a,b)$ son conjuntos de números ordinales, $\psi$ $f$ son funciones de los números ordinales.)

$C_0(a,b) = b \cup {0}$

$C_{n+1}(a,b) = \{c+d, \phi(c,d), \aleph_c, I(c), \psi(e,d), f(e,c,d) | c,d,e \in C_n(a,b), e < a\}$

$C(a,b) = \cup C_n(a,b)$

$f(a,n,b) =$ más grande finito ordinal en $C_n(a,b)$

$\psi(a,b) = b$'th ordinal tal que $b \notin C(a,b)$

Entonces, por ejemplo, $f(I(I(I(I(0)))),x,x)$ es un crecimiento extremadamente rápido de la función, mucho más rápido que $ETree$. Para ayudar a entender esta construcción, consulte "Ordinal colapso de función" en la wikipedia. Si que es todavía confuso, mira en

http://math.ucr.edu/home/baez/week236.html

para una introducción a los números ordinales, y

http://groups.google.com/group/sci.math/browse_thread/thread/b4b2769c6359b3e9/5317b10cbf60196

para una descripción de cómo los ordinales pueden ser utilizados para definir los grandes números.

EDIT: tal vez algo más de explicación es necesaria. $C(a,b)$ es el conjunto más pequeño de números ordinales que contiene todos los números ordinales menos de $b$ $0$ y cerrado bajo las operaciones enumeradas en la segunda línea. La definición puede parecer circular, pero es bien definida por inducción en $a$;$f(c,n,b)$$\psi(c,b)$$c < a$, definimos $C_n(a,b)$, y dado $C_n(a,b)$, definimos $f(a,n,b)$$\psi(a,b)$.

Algunos análisis de $f(a,n,b)$:

$f(0,0,b)$ es el más grande finito ordinal en $C_0(0,b) = b$,$b-1$.

$f(0,1,b)$ $2(b-1)$ si $b \ge 2$, de lo contrario es $\phi(0,0) = 1$.

$f(0,n,b)$ $2^{b-1}$ si $b \ge 2$, de lo contrario es $2^{n-1}$

$f(1,0,b)$ es de nuevo $b-1$ si $b \ge 1$, $0$ si $b = 0$

$f(1,1,b)$ $2^{b-1} (b-1)$ si $b \ge 2$ lo contrario es $1$

$f(1,n,b) > Tower_n (b-1) > 2\uparrow\uparrow n$ $b \ge 2$

$f(2,n,b) > 2\uparrow\uparrow\uparrow n$ $b \ge 2$

$f(m,n,b) > 2 \uparrow^{m+1} n$ $b \ge 2$

$f(\omega,0,b) = b-1$ $b \ge 2$

$f(\omega,1,b) = f(b-1,b-1,b-1) \ge 2 \uparrow^{b}(b-1)$ $b \ge 2$

$f(\omega,2,b) = f(f(\omega,1,b),f(\omega,1,b),f(\omega,1,b)) \ge 2 \uparrow^{2 \uparrow^b (b-1)}(2 \uparrow^b (b-1))$

$f(\omega,n,b)$ es la función de $f(x,x,x)$ aplicado $n$ veces a partir de $b-1$, que es mayor que $F_{\omega+1}(n)$ donde $F$ es el rápido crecimiento de la jerarquía.

$F(\omega+1,n,b)$ es la función de $f(\omega,x,x)$ aplicado $n$ veces a partir de $b-1$, que es mayor que $F_{\omega+2}(n)$.

Cada vez que añadimos $1$$a$, tenemos que ir a una función que se repite la anterior $n$ veces; cada vez que aumentar a un ordinal límite, nos diagonalize más de las funciones anteriores. Así que la tarea se convierte en definir muy grande contables de los números ordinales.

Answer 3

No sé si es el más rápido, pero históricamente la función de Ackermann fue la primera (afaik):

$\qquad A(m, n) =\begin{cases}n+1 & \mbox{if } m = 0 \\A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.\end{cases}$

Se generaliza la idea de que $+$, $\cdot$, $\exp$ y así en forma natural a una serie de operadores; $A$ excedes todas ellas por el control de la apilamiento nivel en el segundo parámetro.

Se ha demostrado que la $A$ (o más bien $A(n,n)$) no es primitiva recursiva, demostrando que crece más rápido que cualquier primitiva de la función recursiva, incluyendo todas las funciones exponenciales.

Answer 4

Así, por ejemplo:

Regla 1 (sólo 2 entradas):

{a,b} = a^b

Regla 2 (2ª entrada es 1):

{a,1 #} = a

Regla 3 (la última entrada es 1):

{#,1} = {#}

Regla 4 (cadena de la 1 de la 3ª entrada a la enésima):

{a,b,1,1,...,1,1,c #} = {a,a,a,a,...,a,{a,b-1,1,1,...,1,1,c #},c-1 #}

Regla 5 (de lo contrario):

{a,b,c #} = {a,{a,b-1,c #},c-1 #}

Aquí # denota sin cambios el resto de la matriz. Entonces mi función es f(n) = {n,n,n,...,n,n,n}.