He aquí un problema que probablemente no resolviste en la escuela: Eres un joven y ambicioso fontanero de Brooklyn en un mundo habitado por violentas setas del tamaño de un humano, llamadas Goombas. El amor de tu vida ha sido secuestrado, así que te embarcas en una misión para rescatarla, aventurándote a través de extensiones de terreno llenas de tuberías y plagadas de monstruos, donde tu única defensa son tus poderes de salto y pisotón.
Es un viaje tan arduo que ningún ordenador —real o hipotético— es lo suficientemente potente como para averiguar si puedes alcanzarla. Y según una investigación publicada por el Grupo de Dureza del MIT, determinar si tu misión es posible en absoluto es al menos tan complicado como descodificar la encriptación detrás de las transacciones financieras. Pero si este problema pudiera hablar, lo primero que diría sería «¡Hola, soy yo, Mario!»
Por el amor al juego
Aunque tiene un canal de YouTube, el MIT Hardness Group no es un grupo de investigación oficial. En su lugar, es un nombre provisional para proyectos de informática teórica —incluyendo varios relacionados con Super Mario— de la clase de Erik Demaine, Cotas Inferiores Algorítmicas: Diversión con Pruebas de Dificultad.
Demaine, profesor de informática, recibió una beca MacArthur (también conocida como subvención para 'genios') por su trabajo en geometría computacional sobre el plegamiento de proteínas y el origami. Pero también investiga la teoría de la complejidad, que se centra en organizar los problemas en categorías según el tiempo y el espacio de memoria que tardan los ordenadores en resolverlos.
Resulta que también es un fan acérrimo de Super Mario. «Crecí jugando a juegos de la NES [Nintendo Entertainment System]», afirma Demaine. «Dediqué muchas horas a jugar de pequeño, así que resulta divertido retomarlo tantos años después y vincularlo con mi investigación».
Super Mario se desarrolla en un universo de desplazamiento horizontal, con plataformas, tuberías y otros obstáculos. El objetivo del juego es rescatar a la Princesa Peach, la monarca del Reino Champiñón, corriendo por este terreno mientras esquiva o se enfrenta a monstruos como los Goombas y a los mortíferos erizos llamados Spinies. El juego se desarrolla a lo largo de varios niveles; en la versión original, cada nivel termina con un mástil de bandera que envía a Mario a la siguiente parte de su misión.
Durante los últimos 14 años, Demaine y sus colaboradores han demostrado muchas cosas sobre Super Mario, como que es incluso más difícil que el infame problema del viajante de comercio (que busca la ruta más eficiente entre muchas ubicaciones diferentes) o el problema de factorizar números grandes. Pero el resultado que más sorprendió a Demaine provino de cuatro de sus estudiantes: Hayashi Ani ’21, MEng ’23; Holden Hall ’26; Ricardo Ruiz ’24, MEng ’25; y Naveen Venkat ’23, MEng ’24. Para su proyecto final en esa clase de 2023, el equipo utilizó una combinación de editores de niveles de Super Mario hechos por fans y una plataforma llamada Super Mario Maker para crear niveles tan difíciles que son indecidibles. En otras palabras, es imposible escribir un programa de ordenador que siempre prediga correctamente si, en esos niveles, Mario puede llegar al castillo.
Anteriormente, Demaine había creído que Super Mario pertenecía a la clase de complejidad PSPACE, que contiene problemas que son resolubles, pero cuyas soluciones se vuelven impracticamente complejas a medida que el problema crece. En ese momento, incluso había dicho que PSPACE era el «hogar permanente» de Mario. Pero los nuevos hallazgos empujaron a Super Mario a RE-Completa, la clase de problemas indecidibles. «Es la clase de complejidad más difícil que podríamos imaginar para este tipo de juegos», afirma Demaine.
Lo que los ordenadores no pueden resolver
En 1936, Alan Turing, padre de la informática mode a, formuló un problema ahora conocido como el Problema de la Parada para demostrar que no es posible construir un ordenador que pueda resolverlo todo.
En el núcleo del Problema de la Parada reside una paradoja, y es la siguiente: Supongamos que tenemos un ordenador sofisticado, llamado el Oráculo, que examina cualquier programa y determina correctamente si un ordenador que lo ejecuta se detendrá en algún momento. Por ejemplo, si ve el programa «Toma 1 y suma 3», el Oráculo dirá que el programa se detiene, pero si el programa dice «Toma 1 y súmale 1 hasta que se convierta en 0», el Oráculo dirá que se ejecuta indefinidamente.
Ahora supongamos que tenemos otro ordenador, el Contrarian, y colocamos el Oráculo en su interior. Cuando se le da un programa al Contrarian, este lo pasa al Oráculo y luego hace lo contrario de lo que el Oráculo dice que hará el programa. Así, si el Oráculo evalúa el programa del Contrarian y cree que se detendrá, el Contrarian se ejecutará indefinidamente. Si el Oráculo cree que el programa se ejecutará indefinidamente, el Contrarian se detendrá. De cualquier manera, la evaluación del Oráculo es incorrecta, por lo que el problema de clasificación es indecidible.
Las demostraciones de que Super Mario es indecidible se basan en una versión más compleja de esta idea. La argumentación del equipo descompone el videojuego usando una técnica llamada reducción, en la que los matemáticos convierten un problema que están intentando resolver en un problema del que ya saben algo. “El ejemplo clásico que recuerdo en una clase de matemáticas es: ¿Cómo se hace una olla de agua hirviendo?”, recuerda Demaine. “Bueno, lleno la olla con agua del grifo, luego la pongo en el fogón y entonces acaba hirviendo. De acuerdo, ahora te doy una olla de agua que ya está llena. ¿Cómo se hace una olla de agua hirviendo? Bueno, primero vacío la olla y lo reduzco al problema anterior”.
En su particular mundo de plataformas y puercoespines, el equipo desglosó su nivel de Super Mario en partes localizadas del camino de Mario llamadas «gadgets», que pudieron utilizar para demostrar que el nivel era indecidible.
«Un 'gadget', en nuestro sentido, es cualquier cosa en tu ento o que decide si puedes o no atravesar un patrón [dentro de un nivel]», explica Jayson Lynch '12, MEng '15, PhD '20, científico investigador del CSAIL y director de algoritmos en MIT FutureTech. Por ejemplo, en un 'gadget', Mario podría necesitar saltar sobre una plataforma para evitar un monstruo mientras avanza por la pantalla. Como estudiante de doctorado bajo la tutela de Demaine, Lynch lideró la formalización de la teoría de los 'gadgets' y trabajó en algunos de los primeros artículos sobre Super Mario, pero no estudió la indecidibilidad del juego.
Uno de los dispositivos favoritos de Lynch en Super Mario es el dispositivo de la puerta, que funciona como una puerta que Mario puede abrir, atravesar y cerrar. La puerta en cuestión está siempre abierta (cuando el Spiny está a la derecha) o cerrada (cuando el Spiny está a la izquierda). Así, si un Spiny se está moviendo de un lado a otro a la izquierda de la puerta, Mario tiene que maniobrar por debajo del Spiny en movimiento y saltar para golpear un bloque de ladrillo justo cuando el Spiny lo alcanza. Esto empuja al Spiny hacia el lado derecho, lo que abre la puerta y permite a Mario recorrer la ruta de paso y llegar al punto donde puede cerrar la puerta. Una vez allí, debe sincronizar otro salto por debajo del Spiny en movimiento para enviarlo de vuelta al lado izquierdo del dispositivo, cerrando la puerta tras de sí.
Dado que una puerta siempre está abierta o cerrada, su estado puede utilizarse para simular una afirmación booleana, siendo 'abierto' verdadero y 'cerrado' falso. Estudios previos sobre Super Mario habían concatenado múltiples mecanismos de puerta para simular un problema de verdadero o falso que los investigadores de la complejidad ya sabían que era difícil. Pero para demostrar la indecidibilidad, el equipo utilizó editores de niveles de Super Mario para crear otro dispositivo, denominado dispositivo contador, que contabiliza los monstruos y obstáculos del juego.
Si se puede construir una máquina con tan solo unos pocos de esos contadores, afirma Demaine, se puede simular un ordenador arbitrario —uno que, en esencia, podría hacer cualquier cosa que un ordenador no cuántico pudiera hacer, dado suficiente tiempo y memoria. Y sin límite en el número de monstruos, una máquina así podría tener memoria infinitamente expandible, a pesar de que el tamaño del nivel permanece igual, lo que él califica de «bastante sorprendente». En otras palabras, cualquier ordenador teórico puede construirse en un nivel de Super Mario . «Se podría usar para resolver cualquier cosa para la que se use un ordenador», dice Demaine. «Podría hacer sus impuestos, compilar su código, ejecutar un LLM u optimizar su horario de clases». Incluso se podrían construir niveles de Super Mario capaces de sobresalir en el sudoku, elaborar estrategias óptimas de ajedrez o demostrar cualquier teorema matemático demostrable.
El matemático del MIT Marvin Minsky inventó las máquinas de contador en 1961 para averiguar cuán simple podía ser un ordenador sin dejar de ser "universal" (tan potente como cualquier otro ordenador, dado el tiempo suficiente). Estos ordenadores teóricos almacenan cada uno dos números y pueden modificarlos sumando 1, restando 1, o realizando algo especial si un número alcanza un valor preestablecido.
En los *gadgets* de contador que los estudiantes diseñaron para Super Mario, los números reflejan cuántos Goombas contienen los niveles. Un número aumenta cuando una tubería escupe un Goomba y disminuye cuando Mario pisa uno. Mario muere si colisiona con un Goomba sin pisarlo, por lo que solo puede continuar por el camino cuando el contador está a 0.
Minsky ya había demostrado que las máquinas de contador son indecidibles porque pueden ejecutar problemas indecidibles. Dado que los investigadores demostraron que los dispositivos de contador simulan máquinas de contador, entonces cualquier nivel de Super Mario que contenga un dispositivo de contador también será irresoluble. «En el futuro, si alguien quiere demostrar que un juego es indecidible —explica Holden Hall, uno de los estudiantes del proyecto—, solo tiene que construir uno de estos dispositivos.»
La existencia de problemas indecidibles como el Problema de la Parada implica que es posible construir un nivel de Super Mario indecidible. Del mismo modo que el único programa indecidible para el Problema de la Parada significaba que es imposible determinar si un programa informático se ejecutará para siempre, el nivel indecidible del equipo significa que es imposible determinar si un nivel de Mario arbitrario puede ser superado.
Poniendo el «súper» en Super Mario
Más de dos años después de la clase de Demaine sobre pruebas de dureza, algunos de sus alumnos siguen reuniéndose semanalmente para debatir su investigación sobre Super Mario.
“Desde el punto de vista de la teoría de la complejidad, estudiar videojuegos es interesante sobre todo por razones didácticas”, declaró Fabrizio Grandoni, profesor investigador de la Universidad de Ciencias Aplicadas y Artes del Sur de Suiza, a MIT News en 2016. “Es una forma sencilla y natural de atraer a los estudiantes para que estudien este tema específico”.
Hall, quien tenía muy poca exposición a las ideas de la teoría de la complejidad antes de tomar la clase de Demaine, es un buen ejemplo de ello, señalando: “Tomé la clase porque mucha gente que conocía la estaba tomando. Pero desde que la tomé, disfruté mucho la clase, y por eso he tomado muchas más clases en ese ámbito”.
Las aplicaciones del trabajo del Grupo de Dureza del MIT van mucho más allá de pisar setas y recolectar monedas. Por ejemplo, investigadores de la Universidad de Texas Valle del Río Grande (entre ellos Timothy Gomez, ahora estudiante de doctorado en el MIT) han utilizado la teoría de *gadgets* desarrollada para analizar juegos como Super Mario, para estudiar la complejidad de problemas relacionados con la planificación del movimiento robótico y el modelado de redes de reacciones químicas.
“[La teoría de los gadgets] puede usarse de forma negativa para decir ‘Oh, bueno, deberíamos dejar de buscar algoritmos porque sabemos que este problema es demasiado difícil’—o puede usarse de un modo positivo, porque, normalmente, para demostrar algo difícil, estás mostrando que puedes construir un ordenador de un tipo determinado”, dice Demaine.
Aunque no hay forma de saber qué huella dejará Super Mario en el futuro de las matemáticas y la informática, una cosa está clara: independientemente de cuántas princesas salve o no salve, el legado de este pequeño fontanero está destinado a extenderse mucho más allá de las pantallas de vídeo.