A new approach to Turing completeness in Baba is You
Caleb Su · International journal of high school research · 2023
Baba is You is a 2019 indie puzzle game whose levels are two-dimensional grids of objects.This paper demonstrates how a universal Turing machine could be created as a custom level in the game if a specific in-game limit were to be removed.A player could perform any computation by playing this level, allowing infinitely many new and meaningful puzzles to be created.Furthermore, the construction is such that the level is won if and only if the Turing machine halts, proving perfect play of the game to be unattainable by any computer.The machine is found to be exponentially time-complex, and the paper concludes with a discussion of the practical feasibility of in-game computation.