<p>The conjecture is not only false, but false for standard and seemingly-minimal models of reversible CA. Specifically, in Margolus' billiard ball model (with the <a href="http://en.wikipedia.org/wiki/Block_cellular_automaton">Margolus neighborhood</a>), suitably aligned large blocks of live cells act as barriers and mirrors, isolating anything beyond them. </p>

CC BY-SA 2.5
2011-02-28T21:00:51.277Z
I was aware of Margolus block cellular automaton and the billiard ball model, but I thought that while it allowed to implement arbitrary reversible finite state automata, it wasn't obvious to me that it was Turing-complete. Now that I'm thinking about it more, I see that it's probably possible to implement a reversible Turing machine using an infinite periodic reversible circuit, and thus a Margolus block CA.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-02-28T18:16:47.297Z
2011-02-28T18:16:47.297Z
David Eppstein
<p>I've been thinking about your problem a little more, and I think separating the Turing-universality from the isolation part may be quite hard. For example, consider a Turing-universal CA with states 0,1,2, where the Turing-universal computations never use two 2's in adjacent cells. You could also have arrange the rules so that if there are two 2's in adjacent cells, they will never be changed. I am fairly sure that one can devise such a Turing-universal CAs so that if you without the state 2, the CA is not universal. You then can't just drop the state 2, as required by property 1. I think this would also evade your new property 2, although maybe not if you required the CA to use all the rules. But it seems like it might be quite difficult to come up with a reformulation which would evade all examples such as this. </p>

CC BY-SA 2.5
2011-02-28T21:20:01.040Z
Thanks for your answer. Do you have any idea about how such cellular automata would be defined?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-02-28T21:40:31.967Z
Think of state 2 as the head on a universal Turing machine. Clearly the automaton is universal if there's just one head, it doesn't do anything without any heads, and with more than one head, you can get isolation. To simulate the traditional model of a Turing machine, you would need several different head states, but that still gives an example which evades your reformulations.
Peter Shor 
CC BY-SA 2.5
2011-03-01T23:18:52.543Z
I think the requirement that the Turing-universal computations be able to access every rule (for every rule, there is some input to the universal computation which uses that rule) is maybe a better notion of minimality than the one I proposed before.
Joshua Grochow
CC BY-SA 2.5
2011-03-02T02:09:14.433Z
Possibly, but I'm not very sure about it. Anyway, If Eppstein remark that Margolus block CA is Turing complete is correct (and if my understanding is right, it is), then my conjecture is trivially falsified.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-02-28T18:18:49.807Z
2011-02-28T18:18:49.807Z
Peter Shor 
<p>I think your definition of isolation is flawed, in that it allows what you called the "interior" to influence the "exterior". In particular reversibility is a non issue since a Turing machine can just throw useless information away instead of erasing it.</p>

<p>If you define an isolated region the other way around, such that <strong>the outside is not influenced by the inside</strong>, then I think you cannot have a Deterministic Turing Machine in a finite isolated region with reversible rules.</p>

<p>The fact that the isolated region shall not be influenced by the outside is not so much related to reversibility and is more about determinism or knowing what your machine does without having to know the full universe, and if that's a given too (eg if each cell of the exterior are initially at a quiescent state), then the dynamics is still reversible when restrained to the isolated region, which is finite, and thus its orbits are finite, in other word, it is periodic.</p>

<p>Good luck defining the result of a computation when the machine reverts periodically to its initial state. Might be possible, but it does not check the definition of Turing complete I know.</p>

<p>Also, there is the question of how you are Turing complete within a finite space. Where is the infinite tape?</p>

CC BY-SA 4.0
2018-11-22T13:02:32.807Z
2018-11-22T15:43:18.253Z
2018-11-22T15:43:18.253Z
4xel
<p>I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought.</p>

<p>Consider Turing-complete reversible cellular automata.</p>

<p>For instance, Wolfram's Rule 110 cellular automaton is Turing-complete, but, if I understand correctly, it's not reversible. However, it can be made reversible by converting it into a second-order cellular automaton and then implementing the second-order CA as a first-order CA with a larger cell state space.</p>

<p>My question is whether it's possible to define a finite region of cells that is completely isolated from the outside.</p>

<p>More specifically: if there exist an initial state of a finite connected region of cells (let's call it <em>Vault</em>), which is composed of a connected region <em>Interior</em> surronded by another region <em>Wall</em>, such that the state of the <em>Interior</em> at any time <em>t</em> depends only on the previous state of <em>Interior</em>.</p>

<p>My conjecture is that such isolated regions are impossible.</p>

<p>My intuition stems from the fact that Turing-complete reversible CA can be considered very simple models of physical reality (and proponents of the digital physics hypothesis argue that the physical world is actually a cellular automaton). If I understand correctly, totally isolated physical systems can't exist, thus I conjecture by analogy that this should also apply to all Turing-complete reversible CA.
(Turing-incomplete or irreversible CA can have isolated regions, but they are probably not good models of fundamental physical reality)</p>

<p>Has anybody already proved or disproved this assertion? Or do you have any thoughts about it?</p>

<p>UPDATE:</p>

<p>As Shor pointed out in the comments, the conjecture as stated above is false, since it is possible to use some states which are not required for Turing-completeness to achieve isolation.</p>

<p>I will try to reformulate the question in a way that the conjecture may possibly hold by adding more requirements on the cellular automaton.</p>

<p>I'm thinking of two reformulations based on two different additional requirements:</p>

<ol>
<li><p><i>Minimal universality</i>: As noted by Grochow, we can define a Turing-complete CA to be "<i>Minimally universal</i>" iff the CA obtained by removing one cell state (and the corresponding rules) is no longer Turing-complete.</p><p>Thus, the conjecture is: <i>There does not exist a minimally universal reversible CA such that isolated regions can be defined.</i></p></li>
<li><p><i>Total harnessability</i>: We may say that the computational power of a Turing-complete CA is <i>totally harnessable</i> iff there exist undecidable properties regarding all cell states.</p><p>More specifically, we define a CA to be <i>totally harnessable</i> iff $\forall s \in CellStates \ \exists$ a computable initial configuration $x(t_0,\,i)$, a finite set of cell indexes $Q$, a vector of cell states $\bar{q}$ containing $s$ and predicate $p(x,\,t)\ \equiv\ \bigwedge_{i \in Q}x(t,\,i)=q_i $ such that the question "$\exists t:\ p(x,\,t)=True$" is undecidable, and the question obtained by removing from predicate $p$ the conditions on state $s$ is decidable.</p><p>Thus the conjecture is: <i>There does not exist a totally harnessable Turing-complete reversible CA such that isolated regions can be defined.</i></p></li>
</ol>

CC BY-SA 2.5
2011-02-26T19:52:05.270Z
If you take a Turing-complete reversible CA and add extra states and rules, it remains Turing-complete. So you can have a Turing-complete reversible CA in which isolation is possible, where the states you use for isolation are not those you use for universal computation. You might want to think about the formulation of your question more closely ... there may be some reasonable way of reformulating it so your conjecture is true.
Peter Shor 
CC BY-SA 2.5
2011-02-28T04:48:53.730Z
@user1749: One way to (partially?) sidestep @Peter Shor's idea is to require that the "universal part" of your machine be able to access all the states and use all the rules of the CA. One interpretation (not the only one) of this would be to only consider "minimally universal" CAs, in which the removal of any state (and any rules pertaining to that state) would cause it to no longer be universal.
Joshua Grochow
CC BY-SA 2.5
2011-02-28T10:49:35.913Z
Yes, I thought about that. It may be interesting to consider "minimally universal" automata, but perhaps the concept is a bit too restrictive. I was thinking of extending the definition by requiring the existence of undecidable questions regarding all states.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2015-03-25T07:18:05.180Z
I realise this is a very old post, but just in case it's helpful to you or someone else, second-order CAs don't necessarily behave in similar ways to the corresponding first-order CA. So making rule 110 second-order will make it reversible, but won't necessarily preserve its computational completeness. (I don't know whether it does or not.) I think it's probably not that hard to find a minimal computationally complete 1D CA though.
N. Virgo
<computability><physics><cellular-automata>
Isolation in Turing-complete reversible cellular automata
Antonio Valerio Miceli-Barone
# Isolation in Turing-complete reversible cellular automata

(Asked by: username_0 on 2011-02-26)

I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought.

Consider Turing-complete reversible cellular automata.

For instance, Wolfram's Rule 110 cellular automaton is Turing-complete, but, if I understand correctly, it's not reversible. However, it can be made reversible by converting it into a second-order cellular automaton and then implementing the second-order CA as a first-order CA with a larger cell state space.

My question is whether it's possible to define a finite region of cells that is completely isolated from the outside.

More specifically: if there exist an initial state of a finite connected region of cells (let's call it *Vault*), which is composed of a connected region *Interior* surronded by another region *Wall*, such that the state of the *Interior* at any time *t* depends only on the previous state of *Interior*.

My conjecture is that such isolated regions are impossible.

My intuition stems from the fact that Turing-complete reversible CA can be considered very simple models of physical reality (and proponents of the digital physics hypothesis argue that the physical world is actually a cellular automaton). If I understand correctly, totally isolated physical systems can't exist, thus I conjecture by analogy that this should also apply to all Turing-complete reversible CA.
(Turing-incomplete or irreversible CA can have isolated regions, but they are probably not good models of fundamental physical reality)

Has anybody already proved or disproved this assertion? Or do you have any thoughts about it?

UPDATE:

As Shor pointed out in the comments, the conjecture as stated above is false, since it is possible to use some states which are not required for Turing-completeness to achieve isolation.

I will try to reformulate the question in a way that the conjecture may possibly hold by adding more requirements on the cellular automaton.

I'm thinking of two reformulations based on two different additional requirements:

1. *Minimal universality*: As noted by Grochow, we can define a Turing-complete CA to be "*Minimally universal*" iff the CA obtained by removing one cell state (and the corresponding rules) is no longer Turing-complete.

   Thus, the conjecture is: *There does not exist a minimally universal reversible CA such that isolated regions can be defined.*
2. *Total harnessability*: We may say that the computational power of a Turing-complete CA is *totally harnessable* iff there exist undecidable properties regarding all cell states.

   More specifically, we define a CA to be *totally harnessable* iff $\forall s \in CellStates \ \exists$ a computable initial configuration $x(t\_0,\,i)$, a finite set of cell indexes $Q$, a vector of cell states $\bar{q}$ containing $s$ and predicate $p(x,\,t)\ \equiv\ \bigwedge\_{i \in Q}x(t,\,i)=q\_i $ such that the question "$\exists t:\ p(x,\,t)=True$" is undecidable, and the question obtained by removing from predicate $p$ the conditions on state $s$ is decidable.

   Thus the conjecture is: *There does not exist a totally harnessable Turing-complete reversible CA such that isolated regions can be defined.*

**Tags:** computability, physics, cellular-automata
> **Comments:**
> **username_1**: If you take a Turing-complete reversible CA and add extra states and rules, it remains Turing-complete. So you can have a Turing-complete reversible CA in which isolation is possible, where the states you use for isolation are not those you use for universal computation. You might want to think about the formulation of your question more closely ... there may be some reasonable way of reformulating it so your conjecture is true.  
> **username_2**: @user1749: One way to (partially?) sidestep @Peter Shor's idea is to require that the "universal part" of your machine be able to access all the states and use all the rules of the CA. One interpretation (not the only one) of this would be to only consider "minimally universal" CAs, in which the removal of any state (and any rules pertaining to that state) would cause it to no longer be universal.  
> **username_0**: Yes, I thought about that. It may be interesting to consider "minimally universal" automata, but perhaps the concept is a bit too restrictive. I was thinking of extending the definition by requiring the existence of undecidable questions regarding all states.  
> **username_3**: I realise this is a very old post, but just in case it's helpful to you or someone else, second-order CAs don't necessarily behave in similar ways to the corresponding first-order CA. So making rule 110 second-order will make it reversible, but won't necessarily preserve its computational completeness. (I don't know whether it does or not.) I think it's probably not that hard to find a minimal computationally complete 1D CA though.  

---

## 3 answers

### Answer by username_4 on 2011-02-28. Score: 7 | Accepted answer

The conjecture is not only false, but false for standard and seemingly-minimal models of reversible CA. Specifically, in Margolus' billiard ball model (with the [Margolus neighborhood](http://en.wikipedia.org/wiki/Block_cellular_automaton)), suitably aligned large blocks of live cells act as barriers and mirrors, isolating anything beyond them.

> **Comments:**
> **username_0**: I was aware of Margolus block cellular automaton and the billiard ball model, but I thought that while it allowed to implement arbitrary reversible finite state automata, it wasn't obvious to me that it was Turing-complete. Now that I'm thinking about it more, I see that it's probably possible to implement a reversible Turing machine using an infinite periodic reversible circuit, and thus a Margolus block CA.  

---

### Answer by username_1 on 2011-02-28. Score: 6

I've been thinking about your problem a little more, and I think separating the Turing-universality from the isolation part may be quite hard. For example, consider a Turing-universal CA with states 0,1,2, where the Turing-universal computations never use two 2's in adjacent cells. You could also have arrange the rules so that if there are two 2's in adjacent cells, they will never be changed. I am fairly sure that one can devise such a Turing-universal CAs so that if you without the state 2, the CA is not universal. You then can't just drop the state 2, as required by property 1. I think this would also evade your new property 2, although maybe not if you required the CA to use all the rules. But it seems like it might be quite difficult to come up with a reformulation which would evade all examples such as this.

> **Comments:**
> **username_0**: Thanks for your answer. Do you have any idea about how such cellular automata would be defined?  
> **username_1**: Think of state 2 as the head on a universal Turing machine. Clearly the automaton is universal if there's just one head, it doesn't do anything without any heads, and with more than one head, you can get isolation. To simulate the traditional model of a Turing machine, you would need several different head states, but that still gives an example which evades your reformulations.  
> **username_2**: I think the requirement that the Turing-universal computations be able to access every rule (for every rule, there is some input to the universal computation which uses that rule) is maybe a better notion of minimality than the one I proposed before.  
> **username_0**: Possibly, but I'm not very sure about it. Anyway, If Eppstein remark that Margolus block CA is Turing complete is correct (and if my understanding is right, it is), then my conjecture is trivially falsified.  

---

### Answer by username_5 on 2018-11-22. Score: 0

I think your definition of isolation is flawed, in that it allows what you called the "interior" to influence the "exterior". In particular reversibility is a non issue since a Turing machine can just throw useless information away instead of erasing it.

If you define an isolated region the other way around, such that **the outside is not influenced by the inside**, then I think you cannot have a Deterministic Turing Machine in a finite isolated region with reversible rules.

The fact that the isolated region shall not be influenced by the outside is not so much related to reversibility and is more about determinism or knowing what your machine does without having to know the full universe, and if that's a given too (eg if each cell of the exterior are initially at a quiescent state), then the dynamics is still reversible when restrained to the isolated region, which is finite, and thus its orbits are finite, in other word, it is periodic.

Good luck defining the result of a computation when the machine reverts periodically to its initial state. Might be possible, but it does not check the definition of Turing complete I know.

Also, there is the question of how you are Turing complete within a finite space. Where is the infinite tape?


---

