Juego de la Hidra

En matemáticas, específicamente en teoría de grafos y teoría de números , un juego de hidra es un juego matemático iterativo para un solo jugador que se desarrolla en un árbol matemático llamado "hidra", donde el objetivo del jugador es "matar" a la hidra eliminando sus nodos ("cabezas") uno por uno mientras la hidra se expande simultáneamente (esto se asemeja a una batalla entre Hércules y la Hidra de Lerna , de ahí su nombre). Las reglas del juego permiten que el jugador finalmente gane, pero el número de pasos necesarios para alcanzar el objetivo crece muy rápidamente a medida que aumenta el tamaño del árbol inicial, por lo que el juego puede usarse para generar números grandes u ordinales infinitos o para demostrar la solidez de ciertas teorías matemáticas. ^{[ 1 ]}

A diferencia de sus contrapartes combinatorias como TREE y SCG , no se requiere ninguna búsqueda para calcular estos valores de función de rápido crecimiento; simplemente hay que seguir aplicando la regla de transformación al árbol hasta que el juego indique que hay que parar.

Un juego de hidra simple consiste en una secuencia de iteraciones que modifican la hidra , un grafo de árbol finito con raíz.${\displaystyle R}$Cada iteración está etiquetada con un número secuencial.${\displaystyle n}$, comenzando con 1, y consta de dos pasos:

1. El jugador selecciona un nodo hoja.${\displaystyle x}$del árbol durante cada turno.
2. Eliminar el nodo hoja${\displaystyle x}$. Dejar${\displaystyle a}$ser${\displaystyle x}$padre de . Si${\displaystyle a=R}$, regresar a la etapa 1. De lo contrario, si${\displaystyle a\neq R}$, dejar${\displaystyle b}$ser el padre de${\displaystyle a}$. Luego crea${\displaystyle n}$nodos hoja como hijos de${\displaystyle b}$de tal manera que los nuevos nodos aparecerían después de cualquier hijo existente de${\displaystyle b}$durante un recorrido en postorden (visualmente, estos nuevos nodos aparecerían a la derecha de cualquier nodo hijo existente). Luego, regrese a la etapa 1.

Aunque la hidra pueda crecer en un número ilimitado${\displaystyle n}$de hojas en cada turno, el juego eventualmente terminará en un número finito de pasos: si${\displaystyle d}$es la mayor distancia entre la raíz y la hoja, y${\displaystyle w}$el número de hojas a esta distancia, inducción en${\displaystyle d}$puede usarse para demostrar que el jugador siempre matará a la hidra. Si${\displaystyle d=1}$, quitar las hojas nunca puede hacer que la hidra crezca, por lo que el jugador gana después${\displaystyle w}$turnos. Para general${\displaystyle d}$, consideramos dos tipos de movimientos: aquellos que involucran una hoja a una distancia menor que${\displaystyle d}$desde la raíz, y aquellos que involucran una hoja a una distancia de exactamente${\displaystyle d}$. Dado que los movimientos del primer tipo también son idénticos a los movimientos en un juego con profundidad${\displaystyle d-1}$La hipótesis de inducción nos dice que después de un número finito de tales movimientos, el jugador no tendrá más remedio que elegir una hoja en profundidad.${\displaystyle d}$Ningún movimiento introduce nuevos nodos a esta profundidad, por lo que todo este proceso solo puede repetirse hasta${\displaystyle w}$veces, después de lo cual ya no hay hojas en profundidad${\displaystyle d}$y el juego ahora tiene profundidad (como mucho)${\displaystyle d-1}$Invocando nuevamente la hipótesis de inducción, encontramos que el jugador eventualmente debe ganar en general.

Si bien esto demuestra que el jugador eventualmente ganará, puede llevar mucho tiempo. Como ejemplo, considere el siguiente algoritmo tanto para los movimientos del jugador como para las respuestas de la hidra. Elija la hoja más a la derecha (es decir, la hoja más nueva que estará en el nivel más cercano a la raíz) y establezca${\displaystyle n=1}$la primera vez,${\displaystyle 2}$la segunda vez, y así sucesivamente, siempre aumentando${\displaystyle n}$por uno. Si una hidra tiene un solo${\displaystyle y}$-rama de longitud, luego para${\displaystyle y=1}$, la hidra muere en un solo paso, mientras que muere en tres pasos si${\displaystyle y=2}$. Se requieren 11 pasos para${\displaystyle y=3}$. Se requieren 1114111 pasos para${\displaystyle y=4}$.${\displaystyle y=5}$se ha calculado exactamente. ^{[ 2 ]} Sea${\displaystyle F(x)=2^{x}\cdot (x+2)-1}$y${\displaystyle F^{n}(x)}$ser${\displaystyle F}$anidado n veces. Entonces${\displaystyle HYDRA(5)=}$${\displaystyle 2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=}$${\displaystyle 2\cdot F^{22539988369408}(22539988369408)+1}$.

La solución general al juego de la hidra (jugado con el algoritmo de la sección anterior) es la siguiente: ^{[ 3 ]}

Dejar${\displaystyle F_{i}(x)}$denota el número de pasos necesarios para disminuir una cabeza de profundidad n cuando todas las cabezas más cercanas a las raíces son singulares (no hay más ramas "derechas").

Entonces${\displaystyle F_{i+1}(x)=F_{i}^{x}(x+1)}$y${\displaystyle F_{1}(x)=2\cdot (x+1)-1=2x+1}$.

La respuesta a${\displaystyle hidra(n)}$es: ${\displaystyle F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))}$

La tasa de crecimiento de esta función es más rápida que la jerarquía estándar de rápido crecimiento , ya que${\displaystyle F_{i}(x)}$por sí solo crece al ritmo de la jerarquía de rápido crecimiento , y la solución es el enésimo anidamiento de${\displaystyle F_{i}(x)}$.

La hidra de Kirby - París se define alterando la regla de la hidra simple definida anteriormente:

• Asumir${\displaystyle b}$es el padre de${\displaystyle a}$si${\displaystyle a\neq R}$. Adjuntar${\displaystyle n}$copias del subárbol con raíz${\displaystyle a}$a${\displaystyle b}$a la derecha de todos los demás nodos conectados a${\displaystyle b}$. Regresar a la etapa 2. ^{[ 4 ]}

En lugar de agregar solo hojas nuevas, esta regla agrega duplicados de un subárbol completo. Manteniendo todo lo demás igual, esta vez${\displaystyle y=1}$requiere${\displaystyle 1}$doblar,${\displaystyle y=2}$requiere${\displaystyle 3}$pasos,${\displaystyle y=3}$requiere${\displaystyle 37}$pasos y${\displaystyle y=4}$requiere más pasos que el número de Graham . La tasa de crecimiento de esta función es masiva , igual a${\displaystyle f_{\varepsilon _{0}}(n)}$en la jerarquía de rápido crecimiento, donde${\displaystyle \varepsilon _{0}}$es el número épsilon más pequeño .

Esta no es la hidra más poderosa. La hidra de Buchholz es una hidra más potente. ^{[ 5 ]} Implica un árbol etiquetado. La raíz tiene una etiqueta única (llámela${\displaystyle R}$), y cada otro nodo tiene una etiqueta que es un número entero no negativo o${\displaystyle \omega }$. ^{[ 6 ]}

1. Una hidra es un árbol etiquetado con raíces finitas. La raíz debe estar etiquetada.${\displaystyle R}$. Etiquete todos los nodos adyacentes a la raíz${\displaystyle 0}$(es importante asegurar que siempre termine) y cada otro nodo con un número entero no negativo o${\displaystyle \omega }$.
2. Elige un nodo hoja${\displaystyle x}$y un número natural${\displaystyle n}$en cada etapa.
3. Quitar la hoja${\displaystyle x}$. Dejar${\displaystyle a}$ser${\displaystyle x}$padre de. No sucede nada más si${\displaystyle a=R}$. Regresar a la etapa 2.
4. Si la etiqueta de${\displaystyle x}$es${\displaystyle 0}$, Asumir${\displaystyle b}$es el padre de${\displaystyle a}$. Adjuntar${\displaystyle n}$copias del subárbol con raíz${\displaystyle a}$a${\displaystyle b}$a la derecha de todos los demás nodos conectados a${\displaystyle b}$. Regresar a la etapa 2.
5. Si la etiqueta de x es${\displaystyle \omega }$, reemplácelo con${\displaystyle n+1}$. Regresar a la etapa 2.
6. Si la etiqueta de${\displaystyle x}$es un número entero positivo${\displaystyle u}$. baja por el árbol buscando un nodo${\displaystyle c}$con una etiqueta${\displaystyle <u}$. Dicho nodo existe porque todos los nodos adyacentes a la raíz están etiquetados${\displaystyle 0}$. Toma una copia del subárbol con raíz${\displaystyle c}$. Reemplazar${\displaystyle x}$con este subárbol. Sin embargo, vuelva a etiquetar.${\displaystyle x}$(la raíz de la copia del subárbol) con${\displaystyle u-1}$. Llama al equivalente de${\displaystyle x}$en el subárbol copiado${\displaystyle x'}$(entonces${\displaystyle x}$es a${\displaystyle x'}$como${\displaystyle c}$es a${\displaystyle x}$), y cámbiele la etiqueta.${\displaystyle (x')}$0. Regresa a la etapa 2. ^{[ 7 ]}

Sorprendentemente, aunque la hidra puede crecer enormemente, esta secuencia siempre termina. ^{[ 8 ]}

Para las hidras de Kirby-París, las reglas son sencillas: se empieza con una hidra, que es un árbol enraizado no ordenado y sin etiquetas.${\displaystyle T}$En cada etapa, el jugador elige un nodo hoja.${\displaystyle c}$cortar y un número entero no negativo${\displaystyle n}$. Si${\displaystyle c}$ es un hijo de la raíz${\displaystyle r}$, se elimina del árbol y no sucede nada más en ese turno. De lo contrario, deja${\displaystyle p}$ ser${\displaystyle c}$padre de y${\displaystyle g}$ ser${\displaystyle p}$padre de. Eliminar${\displaystyle c}$del árbol, luego agregar${\displaystyle n}$ copias de la versión modificada${\displaystyle p}$ como niños a${\displaystyle g}$El juego termina cuando la hidra se reduce a un solo nodo.

Para obtener una función de rápido crecimiento, podemos fijar${\displaystyle n}$, decir, ${\displaystyle n=1}$en el primer paso, entonces${\displaystyle n=2}$,${\displaystyle n=3}$y así sucesivamente, y decide una regla simple sobre dónde cortar, por ejemplo, elegir siempre la hoja más a la derecha. Luego, ${\displaystyle \operatorname {Hydra} (k)}$es el número de pasos necesarios para que el juego termine comenzando con un camino de longitud${\displaystyle k}$, es decir, una pila lineal de ${\displaystyle k+1}$nodos.${\displaystyle \operatorname {Hydra} (k)}$eventualmente domina todas las funciones recursivas que son demostrablemente totales en la aritmética de Peano, y es en sí misma demostrablemente total en${\displaystyle \mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})}$. ^{[ 9 ]}

Esto también podría expresarse utilizando cadenas de corchetes :

• Comience con una secuencia finita de corchetes como por ejemplo:${\displaystyle (()(()(())((()))))}$.
• Elige un par vacío${\displaystyle ()}$y un número entero no negativo${\displaystyle n}$.
• Elimina el par y, si su padre no es el par más externo, toma su padre y agrégalo. ${\displaystyle n}$copias del mismo.

Por ejemplo, con${\displaystyle n=3}$,${\displaystyle (()(()\mathbf {()} ))\implies (()(())(())(())(()))}$A continuación se muestra una lista de valores de${\displaystyle \operatorname {Hydra} (k)}$:

• ${\displaystyle \operatorname {Hydra} (0)=0}$
• ${\displaystyle \operatorname {Hydra} (1)=1}$
• ${\displaystyle \operatorname {Hydra} (2)=3}$
• ${\displaystyle \operatorname {Hydra} (3)=37}$
• ${\displaystyle \operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}}$
• ${\displaystyle \operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)}$
• ${\displaystyle \operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)}$

El juego de la hidra de Buchholz es un juego de hidra en lógica matemática, un juego para un solo jugador basado en la idea de cortar piezas de un árbol matemático. El juego de la hidra se puede utilizar para generar una función de rápido crecimiento.${\displaystyle BH(n)}$, que finalmente domina todas las funciones recursivas demostrablemente totales en${\displaystyle {\mathsf {ID}}_{\nu }}$, la jerarquía de teorías de definiciones inductivas iteradas . Es una extensión de las hidras de Kirby-Paris. Lo que usamos para obtener una función de rápido crecimiento es lo mismo que las hidras de Kirby-Paris, pero debido a que las hidras de Buchholz crecen no solo en ancho sino también en altura,${\displaystyle BH(n)}$tiene una tasa de crecimiento mucho mayor de${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)}$, el ordinal Takeuti–Feferman–Buchholz :

• ${\displaystyle BH(1)=0}$
• ${\displaystyle BH(2)=1}$
• ${\displaystyle BH(3)<f_{\varepsilon _{0}}(3)}$

Este sistema también se puede utilizar para crear una notación ordinal para ordinales infinitos, por ejemplo${\displaystyle \psi _{0}(\Omega _{\omega })=+0(\omega )}$.

• Teorema de Goodstein

 Este artículo incorpora texto de Komi Amiko, disponible bajo la licencia CC BY 4.0 .

• El juego de la hidra
• Hércules y la hidra
• Mata a la hidra matemática por la serie Infinite de PBS