Programming book reviews, programming tutorials,programming news, C#, Ruby, Python,C, C++, PHP, Visual Basic, Computer book reviews, computer history, programming history, joomla, theory, spreadsheets and more.
It is one thing to know that something unlikely is Turing complete; it is quite another to use it to build a computer and then implement something real. This is exactly what has just happened with Conway’s Game Of Life with the construction of a computer to play Tetris. This is a remarkable achievement that should send your brain into a tailspin.
Over a year ago a challenge was issued on StackExchange to create a Game Of Life (GoL) implementation of Tetris.
GoL has long been known to be Turing complete, i.e. it is possible to use it to implement any computation, but the complexity of implementing Tetris is huge. GoL enthusiasts have been pushing the limits of the idea for quite a while and the size of many of their constructions makes it difficult for an outsider to see how such things are created. For example, there is construction known as a metapixel which can mimic any other arrangement, but it is 2048×2048 pixels in size. The trick seems to be that after a while you start to think in terms of bigger and bigger functional units and to put these together to make new and even bigger functional units.
The challenge hung around for a while and then a group of enthusiasts, GoL researchers, it is difficult to know exactly what to call them started to produce some results. A Github project and chat-room enabled a team with a varying composition to work on the mega project – something like a GoL moonshot.
From the metapixel the team first constructed logic gates. In principle once you have a set of gates a processor is possible. After all our non-GoL computers are built from nothing but simple logical gates. In principle all you need is a Nand gate but in practice it is slightly easier to have a variety.
From logic gates the team started to climb the pyramid of complexity. From gate to more complex processing units, flip flops, storage, an arithmetic unit, ROM and so on.
Next they designed an asynchronous processor and an assembly language for it called QFTASM Quest for Tetris Assembly. The next step up was a high level language called Cogol and a backend for GCC is still under construction which will allow exiting C/C++ programs to be compiled to Cogol.
The actual Tetris game was coded in Cogol and compiled to QFTASM and it is a fairly full implementation with a range of parts, drop command, scoring and next piece preview. The resulting machine code was automatically converted into a ROM.
“So, our computer (with the Tetris ROM) has a bounding box of 1,436 x 5,082. Of the 7,297,752 cells in that box, 6,075,811 are empty space, leaving an actual population count of 1,221,941. Each of those cells needs to be translated into an OTCA metapixel, which has a bounding box of 2048×2048 and a population of either 64,691 (for an ON metapixel) or 23,920 (for an OFF metapixel). That means the final product will have a bounding box of 2,940,928 x 10,407,936 (plus a few thousand extra for the borders of the metapixels), with a population between 29,228,828,720 and 79,048,585,231. With 1 bit per live cell, that’s between 27 and 74 GiB needed to represent the entire computer and ROM.”
If you want to see the game in action then the quickest way is to go to the QFTASM interpreter and see it run there. The pieces can be seen as patterns of bits in memory locations 10 to 31. You should be able to recognize the familiar shapes. Controlling the game is more complicated and requires direct memory input – no keyboard input here.
I’m sure that many people have looked at the QFTASM program running and been impressed, but to be honest it is just an interpreter for an assembly language for an imaginary machine. This is not Tetris running on GoL. To see the real thing you need to download Golly, a high speed GoL program and the inital pattern file and load it into Golly and see the whole thing running – now this is amazing. But it is much more difficult to actually play, because the memory doesn’t have a handy bit-oriented display like the simulator.
No doubt this will give rise to reports of us living in a simulation of a simulation of a simulation, but the real truth is deeper. Turing completeness means Turing completeness and with such simple things you can do anything that can be done.
Build a working game of Tetris in Conway’s Game of Life
Cellular Automata – The How and Why
The Game of Life in hardware
A New Kind of Science Is Ten
It’s life but not …
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook, Google+ or Linkedin.
