A Computer In The Game Of Life

November 21, 2020 by Matthew Carlson 20 Comments

We often hear the term “Turing-complete” without giving much thought as to what the implications might be. Technically Microsoft PowerPoint, Portal 2, and Magic: the Gathering all are Turing-complete, what of it? Yet, each time someone embarks on an incredible quest of perseverance and creates a computer in one of these mediums, we stand back in awe.

[Nicolas Loizeau] is one such individual who has created a computer in Conway’s Game of Life. Unlike electricity, the Game of Life uses gliders as signals. Because two orthogonal gliders can cancel each other out or form a glider eater if they intersect with a good phase shift, the basic logic gates can be formed from these interactions. This means the space between gates is crucial as signals need to be in phase alignment. The basic building blocks are a period-60 gun, a 90-degree glider reflector, a glider duplicator, and a glider eater.

All the Python code that generates these structures is on GitHub as the sheer size of the machine couldn’t possibly be placed by hand. The Python includes scripts to assemble the basic programs as a bank of selectable glider generators. It’s all based on Golly, which is an excellent program for simulating Conway’s Game of Life, among other things. While this isn’t the first computer in the Game of Life as [Paul Rendell] published a design in 2000 and [Adam Goucher] published a Spartan universal computer constructor in 2009, we think this is a particularly beautiful one.

The actual architecture has an 8-bit data bus, a 64-byte memory with two read ports, a ROM with 21 bits per line, and a one-hot encoded ALU supporting 8 different operations. Instructions have a 4-bit opcode which is decoding in a few different instructions. The clock is four loops, formed by the glider reflectors as the glider beams rotate. This gives the computer four stages: execution, writing, increment PC, and write PC to memory.

The Game of Life is an excellent example of Cellular Automaton (CA). There are several other types of CA’s and the history behind them is fascinating. We’ve covered this field before and delved into this beautiful fringe of computer science. Check out the video below to truly get a sense of the scale of the machine that [Nicolas] has devised.

Continue reading “A Computer In The Game Of Life” →

The Game That Launched 1,000 Hackers

April 18, 2020 by Elliot Williams 6 Comments

John Conway passed away this week. Even if you don’t know much about mathematics, you will probably know nearly everyone’s favorite cellular automata ruleset: Conway’s “Game of Life”. It’s so much a part of our cultural history, that proto-hacker Eric Scott Raymond suggested using the glider as the hacker emblem.

The idea that a very simple set of rules, applied equally and everywhere, could result in “life” was influential in my growth as a young hacker, and judging from the comments on our article about Conway, I’m not alone. But I won’t lie: I was a kid and thought that it could do much more than make pretty patterns on the screen. I was both right and wrong.

Although amazingly complex machines can be built in Conway’s Life, just check out this video for proof, in the end no grand unifying theory of cellular automata has emerged. As a research topic Conway’s chosen field of mathematics, cellular automata is a backwater. It didn’t really go anywhere. Or did it?

Implementing Conway’s Life in BASIC on a Tandy Color Computer was one of the first things that launched me on my geeky path. It ranks with MENACE: the matchbox-based machine learning algorithm from the 1960’s and an introduction to Markov Chains in the form of a random text generator in my young algorithmic life, all of which I incidentally read about in Martin Gardner’s column in “Scientific American”. Conway’s Life, along with some dumb horse-race game, also taught me about bad random-number generators: the screen would populate the same “randomly” every time on the old CoCo.

So maybe Conway didn’t want to be remembered just for his “Life” because it was a bit of a mathematical dead-end. But in terms of its impact on the world, an entire generation of hackers, and my own personal life, it was able to fill up significantly more than a screen full of pixels. Here’s to Conway, his “Life”, and everyone else who is inspiring the next. You’re not just gliders, you’re glider guns!

[Game of Life example shown in this article is John Conway’s Game of Life – 1.0 written in Python by Nick Jarvis and Nick Wayne]

John Horton Conway, Creator Of Conway’s Game Of Life, Has Died

April 13, 2020 by Mike Szczys 56 Comments

Programmers everywhere are familiar with Conway’s Game of Life: whether they’ve written a version themselves or simply seen the mesmerizing action resulting from the cellular automata, it’s a household name in all homes where code is spoken. On Saturday April 11th, 2020 its inventor and namesake, John Horton Conway passed away from COVID-19 at the age of 82.

Born in Liverpool, Conway received his PhD in mathematics in 1964 from Gonville and Caius College, Cambridge. He accepted a position at Sidney Sussex College, Cambridge which he held until joining the faculty of Princeton University in 1987. A brilliant mathematician, he received numerous awards and was well known for his work in combinatorial game theory, group theory, and theoretical physics.

Many readers will be familiar with his Doomsday algorithm which can be used to deduce the day of the week for any given date in your head. But by far the rockstar mathematics moment of developing Conway’s Game of Life in 1970 cements him a perpetual place of legend in computing lore. His original work on the concept used pencil and paper as the computing revolution had yet to make digital resources easily available, even to mathematics researchers like Conway.

The game uses an infinite grid of squares where all of the edges of the grid wrap around. Four simple rules (which can be boiled down to three if you’re clever) determine which cells live and which cells die during each frame of the “game”. The only parameters that are needed are the number and position of living cells at the start of the game, and the delay between each game frame. But the effect of this simplicity is not to be understated. The game can be coded by a novice — and it’s become a common challenge in University course work. Small errors, or intentional tweaks, in the implementation have profound effects on behavior of the game. And the effect on the person programming it for the first time can be long lasting. You could call it a mathematics gateway drug, grabbing the curiosity of the unsuspecting mind and pulling it down the rabbit hole of advanced mathematics discovery.

We’d love to celebrate his life by hearing your own stories of programming the Game of Life in the comments below. If you haven’t yet had the pleasure, now’s a great time to take on the challenge.

[Game of Life example shown in this article is John Conway’s Game of Life – 1.0 written in Python by Nick Jarvis and Nick Wayne]

Cellular Automata Explorer

September 30, 2016 by Gerrit Coetzee 15 Comments

Well all know cellular automata from Conway’s Game of Life which simulates cellular evolution using rules based on the state of all eight adjacent cells. [Gavin] has been having fun playing with elementary cellular automata in his spare time. Unlike Conway’s Game, elementary automata uses just the left and right neighbors of a cell to determine the next cell ahead in the row. Despite this comparative simplicity, some really complex patterns emerge, including a Turing-complete one.

[Gavin] started off doing the calculations by hand for fun. He made some nice worksheets for this. As we can easily imagine, doing the calculations by hand got boring fast. It wasn’t long before his thoughts turned to automating his cellular automata. So, he put together an automatic cellular automator. (We admit, we are having a bit of fun with this.)

This could have been a quick software project but half the fun is seeing the simulations on a purpose-built ecosystem. The files to build the device are hosted on Thingiverse. Like other cellular automata projects, it uses LED matrices to display the data. An Arduino acts as the brain and some really cool retro switches from the world’s most ridiculously organized electronics collection finish the look of the project.

To use, enter the starting condition with the switches at the bottom. The code on the Arduino then computes and displays the pattern on the matrix. Pretty cool and way faster than doing it by hand.

That’s Life…on A Hackaday Badge

April 5, 2016 by Al Williams 2 Comments

Our Hackaday Chief [Mike] sent me an e-mail the other day with a link to the Belgrade Hackaday Badge simulator. He clearly wanted me to enter something into the demo scene competition. The good news is that because of the simulator, you didn’t have to leave your desk to participate. The bad news is that I had very little time left at the end of the month, so I wanted to do something appealing but it had to be fairly easy to roll out. I wound up doing a very quick project but it had a few fine points that I thought I’d share. The end goal was to have an interesting display of Conway’s game of life on the badge.

By the way, there was a completely different project with the same goal by [Jeremias] on Hackaday.io. As far as I know, this was just the result of two people setting out to do the same thing. You’ll see the user interface is a good bit different, so you might see which you prefer.

If you haven’t seen it, the real badge is below. The emulator, of course, just runs as a window on your PC. For those that will be at the conference, or just want to program closer to the actual hardware, there is now a preconfigured MPLABX framework for the PIC18LF25K50 and the bootloader/kernel running on this badge.

Continue reading “That’s Life…on A Hackaday Badge” →

THP Entry: Tinusaur AVR Platform Teaches Noobs, Plays Game Of Life

July 29, 2014 by Kristina Panos 17 Comments

[Neven Boyanov] says there’s nothing special about Tinusaur, the bite-sized platform for learning and teaching the joys of programming AVRs. But if you’re dying to gain a deeper understanding of your Arduino or are looking to teach someone else the basics, you may disagree with that assessment.

Tinusaur is easy to assemble and contains only the components necessary for ATTiny13/25/45/85 operation (the kit comes with an ’85). [Neven] saved space and memory by forgoing USB voltage regulator. An optional button cell mount and jumper are included in the kit.

[Neven] is selling boards and kits through the Tinusaur site, or you can get the board from a few 3rd party vendors. His site has some projects and useful guides for assembling and driving your Tinusaur. He recently programmed it to play Conway’s Game of Life on an 8×8 LED matrix. If you’re looking for the zero-entry side of the AVR swimming pool, you can program it from the Arduino IDE. Be warned, though; they aren’t fully compatible.

The project featured in this post is an entry in The Hackaday Prize. Build something awesome and win a trip to space or hundreds of other prizes.

Old Fax Machine Shows Signs Of Life

October 24, 2013 by Adam Fabio 5 Comments

fax1

[Dmitry] is a Moscow based artist. He’s also a an avid circuit bender and hardware hacker. His latest project is entitled “signes de vie” or signs of life. [Dmitry] started with an Arduino and an old thermal fax machine. He removed the thermal print head and replaced it with a row of 10 LEDs. These old fax machines would use rolls of paper, cutting each sheet of as it was printed. [Dmitry] kept the roll system, but treated his paper with fluorescent dye. As the paper passes under the LEDs, it pauses for a moment and the LEDs are flashed. This causes a ghostly glow to remain on the paper for several minutes as the next rows are printed.

While [Dmitry] could have made this the world’s biggest tweet printer, he chose to go a more mathematical route. Each printed row of dots represents a generation of one-dimensional cellular automata. Cellular automation is a mathematical model of generations of cells. All cells exist on a grid, and can be alive or dead. The number of neighboring live cells determines if any given cell will live on to the next generation. One common implementation of cellular automation is Conway’s Game of Life. In [Dmitry’s] implementation, a bank of switches select which of the 256 common cellular automata rules controls the colony. A second bank selects how long each generation lasts – from 1 to 18 seconds.

We really like how the paper becomes a printed, yet temporary history of the colony. [Dmitry] doesn’t say if he’s using a single long strip of paper, or if he created a loop. We’re hoping for the latter. Finally a useful implementation of the old black fax loop prank.

Continue reading “Old Fax Machine Shows Signs Of Life” →