Paper by Erik D. Demaine

Reference:
Erik D. Demaine, Justin Kopinsky, and Jayson Lynch, “Recursed Is Not Recursive: A Jarring Result”, in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 35:1–35:15.

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 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.

Comments:
This paper is also available from LIPIcs, and from arXiv. A sample level from the reduction is available on Github.

Length:
The paper is 15 pages.

Availability:
The paper is available in PDF (1163k).
See information on file formats.
[Google Scholar search]


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated December 5, 2021 by Erik Demaine.