Joc de la hidra

En matemàtiques, específicament en teoria de grafos i en teoria de números, un joc de la hidra és un joc matemàtic iterativo que es presenta com un videojoc d'un jugador. Es juga sobre un arbre matemàtic cridat "hidra", i l'objectiu del jugador és "matar" a la hidra eliminant les seues nodos ("caps") una per una mentres la hidra s'expandix simultàneament (açò s'assembla a una batalla entre Hércules i la Hidra de Lerna, d'ahí el nom del joc). Les regles del joc permeten que el jugador guanye finalment, pero el número de passos necessaris per a alcançar l'objectiu creix molt ràpidament a mida que aumenta el tamany de l'arbre inicial, per lo que el joc pot usar-se per a generar números grans o transfinitos o per a demostrar la solidea de certes teories matemàtiques.

A diferència de les seues contrapartes combinatòries com TREE i SCG, no es requerix busca per a calcular estos valors de la funció de ràpit creiximent, simplement cal seguir aplicant la regla de transformació a l'arbre fins que el joc indique que s'ha detingut.

Introducció

Un joc de hidra simple consistix en una seqüència de iteraciones que modifiquen la "hidra", un grafo finito en forma d'arbre arrelat en raïl $R$. Cada iteración s'etiqueta en un número seqüencial $n$, començant en 1, i consta de dos passos:

1. El jugador selecciona un nodo d'un full $x$ de l'arbre en cada tanda.
2. S'elimina el nodo full $x$. Siga $a$ pare de $x$. Si $a=R$, es retorna a l'etapa 1. De lo contrari, si $a\ne R$, siga $b$ el pare de $a$. A continuació, es creen $n$ nodos full com a fills de $b$, de manera que els nous nodos apareguen despuix de qualsevol fill existent de $b$ durant un recorregut en postorden (visualment, estos nous nodos apareixerien a la dreta de qualsevol fill existent). Després, es retorna a l'etapa 1.

Encara que la hidra pot créixer en un número illimitat $n$ de fulls en cada tanda, el joc terminarà en un número finito de passos: si $d$ és la major distància entre la raïl i el full, i $w$ el número de fulls a esta distància, per inducció en $d$ es pot demostrar que el jugador sempre matarà a la hidra. Si $d=1$, llevar els fulls mai pot fer que la hidra creixca, per lo que el jugador guanya despuix de $w$ tandes. Per a $d$ general, consideren-se dos tipos de moviments: aquells que involucren un full a una distància menor que $d$ de la raïl, i aquells que involucren un full a una distància d'exactament $d$. Ya que els moviments del primer tipo són idèntics als moviments en un joc en profunditat $d-1$, l'hipòtesis d'inducció indica que, despuix d'un número finito de dits moviments, el jugador no tindrà més remei que elegir un full en profunditat $d$. Cap moviment introduïx nous nodos a esta profunditat, per lo que tot este procés solament pot repetir-se fins a $w$ voltes, despuix de la qual cosa no queden més fulls en profunditat $d$ i el joc ara té una profunditat (com a màxim) de $d-1$. Invocant de nou l'hipòtesis d'inducció, es té que el jugador deu guanyar finalment.

Si ben açò demostra que el jugador guanyarà finalment, pot dur molt temps. Com a eixemple, considere's el següent algoritme per als moviments del jugador i les respostes de la hidra. Elegir el full més a la dreta (és dir, el full més nou que estarà en el nivell més propenc a la raïl) i establir $n=1$ la primera volta, $2$ la segona volta, i aixina successivament, sempre incrementant $n$ en un. Si una hidra té una sola branca de llongitut $y$, llavors per a $y=1$, la hidra mor en un sol pas, mentres que mor en tres passos si $y=2$. Es requerixen 11 passos per a $y=3$. Es requerixen 1114111 passos per a $y=4$. $y=5$ s'ha calculat en exactitut. Sean $F(x)=2^x\cdot (x+2)-1$ i $F^n(x)$ $F$ anidados n voltes. Llavors $HYDRA(5)=$ $2\cdot F^{F^2(3)+1}(F^2(3)+1)+1=$ $2\cdot F^{22539988369408}(22539988369408)+1$.

Tots els passos del senzill joc de la hidra en i= 3

Solució general

La solució general al joc de la hidra (jugat en l'algoritme de la secció anterior) és la següent:

Siga $F_i(x)$ el número de passos necessaris per a decrementar un cap de profunditat n quan tots els caps més propenques a les raïls són singulars (no hi ha més branques "dretes").

Llavors, $F_{i+1}(x)=F_i^x(x+1)$ i $F_1(x)=2\cdot (x+1)-1=2x+1$.

La resposta a $hydra(n)$ és:

$F_1(F_2(F_3(\dots F_{n-1}(F_n(1))\dots )))$

La taxa de creiximent d'esta funció és més ràpida que la de la funció estàndar en la jerarquia de ràpit creiximent, ya que $F_i(x)$ creix a la mateixa taxa que la jerarquia de ràpit creiximent, i la solució és el n-ésimo anidamiento de $F_i(x)$.

Vore també

• Teorema de Goodstein