Paper by Erik D. Demaine
- 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.
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
- This paper is also available from LIPIcs, and from arXiv. A sample level from the reduction is available on Github.
- The paper is 15 pages.
- 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
Last updated December 5, 2021 by