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]