brhfl.com

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 110¹ 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.

Over four years ago, a challenge was posed on the Programming Puzzles & Code Golf Stack Exchange: Build a working game of Tetris in Conway’s Game of Life (GoL). Yesterday, an incredibly dedicated team of seven posted a working solution that is just fantastic to read about. I am flabbergasted by the work that went into this, and what these folks achieved. Starting with the concept of a metapixel – essentially a giant block of GoL tiles that can be programmed to behave like a single GoL cell, but with any ruleset – they developed wiring, logic gates, an ALU, a RISC architecture, an assembly language, a higher-level language, and finally (for now) a working game of Tetris. Not the first example of advanced computation in GoL (Wireworld is well known), but almost certainly the largest in scope and likely the best-documented as well. I linked to the Stack Exchange page, and if you have any knowledge of GoL, logic gates, or low-level computing, the multiple write-ups are incredibly clear and fascinating.