🍄 Super Mario proven to be algorithmically undecidable
Researchers from the MIT Hardness Group have demonstrated that the problem of determining level reachability in Super Mario is algorithmically undecidable. The game has been moved from the PSPACE complexity class to the RE-Complete class due to the use of in-game mechanics that simulate infinite memory.
🌍 The research shows that gaming environments can serve as models for extremely complex computational problems, helping to classify the complexity of systems in robotics and chemistry.
👤 This confirms that even simple games can possess infinite computational complexity, comparable to the Turing halting problem.
Source 1: https://www.technologyreview.com/2026/06/23/1138262/super-mario-is-mathier-than-you-think/