2026-07-23T22:18:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13394 2024-03-06T10:51:52Z ddc:004 open_access

Recursed Is Not Recursive: A Jarring Result Demaine, Erik D. Kopinsky, Justin Lynch, Jayson Computational Complexity Undecidable Video Games Recursed is a 2D puzzle platform video game featuring "treasure chests" that, when jumped into, instantiate a room that can later be exited (similar to function calls), optionally generating a "jar" that returns back to that room (similar to continuations). We prove that Recursed is RE-complete and thus undecidable (not recursive) by a reduction from the Post Correspondence Problem. Our reduction is "practical": the reduction from PCP results in fully playable levels that abide by all constraints governing levels (including the 15 × 20 room size) designed for the main game. Our reduction is also "efficient": a Turing machine can be simulated by a Recursed level whose size is linear in the encoding size of the Turing machine and whose solution length is polynomial in the running time of the Turing machine. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Justin Kopinsky and Jayson Lynch 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.50 urn:nbn:de:0030-drops-133940 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.50 eng https://creativecommons.org/licenses/by/3.0/legalcode