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.

BibTeX

@InProceedings{Recursed_ISAAC2020,
  AUTHOR        = {Erik D. Demaine and Justin Kopinsky and Jayson Lynch},
  TITLE         = {Recursed Is Not Recursive: A Jarring Result},
  BOOKTITLE     = {Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  bookurl       = {https://algo2020.comp.polyu.edu.hk/isaac.html},
  ADDRESS       = {Hong Kong},
  MONTH         = {December 14--18},
  YEAR          = 2020,
  PAGES         = {35:1--35:15},

  length        = {15 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.ISAAC.2020.50},
  dblp          = {https://dblp.org/rec/conf/isaac/DemaineKL20},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.ISAAC.2020.50">LIPIcs</A>, and from <A HREF="https://arxiv.org/abs/2002.05131">arXiv</A>. A sample level from the reduction is available on <A HREF="https://github.com/edemaine/recursed-xls2lua">Github</A>.},
}

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]