Let’s BUILD a COMPUTER in CONWAY's GAME of LIFE ⠠⠵

one of the most common misconceptions is that complex phenomena arise from complex rules in reality the more rules a system has the more constrained it is emergent behaviors often well emerge from simple discrete rules that have seemingly nothing to do with that like justin go sometimes complexity can hide in the most unexpected places i'm alan zucconi and in this short documentary where we get lost in the endless complexity of a game so apparently simple that its creator called it live life came popularity after appearing in a column written by martin gardner called mathematical games in the october 1970s of scientific american gardner talk about a fantastic combination of this new solitaire game called life that was going to become one of his most successful columns like chess and go life is played with pieces on a board but unlike chess and go it requires no players a zero player game with no winners or losers which result is fully determined by the initial configuration of the pieces on the board a player is only needed to advance the state of the game to the next turn a generation following three simple rules one survival every piece surrounded by two or three other pieces survives for the next turn two depth each piece surrounded by four or more pieces dies from overpopulation likewise every piece next to one or no pieces at all dies from isolation three birth each square adjacent to exactly three pieces gave birth to a new piece the mind behind this bizarre game was john horton conway a brilliant british mathematician fascinated by the exploration of mathematics in its purest form the recreational one conway had carefully designed the rules behind his game of life with the intent of making its evolution unpredictable the idea was to find a simple set of rules which allow the merger of two seemingly disconnected fields engineering and biology some thirty years prior to convoy's game of life in fact stanisworth ulan and john for neumann explore the theory behind self-replicating machines they modeled them using two-dimensional grids updated in discrete steps following precise and deterministic rules they called them cellular automata after its first publication in scientific america life got so popular among mathematicians that a quarterly newsletter called lifeline started appearing it is in there that its editor robin wainwright published a system to classify the many objects patterns as they called that is so appearing in the game class 1 are the so called still lives patterns that do not change over time class 2 are called oscillators and they repeat over a certain number of generation they are classified based on their periods the blinker for instance repeats after two generations hence it has period two many believe that oscillators of any period can be constructed in life and indeed finite oscillators are known to exist for all periods except 19 38 and 41 class 3 groups some of the most studied patterns spaceships those are oscillators that at the end of the cycle somehow find themselves in a different position they effectively move the most well-known and loved is without any doubt the glider discovery in 1969 by the british mathematician richard kenneth guy he was named by john conway himself due to property exhibits called glide symmetry gliders are a smaller spaceship known to exist and yet they play a fundamental role for all mathematicians and computer scientists interested in studying life from a more academic point of view a major breakthrough occurred in 1970 when conway himself after 50 to the first we could find a configuration which grew indefinitely the american mathematician and programmer bill gospel responded with what is now known as the gospel glider gun an oscillator that every 30 generations spawned a new glider that was the first class 4 object to be discovered class 5 patterns behave seemingly radically chaotic as we would say today until they eventually collapse to one of the aforementioned classes but some patents are doomed to a different fate remaining in a perpetual state of chaos forever evolving yet never stabilizing onto something predictable this is the mysterious elusive class 6. life is and remains a fully deterministic game with clear rules and no randomness of any kind yet generally speaking the fate of a pattern cannot be predicted without simulating it directly one could simply wait until a pattern eventually falls into a stable configuration but if it does not if it truly belongs to class 6 then you would wait forever for an answer which will never come the game of life is ultimately undecidable there are many patterns whose fate is easy to predict but in general this cannot be done for an arbitrary pattern that might sound like a bold statement but if we want to understand why we need to go deeper hold on tight to your glider because we're about to build a computer in life the first step to creating a computer is well to understand how computers work in the first place the component that actually performs the computation the processor takes electrical signals and combines them using special circuits called logic gates they can perform very simple mathematical operations using only two values zero and one modern electronic components encode those zeros and ones using two different voltages such as zero and five volts but here in life we need to think creatively we need something that can travel the grid carrying information with it and that can be easily created and destroyed gliders satisfy all of these properties and are therefore the perfect candidates to be used as signal carriers a new glider can be created every 30 generations using a gospel gun so finding one at a specific location every 30 generations means that we have received a pulse a single bit of information and if we do not receive a glider every 30 generations that counts us receiving a we can imagine a traveling glider as a single bit of information moving along an invisible wire this allows encoding any binary signal any sequence of zeros and ones as a series of gliders and all of the binary operations that one can imagine between those sequences can actually be implemented using just three very simple logic gates not and and all the simplest logic gates that we can construct is a not gate it takes a signal at an inverted state in life this means constructing a pattern that will do two things producing a glider when no gliders are received and stopping and incoming gliders from traveling any further it is pretty clear that for the former we need a gospel gun since the not gate has to generate a stream of gliders where nothing is being received for the latter we can exploit another important property of gliders if two of them collide in just the right way they annihilate each other we can carefully place the gospel gun so that it is blocked by the input stream when a glider arrives it will stop the output stream and when no gliders are received the stream will carry on undisturbed an end gate takes two inputs hence two streams and produces a new glider only when he recedes two at the same time we can construct such a pattern by modifying and extending an existing note gate in this construction we can use the glider stream generated from gun a as the output for our logic gate if a is off the output stream will be off as well regardless of the state of b the gun on the right is then placed in such a way that its cloud stream will annihilate any glider coming from a in order for the signal a to survive the gliders from b must block the incoming stream this means that only when both a and b are switched on a gladys stream can travel any further this is indeed an end gate when both input signals are off the stream from the gospel gun would eventually travel outside the gate to stop it from propagating too far we can add a special pattern called a glider eater that well it's an incoming glider the last gate we will construct is a nor gate as the name suggests it produces a glider when it receives at least one from its two input streams once again these can be constructed by modifying an existing and gate the idea is to use the input stream to block a gospel gun which would have otherwise blocked the output string what makes the knot and an or gate so fundamental is that they are a functionally complete set of logic gates it means that they can be chained together to compute the results of any unbearably complex binary expression but will that be enough to build a computer well the answer is no as the information the glider streams only flows in one direction from the top to the bottom what makes computers well computers is essentially the ability to reuse their previous outputs as inputs but luckily for us an entire group of patterns called reflectors allows just that when a glider hits a reflector it bounces off in a different direction this really allows us to read a record glider stream pretty much wherever we want and even to use the result of a logic gate as its input now we really do have everything we need to build a computer starting from one of its most basic components memory blocks one of the simplest form of memory storage in modern electronics is a latch latches are simple circuits that can store a single bit either 0 or 1 and which have 2 inputs called set and reset they are used to set the memory to 1 and 2 reset it back to 0 respectively intuitively you can imagine latches are switches that once pressed remember the state in which they are even when you stop pressing them a very simple set reset latch can be constructed in life using just four gates although that would make for a pretty bulky assembly luckily for us there is a rather inexpensive pattern that can do exactly the same in a much smaller space it uses two gospel guns pointing at each other when a single glider hits a gun in just the right way it introduces a momentary delay in its flow this causes an offset in the glidestream that a gun produces which changes the dynamic of the collision this indeed works as a switch showing the logic gates and memory blocks can be built in a system it's basically enough to prove that at least in theory we can build a proper computer in it these systems are said to be touring complete after the english mathematician alan turing who pretty much came up with a theory behind modern computers as it turns out many other games that pretty much like life does allow players to build structures that can evolve are too incomplete minecraft infini factory prison architect city skylines baba zoo are all unintentionally turing complete and many players myself includers enjoy the challenge of building actual computers in them no matter how small slow or limited those in-game contraptions are they could nonetheless solve the same class of problems that even the most powerful computers can be insuring complete is not measured in gigabytes or teraflops but in which class of problems you can solve and no matter how powerful a turing machine is there are indeed problems that it cannot solve many of those undecidable problems exist with the most famous being the ultim problem deciding whether or not a given program will eventually terminate these should sound very familiar if the rap programs was evolution cannot be predicted and if those very same programs could be included in life then it follows that there must be patterns wars evolution cannot be predicted the mysterious elusive class six now that we know that building a computer in life is technically possible it would be rather anticlimactic to end the video without showing an actual computer built in life in april 2000 paul randall created the first fully functioning computer in the form of a turing machine a construct was architecture was devised by alan turing himself and which often serves as the base to study computers in a more abstract and mathematical sense randall's turing machine takes eleven thousand and forty generations to complete one cycle and the one you see here computes a simple finite state machine with three states randall later released two improved versions of his design including a full universal turing machine a theory machine was programmed is running another turing machine an even bigger result was achieved by nikola luizo in 2016 when he crafted an 8-bit programmable computer compared to a turing machine this is without any doubt a computer in its modern form it supports 8 variables and 13 instructions what makes this endeavor even more surprising is the fact that loiso crafted this button started from only 4 basic patterns a period 60 glider gun a 90 degree glider reflector a glider duplicator and a glider heater once they were used to create knot and an all logic gate it was able to assemble all the necessary circuitry to create basic components for his computer namely set reset latches which he used to create memory blocks and others used to build an arithmetic and logic unit capable of performing simple operations on binary numbers and in case you're wondering this computer is currently busy calculating numbers from the fibonacci series many more people contributed to the creation of some rather outstanding contraptions in life such as this digital clock which comes with its own four-digit display but perhaps one of the most intriguing aspects of being turing complete is not really the fact that you could build a computer in life it is the fact that you can simulate life within life itself [Music] so [Music] so [Music] [Music] [Music] come with game of life is undoubtedly one of the most successful of celravatamata ever discovered some might undoubtedly struggle to understand how simulation they requires well no players could even be described as a game the reality is that life pretty much like any other product worth of the title is a game because for decades he has been capturing the attention of millions of people and 50 years after its original publication thousands still not just playing it are conducting actual research on it as it turns out life is more than just a game conway's achievement was not just discovering what is possibly the most interesting cellular automaton but also to make this entire new field appealing to a much larger audience on the 11th of april 2020 john holton conway died of complication from copied 19. he was 82 years old and many remember him as one of the most charismatic mathematician of his time in awards of his biographer shivan roberts john holton conway is perhaps the most lovable lego maniac he is archimedes nick jagger sabado dali and richard feyman all rolled into one he is one of the greatest living mathematicians with a sly sense of humor a polymath promiscuous curiosity and a compulsion to explain everything about a word to everyone in it according to sir michael etiere former president of the royal society and arbiter of mathematical fashion conway is the most magical mathematician in the world and as the most magical mathematician in the world his legacy as his life lives on [Music] do so [Music] [Music] so [Music] you

Channel: Alan Zucconi

Views: 706,761

Keywords: game of life, conway, life, golly, turing, minecraft, baba is you, logic gates, scientific american, sciam, life in life

Id: Kk2MH9O4pXY

Length: 23min 33sec (1413 seconds)

Published: Mon Oct 05 2020

Reddit Comments

[u/StickyCarpet]

At MIT in the late 70's there were Game of Life displays running on half of the terminal monitors. One guy remarked to me: "Damn, this Game of Life thing has been done to death".

[u/downrightcriminal]

What an absolutely amazing video. Thank you for making and sharing this gem.

[u/surface33]

This is amazing. As someone starting in the field of computer theory there are some connections that are not as clear, specially the And or and not part using life. But the rest its well made!