Baba is Turing Complete (external)

Baba is You is a wonderful puzzle game that has been frustrating the heck out of me lately. Its primary conceit is that puzzles are solved by moving textual blocks around to form subject/predicate constructions that rewrite the rules of the puzzle. Matthew Rodriguez has, as explained in the external link above, implemented Rule 1101 in Baba is You, with a video of the automaton in action on his Twitter feed. Matthew Cook famously proved Rule 110 to be Turing complete, which means (given an infinite grid, blah blah) the grammar and mechanics that make for a puzzle in Baba is You also make for a Turing complete system.

Humorously, the first response on the Twitter post is along the lines of ‘can it play DOOM?’ which… Sure! A Turing machine can theoretically do all of the computations that DOOM makes! Ignoring how much processing power and RAM one would need for this (a convenient thing to ignore, but we’re talking hypotheticals here), folks always seem to jump right from Turing machine to something resembling a modern computer. The only thing on the table is computational ability, and at a bare minimum, one still needs a viable I/O interface in order to do anything beyond turning bits into other bits.

  1. Here’s an implementation of Rule 110 in CSS which both helps demonstrate the rules of 110 and shows Turing completeness in CSS. ↩︎