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

Rig Ved 1.36.7

To do a Namaskaar or bow before someone means that you are humble or without pride and ego. This means that we politely bow before you since you are better than me. Pranipaat(प्राणीपात) also means the same that we respect you without any vanity.

1/9


Surrendering False pride is Namaskaar. Even in devotion or bhakti we say the same thing. We want to convey to Ishwar that we have nothing to offer but we leave all our pride and offer you ourselves without any pride in our body. You destroy all our evil karma.

2/9

We bow before you so that you assimilate us and make us that capable. Destruction of our evils and surrender is Namaskaar. Therefore we pray same thing before and after any big rituals.

3/9

तं घे॑मि॒त्था न॑म॒स्विन॒ उप॑ स्व॒राज॑मासते ।
होत्रा॑भिर॒ग्निं मनु॑षः॒ समिं॑धते तिति॒र्वांसो॒ अति॒ स्रिधः॑॥

Translation :

नमस्विनः - To bow.

स्वराजम् - Self illuminating.

तम् - His.

घ ईम् - Yours.

इत्था - This way.

उप - Upaasana.

आसते - To do.

स्त्रिधः - For enemies.

4/9

अति तितिर्वांसः - To defeat fast.

मनुषः - Yajman.

होत्राभिः - In seven numbers.

अग्निम् - Agnidev.

समिन्धते - Illuminated on all sides.

Explanation : Yajmans bow(do Namaskaar) before self illuminating Agnidev by making the offerings of Havi.

5/9
दधीचि ऋषि को मनाही थी कि वह अश्विनी कुमारों को किसी भी अवस्था में ब्रह्मविद्या का उपदेश नहीं दें। ये आदेश देवराज इन्द्र का था।वह नहीं चाहते थे कि उनके सिंहासन को प्रत्यक्ष या परोक्ष रुप से कोई भी खतरा हो।मगर जब अश्विनी कुमारों ने सहृदय प्रार्थना की तो महर्षि सहर्ष मान गए।


और उन्होनें ब्रह्मविद्या का ज्ञान अश्विनि कुमारों को दे दिया। गुप्तचरों के माध्यम से जब खबर इन्द्रदेव तक पहुंची तो वे क्रोध में खड़ग ले कर गए और महर्षि दधीचि का सर धड़ से अलग कर दिया।मगर अश्विनी कुमार भी कहां चुप बैठने वाले थे।उन्होने तुरंत एक अश्व का सिर महर्षि के धड़ पे...


...प्रत्यारोपित कर उन्हें जीवित रख लिया।उस दिन के पश्चात महर्षि दधीचि अश्वशिरा भी कहलाए जाने लगे।अब आगे सुनिये की किस प्रकार महर्षि दधीचि का सर काटने वाले इन्द्र कैसे अपनी रक्षा हेतु उनके आगे गिड़गिड़ाए ।

एक बार देवराज इन्द्र अपनी सभा में बैठे थे, तो उन्हे खुद पर अभिमान हो आया।


वे सोचने लगे कि हम तीनों लोकों के स्वामी हैं। ब्राह्मण हमें यज्ञ में आहुति देते हैं और हमारी उपासना करते हैं। फिर हम सामान्य ब्राह्मण बृहस्पति से क्यों डरते हैं ?उनके आने पर क्यों खड़े हो जाते हैं?वे तो हमारी जीविका से पलते हैं। देवर्षि बृहस्पति देवताओं के गुरु थे।

अभिमान के कारण ऋषि बृहस्पति के पधारने पर न तो इन्द्र ही खड़े हुए और न ही अन्य देवों को खड़े होने दिया।देवगुरु बृहस्पति इन्द्र का ये कठोर दुर्व्यवहार देख कर चुप चाप वहां से लौट गए।कुछ देर पश्चात जब देवराज का मद उतरा तो उन्हे अपनी गलती का एहसास हुआ।