Document Open Access Logo

Recursed Is Not Recursive: A Jarring Result

Authors Erik D. Demaine , Justin Kopinsky, Jayson Lynch

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.50.pdf
  • Filesize: 1.14 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Computational Complexity
  • Undecidable
  • Video Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Erik D. Demaine, Justin Kopinsky, and Jayson Lynch. Recursed Is Not Recursive: A Jarring Result. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.50

Author Details

Erik D. Demaine
  • Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
Justin Kopinsky
  • Work done while at MIT, Cambridge, MA, USA
Jayson Lynch
  • Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA

Acknowledgements

This work was initiated during the 33rd Bellairs Winter Workshop on Computational Geometry, co-organized by Erik Demaine and Godfried Toussaint in March 2018 in Holetown, Barbados. We thank the other participants - in particular, Robert Hearn - for related discussions and providing an inspiring atmosphere. We thank Edison Y. He for his helpful comments on earlier drafts of this paper. Figures were generated using SVG Tiler [Demaine, 2020].

References

  1. Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), pages 3:1-3:21, La Maddalena, Italy, June 2018. Google Scholar
  2. Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch, Sarah Scheffler, and Adam Suhl. PSPACE-completeness of pulling blocks to reach a goal. In Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), pages 31-32, Tokyo, Japan, September 2019. Google Scholar
  3. Alex Churchill. Magic: the Gathering is Turing complete. http://www.toothycat.net/~hologram/Turing/, 2012.
  4. Alex Churchill, Stella Biderman, and Austin Herrick. Magic: The Gathering is Turing complete. arXiv:1904.09828, 2019. URL: http://arxiv.org/abs/1904.09828.
  5. Computational complexity theory Steam curator. https://store.steampowered.com/curator/31317680-Computational-Complexity-Theory/, 2017. Steam curator page claiming hardness results for various games.
  6. Michael J. Coulombe and Jayson Lynch. Cooperating in video games? impossible! undecidability of team multiplayer games. In Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe, editors, Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), volume 100 of LIPIcs, pages 14:1-14:16, La Maddalena, Italy, June 2018. URL: https://doi.org/10.4230/LIPIcs.FUN.2018.14.
  7. Erik D. Demaine. SVG Tiler. https://github.com/edemaine/svgtiler, 2020.
  8. Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Computational complexity of motion planning of a robot through simple gadgets. In Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), volume 100 of LIPIcs, pages 18:1-18:21, La Maddalena, Italy, June 2018. Google Scholar
  9. Erik D. Demaine and Justin Kopinsky. recursed-xls2lua. https://github.com/edemaine/recursed-xls2lua, 2020. Tool to convert xls descriptions of Recursed levels to playable lua files, with examples.
  10. Erik D. Demaine, Justin Kopinsky, and Jayson Lynch. Recursed is not recursive: A jarring result. arXiv:2002.05131, 2020. URL: http://arxiv.org/abs/2002.05131.
  11. edderiofer. edderiofer Steam review. https://steamcommunity.com/id/edderiofer/recommended/497780/, 2017. User review for Recursed which conjectures undecidability.
  12. Linus Hamilton. Braid is undecidable. arXiv:1412.0784, 2014. URL: http://arxiv.org/abs/1412.0784.
  13. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, Ltd., Natick, MA, USA, 2009. Google Scholar
  14. Marvin L. Minsky. Recursive unsolvability of Post’s problem of "Tag" and other topics in theory of Turing machines. Annals of Mathematics, 74(3):437-455, November 1961. Google Scholar
  15. Portponky. Recursed. https://store.steampowered.com/app/497780/Recursed/, 2016.
  16. Portponky. Recursed - fissure / jar mechanic. https://youtu.be/WumGkuBzvLQ, 2016.
  17. Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264-268, 1946. Google Scholar
  18. Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact