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