5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Feb 26, 2011 at 19:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Feb 28, 2011 at 4:48
  • $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Feb 28, 2011 at 10:49
  • $\begingroup$ 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. $\endgroup$
    – N. Virgo
    Mar 25, 2015 at 7:18

3 Answers 3

Reset to default
7
$\begingroup$

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), suitably aligned large blocks of live cells act as barriers and mirrors, isolating anything beyond them.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Feb 28, 2011 at 21:00
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. Do you have any idea about how such cellular automata would be defined? $\endgroup$
    – Antonio Valerio Miceli-Barone
    Feb 28, 2011 at 21:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Feb 28, 2011 at 21:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Mar 1, 2011 at 23:18
  • $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Mar 2, 2011 at 2:09
0
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.