Juego de hidra

Juego matemático iterativo para un solo jugador que se juega en un árbol matemático.

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 juega en un árbol matemático llamado hidra , donde, por lo general, el objetivo es cortar las "cabezas" de la hidra mientras la hidra se expande simultáneamente. Los juegos de hidra se pueden utilizar 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: uno simplemente debe seguir aplicando la regla de transformación al árbol hasta que el juego indique que debe detenerse.

Introducción

Un juego de hidra simple se puede definir de la siguiente manera:

• Una hidra es un árbol con raíces finitas, que es un grafo conectado sin ciclos y un nodo específico designado como la raíz del árbol. En un árbol con raíces, cada nodo tiene un solo padre (con excepción de la raíz, que no tiene padre) y un conjunto de hijos, a diferencia de un árbol sin raíces donde no hay una relación padre-hijo y simplemente nos referimos a las aristas entre los nodos. ${\displaystyle R}$
• El jugador selecciona un nodo hoja del árbol y un número natural durante cada turno. Un nodo hoja puede definirse como un nodo sin hijos o un nodo de grado 1 que no es . ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle R}$
• Eliminar el nodo hoja . Sea el padre de . Si , volver a la etapa 2. De lo contrario, si , sea el padre de . A continuación, crear nodos hoja como hijos de de manera que los nuevos nodos aparezcan después de cualquier hijo existente de durante un recorrido de orden posterior (visualmente, estos nuevos nodos aparecerían al lado derecho de cualquier hijo existente). A continuación, volver a la etapa 2. ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle a=R}$ ${\displaystyle a\neq R}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle b}$

Aunque la hidra puede crecer un número ilimitado de hojas en cada turno, el juego acabará finalmente en un número finito de pasos: si es la distancia máxima entre la raíz y la hoja, y el número de hojas a esta distancia, la inducción sobre se puede utilizar para demostrar que el jugador siempre matará a la hidra. Si , quitar las hojas nunca puede hacer que la hidra crezca, por lo que el jugador gana después de los turnos. Para el general , consideramos dos tipos de movimientos: los que implican una hoja a una distancia menor que desde la raíz, y los que implican una hoja a una distancia de exactamente . Dado que los movimientos del primer tipo también son idénticos a los movimientos en un juego con profundidad , 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 opción que elegir una hoja a una profundidad . Ningún movimiento introduce nuevos nodos a esta profundidad, por lo que todo este proceso solo puede repetirse hasta veces, después de las cuales no hay más hojas a la profundidad y el juego ahora tiene profundidad (como máximo) . Invocando de nuevo la hipótesis de inducción, encontramos que el jugador debe ganar finalmente en general. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle d}$ ${\displaystyle d=1}$ ${\displaystyle w}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle d}$ ${\displaystyle d-1}$

Si bien esto demuestra que el jugador ganará eventualmente, puede llevar mucho tiempo. Como ejemplo, considere el siguiente algoritmo. 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 la primera vez, la segunda vez, y así sucesivamente, siempre aumentando en uno. Si una hidra tiene una rama de longitud única, entonces para , la hidra muere en un solo paso, mientras que muere en tres pasos si . Hay 11 pasos necesarios para . Hay 1114111 pasos necesarios para . ^[2] se ha calculado exactamente. ^[3] Sea y anidados n veces. Entonces . ${\displaystyle n=1}$ ${\displaystyle 2}$ ${\displaystyle n}$ ${\displaystyle y}$ ${\displaystyle y=1}$ ${\displaystyle y=2}$ ${\displaystyle y=3}$ ${\displaystyle y=4}$ ${\displaystyle y=5}$ ${\displaystyle F(x)=2^{x}\cdot (x+2)-1}$ ${\displaystyle F^{n}(x)}$ ${\displaystyle F}$ ${\displaystyle HYDRA(5)=2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=2\cdot F^{22539988369408}(22539988369408)+1}$

Todos los pasos del sencillo juego de la hidra con y = 3

Solución general

La solución general del juego de la hidra es la siguiente: ^[4]

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

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

La respuesta es: ${\displaystyle hydra(n)}$ ${\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 de crecimiento rápido estándar , ya que solo crece a la tasa de la jerarquía de crecimiento rápido , y la solución es la anidación n de . ${\displaystyle F_{i}(x)}$ ${\displaystyle F_{i}(x)}$

Hidras de Kirby-Paris y Buchholz

La hidra de Kirby-Paris se define alterando la cuarta regla de la hidra definida anteriormente.

4 _KP : Supongamos que es el padre de if . Adjuntamos copias del subárbol con raíz a la derecha de todos los demás nodos conectados a . Regresamos a la etapa 2. ^[5] ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\neq R}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$

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

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

1. Una hidra es un árbol etiquetado con raíces finitas. La raíz debe estar etiquetada como . Etiqueta todos los nodos adyacentes a la raíz (es importante para garantizar que siempre termine) y todos los demás nodos con un número entero no negativo o . ${\displaystyle R}$ ${\displaystyle 0}$ ${\displaystyle \omega }$
2. Elija un nodo de hoja y un número natural en cada etapa. ${\displaystyle x}$ ${\displaystyle n}$
3. Quitar la hoja . Sea el padre de . No ocurre nada más si . Volver a la etapa 2. ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle a=R}$
4. Si la etiqueta de es , supongamos que es el padre de . Adjunte copias del subárbol con raíz a la derecha de todos los demás nodos conectados a . Regrese a la etapa 2. ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$
5. Si la etiqueta de x es , reemplácela por . Regrese a la etapa 2. ${\displaystyle \omega }$ ${\displaystyle n+1}$
6. Si la etiqueta de es un entero positivo , baje por el árbol buscando un nodo con una etiqueta . Tal nodo existe porque todos los nodos adyacentes a la raíz están etiquetados como . Tome una copia del subárbol con raíz . Reemplace con este subárbol. Sin embargo, vuelva a etiquetar (la raíz de la copia del subárbol) con . Llame al equivalente de en el subárbol copiado (por lo que es a como es a ), y vuelva a etiquetarlo como 0. Vuelva a la etapa 2. ^[8] ${\displaystyle x}$ ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle <u}$ ${\displaystyle 0}$ ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle u-1}$ ${\displaystyle x}$ ${\displaystyle x'}$ ${\displaystyle x}$ ${\displaystyle x'}$ ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle (x')}$

Sorprendentemente, aunque la hidra puede crecer enormemente en altura, esta secuencia siempre termina. ^[9]

Más sobre las hidras KP

Para las hidras de Kirby–Paris, las reglas son simples: comienza con una hidra, que es un árbol con raíz desordenado y sin etiquetar . En cada etapa, el jugador elige un nodo de hoja para cortar y un entero no negativo . Si  es un hijo de la raíz , se elimina del árbol y no sucede nada más en ese turno. De lo contrario,  sea el padre de y  sea el padre de . Elimine del árbol y luego agregue  copias del modificado  como hijos a . El juego termina cuando la hidra se reduce a un solo nodo. ${\displaystyle T}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle c}$ ${\displaystyle g}$ ${\displaystyle p}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle g}$

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

Esto podría expresarse alternativamente utilizando cadenas de corchetes:

• Comience con una secuencia finita de corchetes como . ${\displaystyle (()(()(())((()))))}$
• Elija un par vacío y un número entero no negativo . ${\displaystyle ()}$ ${\displaystyle n}$
• Elimina el par y, si su padre no es el par más externo, toma su padre y añade  copias de él. ${\displaystyle n}$

Por ejemplo, con , . A continuación se muestra una lista de valores de : ${\displaystyle n=3}$ ${\displaystyle (()(()\mathbf {()} ))\implies (()(())(())(())(()))}$ ${\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)}$

Más sobre las hidras de Buchholz

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 crecimiento rápido , que eventualmente domina todas las funciones recursivas totales demostrables. Es una extensión de las hidras de Kirby-Paris. Lo que usamos para obtener una función de crecimiento rápido 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, tiene una tasa de crecimiento mucho mayor de : ${\displaystyle BH(n)}$ ${\displaystyle BH(n)}$ ${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)}$

• ${\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 )}$

Véase también

• Teorema de Goodstein

Referencias

1. Kirby, Laurie; Paris, Jeff. "Resultados de independencia accesibles para la aritmética de Peano" (PDF) . Departamento de lógica aplicada . Consultado el 4 de septiembre de 2021 .
2. "El juego de la Hidra - Numberphile". 18 de abril de 2024.
3. "Hidra(5)".
4. "El juego de la Hidra resuelto".
5. "Hidras". agnijomaths.com . Consultado el 5 de septiembre de 2021 .
6. Hamano, Masahiro; Okada, Mitsuhiro (1995). "Una relación entre el juego de la hidra de reducción de pruebas de Gentzen, el juego de la hidra de Kirby-Paris y el juego de la hidra de Buchholz (informe preliminar)*" (PDF) . Instituto de Investigación de Ciencias Matemáticas, Universidad de Kioto . Consultado el 4 de septiembre de 2021 .
7. Ketonen, Jussi; Solovay, Robert (1981). "Funciones de Ramsey de rápido crecimiento". Anales de Matemáticas . 113 (2): 267–314. doi :10.2307/2006985. ISSN  0003-486X. JSTOR  2006985.
8. Buchholz, Wilfried (27 de noviembre de 1984). "Un resultado de independencia para Π11 - CA + BI" (PDF) . Universidad Ludwig-Maximilians de Múnich . Consultado el 4 de septiembre de 2021 .
9. Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "Una prueba de independencia directa del juego de la Hidra de Buchholz en árboles etiquetados finitos". Archivo de Lógica Matemática . 37 (2): 67–89. doi :10.1007/s001530050084. ISSN  1432-0665. S2CID  40113368.
10. Carlucci, Lorenzo (7 de mayo de 2003). "Una nueva prueba teórica de la independencia del teorema de la Hidra de Kirby-Paris". Ciencias Informáticas Teóricas . 300 (1–3): 365–378. doi :10.1016/S0304-3975(02)00332-8. ISSN  0304-3975.

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

Enlaces externos

• El juego de la hidra
• Hércules y la hidra
• Matar a la hidra matemática de PBS Infinite Series