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
For the glider stream to the right to survive an AND gate, the second input needs to cancel the stream coming from the glider gun to the right.

⬇️ 1 𝗔𝗡𝗗 1 = 1
Another small modification allows to construct an OR gate.

⬇️ 0 𝗢𝗥 0 = 0
⬇️ 0 𝗢𝗥 1 = 1 ⬇️ 1 𝗢𝗥 1 = 1
The AND, OR & NOT gates are said to be FUNCTIONALLY COMPLETE, as can be used to construct any logic expression.

This is one step away from TURING COMPLETENESS. ✨

What we need is a memory block! The pattern below works as a SET-RESET LATCH: a simple 1-bit memory register!
LOGIC GATES & LATCHES are everything needed to build an actual computer. 🖥️

If you are interested to learn more about this, this short documentary goes into great length to explain the process of building an actual computer in Conway's Game of Life. ⠠⠵

https://t.co/7e3LKmGfNi
If you enjoyed this thread, follow me for more content like this! 😎

I tweet about Programming, Artificial Intelligence, Game Development & Shader Coding! 🤓

More from Gaming

You May Also Like

The chorus of this song uses the shlokas taken from Sundarkand of Ramayana.

It is a series of Sanskrit shlokas recited by Jambavant to Hanuman to remind Him of his true potential.

1. धीवर प्रसार शौर्य भरा: The brave persevering one, your bravery is taking you forward.


2. उतसारा स्थिरा घम्भीरा: The one who is leaping higher and higher, who is firm and stable and seriously determined.

3. ुग्रामा असामा शौर्या भावा: He is strong, and without an equal in the ability/mentality to fight

4. रौद्रमा नवा भीतिर्मा: His anger will cause new fears in his foes.

5.विजिटरीपुरु धीरधारा, कलोथरा शिखरा कठोरा: This is a complex expression seen only in Indic language poetry. The poet is stating that Shivudu is experiencing the intensity of climbing a tough peak, and likening

it to the feeling in a hard battle, when you see your enemy defeated, and blood flowing like a rivulet. This is classical Veera rasa.

6.कुलकु थारथिलीथा गम्भीरा, जाया विराट वीरा: His rough body itself is like a sharp weapon (because he is determined to win). Hail this complete

hero of the world.

7.विलयगागनथाला भिकारा, गरज्जद्धरा गारा: The hero is destructive in the air/sky as well (because he can leap at an enemy from a great height). He can defeat the enemy (simply) with his fearsome roar of war.