You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games

[2405.10546] You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Computational Complexity arXiv:2405.10546 (cs) [Submitted on 17 May 2024 ( v1 ), last revised 15 Aug 2026 (this version, v2)] Title: You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games Authors: MIT Hardness Group , Erik D. Demaine , Lilly Hall , Hayashi Layers , Ricardo Ruiz , Naveen Venkat View a PDF of the paper titled You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games, by MIT Hardness Group and 5 other authors View PDF HTML (experimental) Abstract: We prove RE-completeness (and thus undecidability) of several 2D games in the Super Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U, and 2), and both Super Mario Maker games in all five game styles (Super Mario Bros. 1 and 3, Super Mario World, New Super Mario Bros. U, and Super Mario 3D World). These results hold even when we restrict to constant-size levels and screens, but they do require generalizing to allow arbitrarily many enemies at each location and onscreen, as well as allowing for exponentially large (or no) timer. Our New Super Mario Bros. constructions fit within one standard screen size. In our Super Mario Maker reductions, we work within the standard screen size and use the property that the game engine remembers offscreen objects that are global because they are supported by "global ground". To prove these Mario results, we build a new theory of counter gadgets in the motion-planning-through-gadgets framework, and provide a suite of simple gadgets for which reachability is RE-complete. Subjects: Computational Complexity (cs.CC) Cite as: arXiv:2405.10546 [cs.CC] (or arXiv:2405.10546v2 [cs.CC] for this version) https://doi.org/10.48550/arXiv.2405.10546 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Lilly Hall [ view email ] [v1] Fri, 17 May 2024 05:15:33 UTC (25,404 KB) [v2] Sat, 15 Aug 2026 21:34:03 UTC (9,870 KB) Full-text links: Access Paper: View a PDF of the paper titled You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games, by MIT Hardness Group and 5 other authors View PDF HTML (experimental) TeX Source view license Current browse context: cs.CC < prev | next > new | recent | 2024-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games#611246
• You can't solve these Super Mario Bros. levels: undecidable Mario games#490061
• Valperga Volume 1 (of 3) or, The life and adventures of Castruccio, prince of Lucca#59793
• Valperga Volume 2 (of 3) or, The life and adventures of Castruccio, prince of Lucca#59794
• Comparación de propiedades físicas de tres formulaciones de chocolate con diferentes porcentajes de pasta de cacao (Theobroma cacao L.) CCN 51#365338