论文标题
递归不是递归的：一个令人震惊的结果
Recursed is not Recursive: A Jarring Result
论文作者
论文摘要
递归是一个2D拼图平台的视频游戏，其中包含宝藏箱，然后跳入后，实例化了一个可以退出的房间（类似于功能呼叫），可选地生成一个回到该房间的罐子（类似于连续）。我们证明，递归是重新完成的，因此通过减少后通讯问题而无法确定（不是递归）。我们的减少是“实用的”：从PCP中减少的会导致完全可玩的水平，这些水平遵守了为主游戏设计的所有约束水平（包括15x20房间尺寸）。我们的还原也是“有效的”：图灵机可以通过递归的级别模拟，其大小在图灵机的编码大小中是线性的，并且在图灵机的运行时间内，其解决方案长度是多项式的。
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 15x20 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.
