Recursed Is Not Recursive: A Jarring Result

DOI10.4230/LIPICS.ISAAC.2020.50MaRDI QIDQ6065458zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Justin Kopinsky, Jayson Lynch

Publication date 14 November 2023

Full work available at URL https://arxiv.org/abs/2002.05131

zbMATH Keywords

computational complexityundecidablevideo games

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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 15x20 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.

Cites work

• A variant of a recursively unsolvable problem
• Computational complexity of motion planning of a robot through simple gadgets
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Games, puzzles, and computation
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

This page was built for publication: Recursed Is Not Recursive: A Jarring Result

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065458)