Fifty years have passed since CONWAY'S GAME OF LIFE firstly appeared on a column called "Mathematical Games" on @sciam.
While most Programmers & Computer Science enthusiasts are familiar with it, not many know that the game is actually TURING COMPLETE.
Let's see why. โ โ ต
๐งต๐
The quickest way to prove that a system is TURING COMPLETE is to show that it allows for the constructions of LOGIC GATES. ๐ฅ๏ธ
So, let's see how the ๐๐ก๐, ๐ข๐ฅ and ๐ก๐ข๐ง gates can actually be constructed in Conway's Game of Life...
Firstly, we need to find a way to encode binary signals.
One very popular choice is to use a stream of GLIDERS. The so-called GOSPER GLIDER GUN can generated a new glider every 30 generations. ๐ซ
Hence, receiving a glider every 30 generations counts as a "1".
When two GLIDERS hit each other in just the right way, they both get destroyed. ๐ฅ
This means that a GLIDER GUN can stop an incoming glider stream!
We can exploit this mechanism to simulate a NOT gate:
โฌ๏ธ ๐ก๐ข๐ง 0 = 1 โฌ๏ธ ๐ก๐ข๐ง 1 = 0
With the same principle, and AND gate can be also constructed by extending a NOT gate.
โฌ๏ธ 0 ๐๐ก๐ 1 = 0 โฌ๏ธ 1 ๐๐ก๐ 0 = 0