论文标题
爸爸你是不可确定的吗
Baba is You is Undecidable
论文作者
论文摘要
我们确定了2019年拼图游戏的不可证明的爸爸是通过减少邮政通讯问题的减少。特别是，我们考虑了由Newy（Arxiv：1312.6700）引入的后通讯问题的限制形式，该问题仅限于五对单词。爸爸是您是一款屡获殊荣的游戏，玩家可以通过推动阐明规则的块来重新编程游戏的机制。我们通过在水平方向上的游戏场的大小概括，在水平的一侧增加了“走廊”，实现了不可证明的性能。 Baba的不可证明的是，您已经在网上使用不同的来源问题（包括模拟Turing Machines和Conway的生活游戏）在线声称，但是，这种贡献似乎是结果的第一个正式证明。
We establish the undecidability of 2019 puzzle game Baba is You through a reduction from the Post correspondence problem. In particular, we consider a restricted form of the Post correspondence problem introduced by Neary (arXiv:1312.6700) that is limited to five pairs of words. Baba is You is an award winning tile-based game in which the player can reprogram the game's mechanisms by pushing blocks that spell out the rules. We achieve undecidability through a generalization of the size of the playfield in the horizontal direction, adding a "hallway" to one side of the level. The undecidability of Baba is You has been claimed several times online using different source problems, including the simulation of Turing machines and Conway's Game of Life, however, this contribution appears to be the first formal proof of the result.
