Aquí hay un problema que probablemente no resolviste en la escuela: eres un joven plomero ambicioso de Brooklyn en un mundo habitado por violentos hongos de tamaño humano llamados Goombas. El amor de tu vida ha sido secuestrado, por lo que te embarcas en una búsqueda para rescatarla, aventurándote a través de tramos de terreno lleno de tuberías y plagado de monstruos donde tu único medio de protección son tus poderes de saltar y pisotear. Erik Demaine investiga la teoría de la complejidad, que examina la cantidad de tiempo y memoria que necesitan las computadoras para resolver problemas. También es un ávido fanático de Super Mario. Mario abre la puerta empujando al Spiny de izquierda a derecha. Con el Spiny fuera del camino, Mario puede atravesar la puerta abierta y seguir el camino transversal hacia el otro lado. Una vez allí, podrá empujar al Spiny hacia la izquierda y cerrar la puerta.
Dado que una puerta siempre está abierta o cerrada, su estado se puede utilizar para simular una afirmación verdadera o falsa, siendo abierta verdadera y cerrada falsa. Artículos anteriores de Super Mario habían unido múltiples dispositivos de puertas para simular un problema de verdadero o falso que los investigadores de complejidad ya sabían que era difícil. Pero para mostrar indecidibilidad, el equipo utilizó editores de niveles de Super Mario para armar otro dispositivo, llamado dispositivo contador, que cuenta los monstruos y obstáculos del juego.
Si se puede construir una máquina con sólo unos pocos de esos contadores, dice Demaine, se puede simular una computadora arbitraria, una que esencialmente podría hacer cualquier cosa que una computadora no cuántica pudiera hacer, con suficiente tiempo y memoria. Y sin límite en el número de monstruos, una máquina así podría tener una memoria infinitamente ampliable, aunque el tamaño del nivel siga siendo el mismo, lo que él llama “bastante salvaje”. En otras palabras, cualquier computadora teórica se puede construir en un nivel de Super Mario. “Podrías usarlo para resolver cualquier cosa que puedas hacer con una computadora”, dice Demaine. “Podría hacer que haga sus impuestos, compile su código, ejecute un LLM u optimice su horario de clases”. Incluso podrías construir niveles de Super Mario que te permitan sobresalir en el sudoku, construir estrategias óptimas de ajedrez o demostrar cualquier teorema matemático demostrable.
El matemático del MIT Marvin Minsky inventó las máquinas contadoras en 1961 para descubrir qué tan simple podía ser una computadora sin dejar de ser “universal” (tan poderosa como cualquier otra computadora, si se le daba suficiente tiempo). Cada una de estas computadoras teóricas almacena dos números y puede cambiarlos sumando 1, restando 1 o haciendo algo especial si un número alcanza un valor establecido.
En los contadores 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 choca con un Goomba sin pisotearlo, por lo que podrá continuar por el camino sólo cuando el contador esté en 0.
[contenido incrustado]
El grupo MIT Hardness diseñó este dispositivo contador en Super Mario Maker 1 para demostrar la indecidibilidad.
Minsky ya había demostrado que las máquinas contadoras son indecidibles porque pueden ejecutar problemas indecidibles. Dado que los investigadores demostraron que los dispositivos de contador simulan máquinas de contador, cualquier nivel de Super Mario que contenga un dispositivo de contador también será irresoluble. “En el futuro, si alguien quiere mostrar un juego indecidible”, explica Holden Hall, uno de los estudiantes detrás del proyecto, “sólo tendrá que fabricar uno de estos gadgets”.
La existencia de problemas indecidibles como el problema de la detención implica que es posible construir un nivel de Super Mario indecidible. Así como el singular programa indecidible para Halting Problem significaba que es imposible determinar si un programa de computadora se ejecutará para siempre, el nivel indecidible del equipo significa que es imposible determinar si se puede superar un nivel arbitrario de Mario.
Poniendo el “super” en Super Mario
Más de dos años después de la clase de Demaine sobre pruebas de dureza, algunos de sus estudiantes continúan reuniéndose semanalmente para discutir su investigación sobre Super Mario.
“Desde el punto de vista de la teoría de la complejidad, estudiar videojuegos es interesante principalmente por razones didácticas”, dijo a MIT News en 2016 Fabrizio Grandoni, profesor investigador de la Universidad de Ciencias y Artes Aplicadas del Sur de Suiza. “Es una forma sencilla y natural de atraer a los estudiantes para que estudien este tema específico”.
Hall, que tuvo 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 y señala: “Tomé la clase porque un grupo de personas que conocía la estaban tomando. Pero desde que la tomé, realmente disfruté la clase, y por eso he tomado muchas más clases en ese ámbito”.
Las aplicaciones del trabajo del MIT Hardness Group van mucho más allá de pisotear setas y recolectar monedas. Por ejemplo, investigadores de la Universidad de Texas Rio Grande Valley (incluido Timothy Gómez, ahora estudiante de doctorado en el MIT) han utilizado la teoría de los dispositivos desarrollada para analizar juegos como Super Mario para estudiar la complejidad de los problemas relacionados con la planificación del movimiento robótico y el modelado de redes de reacciones químicas.
“[La teoría de los dispositivos] puede usarse de manera negativa para decir ‘Oh, bueno, deberíamos dejar de buscar algoritmos porque sabemos que este problema es demasiado difícil’, o puede usarse de esta manera positiva, porque generalmente, para demostrar algo difícil, estás demostrando que puedes construir una computadora de cierto tipo”, dice Demaine.
Aunque no hay forma de saber qué marca dejará Super Mario en el futuro de las matemáticas y la informática, una cosa es segura: no importa cuántas princesas salve o no, el legado de este pequeño plomero se extenderá mucho más allá de las pantallas de video.
Publicado originalmente en technologyreview.com el 23 de junio de 2026.
Ver fuente original
