2
$\begingroup$

Proof of universality of Game of Life is straightforward (CAFAQ):

(two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: 111111...) For every 0 in the input byte, the missing glider in the input stream allows a glider from the glider gun to pass, whereas for every 1 in the input byte, a glider in the input stream annihilates the corresponding glider coming from the glider gun. Thus, looking at the output stream from the glider-gun DOWNSTREAM of the collision site, there is a glider (a 1) for every "hole" in the input stream (a 0) and there is a hole (a 0) for every glider (1) in the input stream. Thus, the filtered output of the glider-gun is the logical NOT of the encoded input stream.

And not a universal computer in sight!

By colliding this output stream (call it NOT A if the input steam is A) with another input stream, B, one gets A AND B in the continuation of the input stream B after the collision site.

So what is sufficient for universality is a particle $\alpha$ such that after collision with itself complete annihilation occurs $\alpha + \alpha = 0$. This seems to be an easy requirement. However, ECA 110 (or Rule 110) was proved via simulating cyclic tag system. And ECA 54 was not yet proven to be universal.

Both ECA 110 and ECA 54 have rich glider/particle sets. I did not yet dig deep into the glider sets. I first want to ask:

Was the contrast between simplicity of $\alpha + \alpha = 0$ and problems with proving universality of ECA examined somehow? Are the particle systems categorized in some way, to explain why rich particle systems are not necessary universal, while system as simple as $\alpha + \alpha = 0$ can be universal?

$\endgroup$
  • $\begingroup$ Can you give a definition of "rich particle systems"? Furthermore the "gadgets" needed to simulate a turing machine with the game of life are rather complex (see for example rendell-attic.org/gol/tm.htm and rendell-attic.org/gol/tmdetails.htm) $\endgroup$ – Marzio De Biasi Mar 23 '12 at 23:14
  • $\begingroup$ To perform universal computations the NOT and AND gates are sufficient. The TM explicit simulation is rather a nice toy. Rich particle system – hard time defining it, but if you look into or recall the Cook's paper on Rule 110 you will see how many gliders/particles the CA has. $\endgroup$ – Mooncer Mar 23 '12 at 23:31
  • $\begingroup$ ok, but the NOT and AND gates need to be "combined": you also need "wires" (ideal lines on the 2d space) and "pulses" (glider gun) and "flip-flops" (particular cell configurations), so calling it an $\alpha + \alpha = 0$ system is a little reductive. Furthermore you are asking why in a 2D CA (Game of Life) things are simpler than in a 1D CA (ECA 54). However someone else will surely give a better answer. $\endgroup$ – Marzio De Biasi Mar 23 '12 at 23:52
  • $\begingroup$ another note: the first proofs of the universality of one dimensional CAs relied on an explicit simulation of an universal turing machine, so it's not just a nice toy :-). I think (but I'm not an expert) that tag systems were used later to prove universality of smaller and more elementary CAs. $\endgroup$ – Marzio De Biasi Mar 24 '12 at 0:22
  • 1
    $\begingroup$ @Boordet: for a discussion on the sufficient/necessary properties in "universal systems" you can see: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.6267 or arxiv.org/pdf/cs/0404021v4.pdf (both with many additional references). $\endgroup$ – Marzio De Biasi Mar 24 '12 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.