<p>Proof of universality of Game of Life is straightforward  (<a href="http://cafaq.com/lifefaq/index.php" rel="nofollow">CAFAQ</a>):</p>

<blockquote>
  <p>(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.</p>
  
  <p>And not a universal computer in sight!</p>
  
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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:</p>

<p><strong>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 <em>rich</em> particle systems are not necessary universal, while system as simple as $\alpha + \alpha = 0$ can be universal?</strong></p>

CC BY-SA 3.0
2012-03-23T23:14:57.777Z
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 http://rendell-attic.org/gol/tm.htm and http://rendell-attic.org/gol/tmdetails.htm)
Marzio De Biasi
CC BY-SA 3.0
2012-03-23T23:31:38.410Z
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.
Mooncer
CC BY-SA 3.0
2012-03-23T23:52:25.933Z
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.
Marzio De Biasi
CC BY-SA 3.0
2012-03-24T00:22:48.423Z
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.
Marzio De Biasi
CC BY-SA 3.0
2012-03-24T00:49:38.927Z
I was thinking of mentioning the Life/Turing complete equivalence somewhere but couldnt think of a question & it appears yours is the 1st mention here on TCS stackexchange of this very interesting proof [apparently originally due to john conway but I dont have a ref]. it appears to me that study of TM completeness in CAs is still in a very early stage and it seems quite plausible that it can be found in more 1d rules... moreover as you note there is generally more "wiggle" in proofs of TM completeness in CA arena compared with outside of it with use of periodic tape patterns.
vzn
CC BY-SA 3.0
2012-03-24T00:50:00.247Z
@MarzioDeBiasi When I wrote about the nice toy I only referred to the tm.html site. As far as I understand the author simulated a physical machine, not only the mathematical model. On the other hand I would have hard time defining what is the difference. Tag Systems are IMO far more basic than TM so simulating them does not look so impressive. I like the tag systems, they are so basic! And the cyclic TS are even more basic.
Mooncer
CC BY-SA 3.0
2012-03-24T00:50:10.777Z
@MarzioDeBiasi You are right about the pulses. This is indeed an exclusive feature not related to the $\alpha + \alpha$ collision. The wires are rather obvious. AND ALL THIS: pulses, wires, particle collisions, maybe others – is the analysis, classification that I am asking about. Are they all needed? Does having one of the features allow to ignore some other? Etc.
Mooncer
CC BY-SA 3.0
2012-03-24T01:37:34.723Z
@Boordet: for a discussion on the sufficient/necessary properties in "universal systems" you can see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.6267 or http://arxiv.org/pdf/cs/0404021v4.pdf (both with many additional references).
Marzio De Biasi
<computability><universal-computation><cellular-automata>
Particle collisions for universal computation
Mooncer
# Particle collisions for universal computation

(Asked by: username_0 on 2012-03-23)

Proof of universality of Game of Life is straightforward ([CAFAQ](http://cafaq.com/lifefaq/index.php)):

> (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?**

**Tags:** computability, universal-computation, cellular-automata
> **Comments:**
> **username_1**: 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 http://rendell-attic.org/gol/tm.htm and http://rendell-attic.org/gol/tmdetails.htm)  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: I was thinking of mentioning the Life/Turing complete equivalence somewhere but couldnt think of a question & it appears yours is the 1st mention here on TCS stackexchange of this very interesting proof [apparently originally due to john conway but I dont have a ref]. it appears to me that study of TM completeness in CAs is still in a very early stage and it seems quite plausible that it can be found in more 1d rules... moreover as you note there is generally more "wiggle" in proofs of TM completeness in CA arena compared with outside of it with use of periodic tape patterns.  
> **username_0**: @MarzioDeBiasi When I wrote about the nice toy I only referred to the tm.html site. As far as I understand the author simulated a physical machine, not only the mathematical model. On the other hand I would have hard time defining what is the difference. Tag Systems are IMO far more basic than TM so simulating them does not look so impressive. I like the tag systems, they are so basic! And the cyclic TS are even more basic.  
> **username_0**: @MarzioDeBiasi You are right about the pulses. This is indeed an exclusive feature not related to the $\alpha + \alpha$ collision. The wires are rather obvious. AND ALL THIS: pulses, wires, particle collisions, maybe others – is the analysis, classification that I am asking about. Are they all needed? Does having one of the features allow to ignore some other? Etc.  
> **username_1**: @Boordet: for a discussion on the sufficient/necessary properties in "universal systems" you can see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.6267 or http://arxiv.org/pdf/cs/0404021v4.pdf (both with many additional references).  

---

## 0 answers

