MIT 연구진에 따르면 '슈퍼 마리오'는 단순한 게임을 넘어 컴퓨터로도 풀 수 없는 최고 난도의 '결정 불가능(undecidable)' 문제로 증명되었습니다. 알고리즘 복잡도 이론을 바탕으로 한 이 연구는 게임의 레벨 설계가 튜링 머신의 정지 문제(Halting Problem)와 같은 수학적 한계에 도달해 있음을 보여줍니다.
번역된 본문
학교에서 접해보지 못했을 법한 문제를 하나 소개합니다. 당신은 굼바(Goomba)라는 폭력적인 인간 크기의 버섯들이 살고 있는 세계에서 살아가는 야심 찬 브루클린 출신의 젊은 배관공입니다. 당신의 평생 소중한 사람이 납치되어 그녀를 구출하기 위한 여정을 떠납니다. 파이프와 괴물로 가득 찬 지형을 모험하면서, 당신이 몸을 보호할 수 있는 유일한 수단은 점프하고 밟는 능력뿐입니다. 이 여정은 너무나 고되어서, 실존하든 가상이든 그 어떤 컴퓨터조차 당신이 그녀에게 도달할 수 있는지 알아낼 만큼 강력하지 않습니다. MIT Hardness Group이 발표한 연구에 따르면, 이 여정이 가능한지조차 결정하는 것은 적어도 금융 거래를 보호하는 암호화 기술을 해독하는 것만큼이나 복잡한 일입니다. 하지만 이 문제가 말을 할 수 있다면, 가장 먼저 할 말은 "안녕, 여기는 나, 마리오!"일 것입니다.
게임을 향한 애정
MIT Hardness Group은 유튜브 채널을 운영하고 있긴 하지만 공식 연구 그룹은 아닙니다. 대신, 에릭 데메인(Erik Demaine) 교수의 '알고리즘 하한선: 증명의 재미(Algorithmic Lower Bounds: Fun with Hardness Proofs)' 수업에서 파생된 이론적 컴퓨터 과학 프로젝트들을 위한 가칭입니다. 컴퓨터 과학 교수인 데메인은 단백질 접힘 및 종이접기에 대한 계산 기하학 연구로 맥아더 펠로십(일명 '천재' 보조금)을 수상한 바 있습니다. 그는 컴퓨터가 문제를 해결하는 데 걸리는 시간과 메모리 공간을 기준으로 문제를 분류하는 복잡도 이론(complexity theory)도 연구합니다. 그는 우연히도 열렬한 슈퍼 마리오 팬이기도 합니다. 데메인은 "어릴 적 NES [닌텐도 엔터테인먼트 시스템] 게임을 하며 자랐다"며, "아이로서 수많은 시간을 게임에 쏟았기 때문에, 수년이 지난 지금 다시 이 게임으로 돌아와 내 연구와 연결하는 것은 매우 재미있는 일"이라고 말합니다.
슈퍼 마리오는 플랫폼, 파이프 및 기타 장애물로 이루어진 수평 스크롤 방식의 우주를 배경으로 합니다. 이 게임의 목표는 굼바나 가시 달린 독고 미니(Spinies) 같은 괴물을 피하거나 결투를 벌이면서 지형을 질주하여 버섯 왕국의 통치자인 피치 공주를 구출하는 것입니다. 게임은 여러 레벨로 진행되며, 오리지널 버전에서는 각 레벨의 끝에 깃대가 있어 마리오를 다음 미션으로 보냅니다. 지난 14년 동안 데메인과 그의 공동 연구자들은 슈퍼 마리오에 대해 여러 가지를 증명했습니다. 예를 들어, 이 게임은 악명 높은 외판원 문제(여러 다른 위치 간의 가장 효율적인 경로를 찾는 문제)나 큰 숫자를 소인수분해하는 문제보다 더 어렵다는 것입니다. 하지만 데메인을 가장 놀라게 한 결과는 그의 네 명의 학생들(하야시 아니, 홀든 홀, 리카르도 루이스, 나빈 벤카트)로부터 나왔습니다. 2023년 수업의 기말 프로젝트를 위해 이 팀은 팬들이 만든 슈퍼 마리오 레벨 에디터와 '슈퍼 마리오 메이커(Super Mario Maker)'라는 플랫폼을 조합하여 '결정 불가능(undecidable)'할 정도로 어려운 레벨을 만들었습니다. 즉, 그 레벨들에서 마리오가 성에 도달할 수 있는지 항상 올바르게 예측하는 컴퓨터 프로그램을 작성하는 것은 불가능합니다. 이전에는 데메인이 슈퍼 마리오가 PSPACE 복잡도 클래스(문제가 커질수록 해결책이 비현실적으로 복잡해지지만 풀 수는 있는 문제들)에 속한다고 믿었습니다. 당시 그는 PSPACE가 마리오의 "영구적인 집"이라고까지 말했습니다. 하지만 새로운 연구 결과는 슈퍼 마리오를 결정 불가능한 문제들의 집합인 RE-Complete로 격상시켰습니다. 데메인은 "이것은 이러한 종류의 게임에서 우리가 상상할 수 있는 가장 어려운 복잡도 클래스"라고 말합니다.
컴퓨터가 풀 수 없는 것
1936년, 현대 컴퓨터 과학의 아버지인 앨런 튜링(Alan Turing)은 모든 것을 해결할 수 있는 컴퓨터를 구축하는 것은 불가능하다는 것을 증명하기 위해 현재 '정지 문제(Halting Problem)'로 알려진 퍼즐을 만들었습니다. 정지 문제의 핵심에는 역설이 있는데, 다음과 같습니다. 어떤 프로그램이든 보고 컴퓨터가 그것을 따라 결국 멈출지(끝날지) 올바르게 결정할 수 있는 '오라클(Oracle)'이라는 멋진 컴퓨터가 있다고 가정해 봅시다. 예를 들어, '1에 3을 계속 더하라'는 프로그램을 본다면 오라클은...
Here’s a problem you probably didn’t solve in school: You’re an ambitious young plumber from Brooklyn in a world inhabited by violent human-size mushrooms called Goombas. The love of your life has been kidnapped, so you embark on a quest to rescue her, venturing through stretches of pipe-filled and monster-ridden terrain where your only means of protection are your powers of jumping and stomping. It’s a journey so arduous that no computer—real or hypothetical—is powerful enough to figure out if you can reach her. And according to research published by the MIT Hardness Group, determining whether your quest is possible at all is at least as complicated as decoding the encryption behind financial transactions. But if this problem could talk, the first thing it would say is “Hello, it’s a-me, Mario!” For the love of the game Though it does have a YouTube channel, the MIT Hardness Group isn’t an official research group. Instead, it’s a placeholder name for theoretical computer science projects—including several related to Super Mario—from Erik Demaine’s class Algorithmic Lower Bounds: Fun with Hardness Proofs. Demaine, a professor of computer science, received a MacArthur fellowship (also known as a “genius” grant) for his work in computational geometry on protein folding and origami. But he also researches complexity theory, which focuses on organizing problems into categories based on how much time and memory space it takes for computers to solve them. He happens to be an avid Super Mario fan as well. “I grew up playing NES [Nintendo Entertainment System] games,” Demaine says. “I poured many hours into playing as a kid, so it’s fun to come back to it these many years later and tie it into my research.” Super Mario takes place on a horizontally scrolling universe of platforms, pipes, and other obstacles. The object of the game is to rescue Princess Peach, the monarch of the Mushroom Kingdom, by racing through this terrain while sidestepping or dueling monsters like Goombas and deadly porcupines called Spinies. The game takes place over several levels; in the original version, each level ends with a flagpole that sends Mario on to the next part of his mission. Over the last 14 years, Demaine and his collaborators have proved many things about Super Mario, such as that it’s even harder than the infamous traveling-salesman problem (which seeks the most efficient route between many different locations) or the problem of factoring large numbers. But the result that surprised Demaine the most came from four of his students: Hayashi Ani ’21, MEng ’23; Holden Hall ’26; Ricardo Ruiz ’24, MEng ’25; and Naveen Venkat ’23, MEng ’24. For their final project in that 2023 class, the team used a combination of fan-made Super Mario level editors and a platform called Super Mario Maker to create levels so hard that they are undecidable. In other words, it’s impossible to write a computer program that always correctly predicts whether, in those levels, Mario can reach the castle. Previously, Demaine had believed that Super Mario belonged in the PSPACE complexity class, which contains problems that are solvable but whose solutions become impractically complex as the problem gets bigger. At the time, he had even said that PSPACE was Mario’s “permanent home.” But the new findings pushed Super Mariointo RE-Complete, the class of undecidable problems. “It’s the hardest complexity class we could imagine for these sorts of games,” Demaine says. What computers can’t solve In 1936, Alan Turing, the father of modern computer science,created a puzzle now known as the Halting Problem to prove it’s not possible to construct a computer that can solve everything . At the core of the Halting Problem lies a paradox, and it goes like this: Suppose you have a fancy computer, called the Oracle, that looks at any program and correctly determines whether a computer following it will ever come to a stop. For example, if it sees the program “Take 1 and add 3,” the Oracle will say the program halts, but if the program says “Take 1 and add 1 to it until it becomes 0,” the Oracle will say it runs forever. Now suppose you have another computer, the Contrarian, and you put the Oracle inside it. When you give the Contrarian a program, it passes it to the Oracle and then does the opposite of whatever the Oracle says the program will do. So if the Oracle assesses the Contrarian’s program and thinks it will halt, the Contrarian will run forever. If the Oracle thinks the program will run forever, the Contrarian will halt. Either way, the Oracle’s assessment is wrong, so the classification problem is undecidable. The proofs that Super Mario is undecidable rely on a more complex version of this idea. The team’s argument breaks down the video game using a technique called a reduction, in which mathematicians convert a problem they’re trying to solve into a problem they already know something about. “The classic example I remember in a math class is: How do you make a pot of boiling water?” Demaine recalls. “Well, I fill up the pot with water from the sink, and then I put it on the stove, and then it eventually boils. Okay, now I’ll give you a pot of water that’s already filled. How do you make a pot of boiling water? Well, I empty out the pot first and reduce to the previous problem.” In their particular world of platforms and porcupines, the team broke down their Super Mariolevel into localized parts of Mario’s path called gadgets, which they could use to prove that the level was undecidable. “A gadget in our sense is anything in your environment that decides whether or not you can go through one pattern [within a level],” explains Jayson Lynch ’12, MEng ’15, PhD ’20, a CSAIL research scientist and head of algorithms at MIT FutureTech. For example, in one gadget Mario might need to jump on a platform to avoid a monster as he makes his way across the screen. As a PhD student mentored by Demaine, Lynch spearheaded the formalization of gadget theory and worked on some of the earlier Super Mario papers but did not study the game’s undecidability. One of Lynch’s favorite Super Mario gadgets is the door gadget, which works like a door that Mario can open, traverse, and close. The door in question is always either open (when the Spiny is on the right) or closed (when the Spiny is on the left). So if a Spiny is pacing back and forth on the left of the door, Mario has to navigate beneath the moving Spiny and jump up to hit a brick block just as the Spiny reaches it. This bumps the Spiny to the right side, which opens the door and allows Mario to travel across the traverse path and get to the spot where he can close the door. Once there, he must time another jump beneath the pacing Spiny to send it back to the left side of the gadget, closing the door behind him. Since a door is always open or closed, its state can be used to simulate a true or false statement, with open being true and closed being false. Earlier Super Mario papers had strung together multiple door gadgets to simulate a true-or-false problem that complexity researchers already knew to be hard. But to show undecidability, the team used Super Mario level editors to put together another device, called a counter gadget, that tallies the game’s monsters and obstacles. If you can build a machine with even just a few of those counters, Demaine says, you can simulate an arbitrary computer—one that could essentially do anything a non-quantum computer could do, given enough time and memory. And with no limit on the number of monsters, such a machine could have infinitely expandable memory, even though the level size stays the same, which he calls “pretty wild.” In other words, any theoretical computer can be built in a Super Mario level. “You could use it to solve anything you can use a computer to do,” says Demaine. “You could have it do your taxes, or compile your code, or run an LLM, or optimize your class schedule.” You might even build Super Mario level