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

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


सत्यवती ने महर्षि भृगु से अपने तथा अपनी माता के लिए पुत्र का वरदान मांगा।ये जानकर महर्षि भृगु ने यज्ञ किया और तत्पश्चात सत्यवती और उसकी माता को अलग-अलग प्रकार के दो चरू (यज्ञ के लिए पकाया हुआ अन्न) दिए और कहा कि ऋतु स्नान के बाद तुम्हारी माता पुत्र की इच्छा लेकर पीपल का आलिंगन...

...करें और तुम भी पुत्र की इच्छा लेकर गूलर वृक्ष का आलिंगन करना। आलिंगन करने के बाद चरू का सेवन करना, इससे तुम दोनो को पुत्र प्राप्ति होगी।परंतु मां बेटी के चरू आपस में बदल जाते हैं और ये महर्षि भृगु अपनी दिव्य दृष्टि से देख लेते हैं।

भृगु ऋषि सत्यवती से कहते हैं,"पुत्री तुम्हारा और तुम्हारी माता ने एक दुसरे के चरू खा लिए हैं।इस कारण तुम्हारा पुत्र ब्राह्मण होते हुए भी क्षत्रिय सा आचरण करेगा और तुम्हारी माता का पुत्र क्षत्रिय होकर भी ब्राह्मण सा आचरण करेगा।"
इस पर सत्यवती ने भृगु ऋषि से बड़ी विनती की।


सत्यवती ने कहा,"मुझे आशीर्वाद दें कि मेरा पुत्र ब्राह्मण सा ही आचरण करे।"तब महर्षि ने उसे ये आशीर्वाद दे दिया कि उसका पुत्र ब्राह्मण सा ही आचरण करेगा किन्तु उसका पौत्र क्षत्रियों सा व्यवहार करेगा। सत्यवती का एक पुत्र हुआ जिसका नाम जम्दाग्नि था जो सप्त ऋषियों में से एक हैं।