“Recursed Is Not Recursive: A Jarring Result”, 2020-02-12 (; backlinks):
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.