We often hear the term “Turing-complete” without giving much thought as to what the implications might be. Technically Microsoft PowerPoint, Portal 2, and Magic: the Gathering all are Turing-complete, what of it? Yet, each time someone embarks on an incredible quest of perseverance and creates a computer in one of these mediums, we stand back in awe.
[Nicolas Loizeau] is one such individual who has created a computer in Conway’s Game of Life. Unlike electricity, the Game of Life uses gliders as signals. Because two orthogonal gliders can cancel each other out or form a glider eater if they intersect with a good phase shift, the basic logic gates can be formed from these interactions. This means the space between gates is crucial as signals need to be in phase alignment. The basic building blocks are a period-60 gun, a 90-degree glider reflector, a glider duplicator, and a glider eater.
All the Python code that generates these structures is on GitHub as the sheer size of the machine couldn’t possibly be placed by hand. The Python includes scripts to assemble the basic programs as a bank of selectable glider generators. It’s all based on Golly, which is an excellent program for simulating Conway’s Game of Life, among other things. While this isn’t the first computer in the Game of Life as [Paul Rendell] published a design in 2000 and [Adam Goucher] published a Spartan universal computer constructor in 2009, we think this is a particularly beautiful one.
The actual architecture has an 8-bit data bus, a 64-byte memory with two read ports, a ROM with 21 bits per line, and a one-hot encoded ALU supporting 8 different operations. Instructions have a 4-bit opcode which is decoding in a few different instructions. The clock is four loops, formed by the glider reflectors as the glider beams rotate. This gives the computer four stages: execution, writing, increment PC, and write PC to memory.
The Game of Life is an excellent example of Cellular Automaton (CA). There are several other types of CA’s and the history behind them is fascinating. We’ve covered this field before and delved into this beautiful fringe of computer science. Check out the video below to truly get a sense of the scale of the machine that [Nicolas] has devised.
> Technically Microsoft PowerPoint, Portal 2, and Magic: the Gathering all are Turing-complete,
No system with bounded storage is Turing complete (and all behaviors of evolving computing systems with bounded numbers of states are decidable…).
And I mean, that thing can’t even run itself…
By that logic nothing that exists is turing complete and therefore the phrase has little use.
What people mean is that a variant of the model, with unbounded storage, is Turing complete.
The mathematical definition of a turning machine says no such thing. It only mentions “infinite” to specifically disallow it for nearly all aspects of the machine.
Having infinite storage is allowed, but only if it is filled with ‘no-op’ blank instructions. The moment you use that infinite storage for anything else, it is no longer a turning machine.
Unbounded, not infinite.
Oh, I was giving him the benefit of the doubt, since not being infinite is the only limitation mentioned in the definition.
If they literally meant “unbounded”, that would just be completely flat out wrong, the bounding limits are explicitly defined on every aspect of a turning machine.
The tape of the Turing machine is defined to be unbounded.
@Artenz No, it really is not. “Q” is a tape with a finite set of states. “Gamma” is a finite set of tape symbols. Those are the only requirements for storage. There’s only 7 components to the formula, you can go and check this yourself to see.
Turing said the tape itself may be infinitely long, but not must be. It must be bounded however.
Alen Turning also defined the result of running out of tape, as it halts the system.
Why would the maker of the definition detail what happens when you run out of tape, if your claim the tape must be unbounded was true? Why didn’t Alen say it must be unbounded either?
https://plato.stanford.edu/entries/turing-machine/
A Turing Machine halts when it reaches the halting state. It cannot run out of tape. Look at section 1.3 of the article you quoted. The transition function produces L or R to indicate that the tape should move Left or Right. There is no case for having reached the “end of the tape”.
Hey, Kid?
The tape has to be unbounded. Really. No, it doesn’t have to be infinite… but the machine has to be able to *add* as much tape as it wants any time it wants. At any given moment, your tape is indeed of finite length… but you *always have to be able to go down to the store and by more tape*. There can be *no* a priori limit on how large your tape *can* get. This is a simple distinction that you’re meant to get the first time somebody explains Turing machines.
The whole idea of Turing completeness doesn’t even work unless you have unbounded storage, because you’re meant to be able to simulate *any* Turing machine, regardless of the size of *its* tape. Which means *your* tape (or other storage) has to be big enough to represent *any* machine* I give you. If your bound is b, I am free to give you a machine that uses 2b storage, and you are hosed.
And none of the theorems about Turing machines or their equivalents apply unless the tape is truly unbounded. For example, you can solve the halting problem for bounded state size. If the machine ever returns to a previous state, then the program does not halt. Since there are a finite number of states, the machine can’t run forever without returning to one of them.
And, yeah, duh, I know people don’t mean *literally* Turing complete…
MtG is Turing complete?!
I’m now imagining some dystopian future where silicon is outlawed and halls full of geeks are paid in Doritos and Mountain Dew to play MtG all day to compute data.
Paradise?
Dr Who has Logopolis: https://en.m.wikipedia.org/wiki/Logopolis
Ob-xkcd: https://xkcd.com/505/
Also, a computer like this was a fun little bit in The Three Body Problem
Super cool.
Since gliders move “diagonally”, I feel like the standard view for Life should actually be 45 degrees rotated from what we use now. It would make this labyrinth of mirrors and beams look like an integrated circuit — people design rectilinear things horizontally and vertically.
Portal 2? I knew that logic gates were possible in that game, but I didn’t know that anyone had made actual computers with it. I guess it’s time for me to poke around and see if I can find one.
https://steamcommunity.com/sharedfiles/filedetails/?id=1788462873
Now code it to play the game of life……………………………..
Already been done: https://youtu.be/xP5-iIeKXE8?si=Rh_8-KrLds8KO4wz
Anything that can hose those very simple rules, or other simple Turing complete rules is potentially capable of any computation that is possible on a classical computer. Even an automata propagating through the quantum foam with the substrate being a web of virtual particle pairs. Most people look and a Feynman diagram and assume that it is finite rather than the truth which is that it is part of an almost infinite web of interactions, because as virtual particles manifest they need not annihilate each other but are free to interact with and annihilate another opposite particle, this is why their Feynman diagrams are not isolated and can be part of a web. In fact this has to happen for black holes to have an event horizon, one pair member can fall into the hole leaving its anti twin to interact with another member of a different pair, this then sets off a cascade as the entire universe tries to balance the equation and we could assume that the balance is entirely maintained within the vicinity of the black hole, but is there any reason that physics dictates this to be the only case? I say no, so we have this web of interactions and the nature of them can form local patterns which can propagate, this is what we see in 2D or greater Cellular Automata, which have also been shown to be Turing complete, i.e. capable of hosting an A.I. So do the math, how dense is the quantum foam which covers the entire universe, how complex a CA pattern can it host in a given volume of space. Could we see it hosting human-level intelligence in areas as small as a single ångström?
FWIW this calls to mind a related fictional account some might find interesting. I don’t recall all of the details, but in David Brin’s classic 1993 SF novel, Glory Season, dedicated Game of Life machines are portrayed as being widely used in popular battle-of-the-patterns competitions The protagonists manage to adapt them as crypto messaging devices, programmed via the initial pattern set up.