En matemáticas, específicamente en teoría de grafos y en teoría de números, un juego de la hidra es un juego matemático iterativo que se presenta como un videojuego de un jugador. Se juega sobre un árbol matemático llamado "hidra", y el objetivo del jugador es "matar" a la hidra eliminando sus nodos ("cabezas") una por una mientras la hidra se expande simultáneamente (esto se asemeja a una batalla entre Hércules y la Hidra de Lerna, de ahí el nombre del juego). Las reglas del juego permiten que el jugador gane finalmente, 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 o transfinitos o para demostrar la solidez de ciertas teorías matemáticas.

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

Introducción Un juego de hidra simple consiste en una secuencia de iteraciones que modifican la "hidra", un grafo finito con forma de árbol enraizado con raíz . Cada iteración se etiqueta con un número secuencial , comenzando con 1, y consta de dos pasos: El jugador selecciona un nodo de una hoja del árbol en cada turno. Se elimina el nodo hoja . Sea padre de . Si , se regresa a la etapa 1. De lo contrario, si , sea el padre de . A continuación, se crean nodos hoja como hijos de , de manera que los nuevos nodos aparezcan después de cualquier hijo existente de durante un recorrido en postorden (visualmente, estos nuevos nodos aparecerían a la derecha de cualquier hijo existente). Luego, se regresa a la etapa 1.

Aunque la hidra puede crecer en un número ilimitado de hojas en cada turno, el juego terminará en un número finito de pasos: si es la mayor distancia entre la raíz y la hoja, y el número de hojas a esta distancia, por inducción en se puede 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 turnos. Para general, considérense dos tipos de movimientos: aquellos que involucran una hoja a una distancia menor que de la raíz, y aquellos que involucran una hoja a una distancia de exactamente . Dado que los movimientos del primer tipo son idénticos a los movimientos en un juego con profundidad , la hipótesis de inducción indica que, tras un número finito de dichos movimientos, el jugador no tendrá más remedio que elegir una hoja con profundidad . Ningún movimiento introduce nuevos nodos a esta profundidad, por lo que todo este proceso solo puede repetirse hasta veces, tras lo cual no quedan más hojas con profundidad y el juego ahora tiene una profundidad (como máximo) de . Invocando de nuevo la hipótesis de inducción, se tiene que el jugador debe ganar finalmente.

Si bien esto demuestra que el jugador ganará finalmente, puede llevar mucho tiempo. Como ejemplo, considérese el siguiente algoritmo para los movimientos del jugador y las respuestas de la hidra. Elegir 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 establecer la primera vez, la segunda vez, y así sucesivamente, siempre incrementando en uno. Si una hidra tiene una sola rama de longitud , entonces para , la hidra muere en un solo paso, mientras que muere en tres pasos si . Se requieren 11 pasos para . Se requieren 1114111 pasos para . se ha calculado con exactitud. Sean y anidados n veces. Entonces .

Solución general La solución general al juego de la hidra (jugado con el algoritmo de la sección anterior) es la siguiente:

Sea el número de pasos necesarios para decrementar 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, y .

La respuesta a es:

La tasa de crecimiento de esta función es más rápida que la de la función estándar con la jerarquía de rápido crecimiento, ya que crece a la misma tasa que la jerarquía de rápido crecimiento, y la solución es el n-ésimo anidamiento de .

Hidras de Kirby-París y Buchholz La hidra de Kirby-Paris se define modificando la regla de la hidra simple definida anteriormente:

Se asume que es el padre de si . Se adjuntan copias del subárbol con raíz a a la derecha de todos los demás nodos conectados a . Se regresa a la etapa 2.

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 turnos, requiere pasos, requiere pasos y requiere un número de pasos superior al número de Graham. La tasa de crecimiento de esta función es "masiva", igual a en la jerarquía de rápido crecimiento, donde es el número épsilon más pequeño.

Esta no es la hidra más poderosa. La hidra de Buchholz, que implica un árbol etiquetado, es todavía más potente. La raíz tiene una etiqueta única (denominada ), y cada uno de los demás nodos tiene una etiqueta que es un número entero o no negativo.

Una hidra es un árbol etiquetado con raíces finitas. La raíz debe etiquetarse como . Etiquétense todos los nodos adyacentes a la raíz como (importante para asegurar que siempre termine) y todos los demás nodos con un número entero no negativo o . Elíjase un nodo hoja y un número natural en cada etapa. Elimínese la hoja . Sea el padre de . No ocurre nada más si . Regrese a la etapa 2. Si la etiqueta de es , supóngase que es el padre de . Adjúntense copias del subárbol con raíz a a la derecha de todos los demás nodos conectados a . Regresar a la etapa 2. Si la etiqueta de x es , reemplácela por . Regresar a la etapa 2. Si la etiqueta de es un entero positivo , recórrase el árbol buscando un nodo con la etiqueta . Dicho nodo existe porque todos los nodos adyacentes a la raíz tienen la etiqueta . Tome una copia del subárbol con raíz . Reemplácese con este subárbol. Sin embargo, cambie la etiqueta de (la raíz de la copia del subárbol) a . Llamando al equivalente de en el subárbol copiado (de modo que es a como es a ), y cámbiale la etiqueta a 0. Volver a la etapa 2.

Sorprendentemente, aunque la hidra puede crecer enormemente, esta secuencia siempre se termina.

Más sobre las hidras de Kirby-Paris Para las hidras de Kirby-Paris, las reglas son sencillas: comienza con una hidra, que es un árbol enraizado no ordenado y sin etiquetar . En cada etapa, el jugador elige un nodo hoja para cortar y un entero no negativo . Si es hijo de la raíz , se elimina del árbol y no ocurre nada más en ese turno. De lo contrario, es el padre de , y es el padre de . Se elimina del árbol y luego se añaden copias de del modificado como hijos de . El juego termina cuando la hidra se reduce a un solo nodo.

Para obtener una función de rápido crecimiento, se puede fijar , por ejemplo, en el primer paso, luego , , y así sucesivamente, y decidir una regla simple para el corte, por ejemplo, elegir 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. finalmente domina a todas las funciones recursivas que son demostrablemente totales en la aritmética de Peano, y es demostrablemente total en .

Esto también podría expresarse usando cadenas de paréntesis:

Comiéncese con una secuencia finita de paréntesis como . Selecciónese un par vacío y un entero no negativo . Elimínese el par y, si su padre no es el par más externo, tome su padre y añada copias del mismo.

Por ejemplo, con , . A continuación, se muestra una lista de valores de :

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 usar para generar una función de rápido crecimiento , que finalmente domina a todas las funciones recursivas demostrablemente totales en , la jerarquía de teorías de definiciones inductivas iteradas. Es una extensión de las hidras de Kirby-París. El método que utilizamos para obtener una función de rápido crecimiento es el mismo que el de las hidras de Kirby-Paris, pero dado que las hidras de Buchholz crecen no solo en anchura sino también en altura, tiene una tasa de crecimiento mucho mayor que , el ordinal de Takeuti-Feferman-Buchholz:

Este sistema también puede utilizarse para crear una notación ordinal para ordinales infinitos, por ejemplo, .

Véase también Teorema de Goodstein

Referencias

Fuentes 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 Mata a la Hidra Matemática por PBS Infinite Series

Categoría:Teoría de grafos Categoría:Objetos en teoría de grafos Categoría:Teoría de números Categoría:Teoría de conjuntos