# Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.

I haven't even found a definition anywhere. It feels like NCAs can't be equivalent to CAs (not in the same lattice at least), even though I can convert a NFSM to a FSM the possibly exponential growth of the required states doesn't fit to the CA definition, it would need a higher dimensional lattice (i.e. more local neighbours).

So, are NCAs and CAs equivalent ? Are there papers or books discussing this ?

I think you should define precisely what you mean by equivalent, and possibly what kind of CA you are willing to consider, with what communication grid. So I will just assume the simplest interpretation.

Given that it is fairly easy to build deterministic cellular automata with Turing power (even with a 1 dimemsional grid), and that according to the current wisdom of the Church-Turing Thesis, we have little chance to improve on that, my best bet is that non-deterministic cellular automata cannot be more powerful than deterministic ones. Given that adding non-determinism can only increase the computational power, i.e. a deterministic automaton is a special case of non-determinism, whe should not expect non-deterministic cellular automata to be less powerful than deterministic ones.

Hence, in terms of computational power, deterministic and non-deterministic cellular automata are equivalent.

• Yes, I meant it in the simplest interpretation. By equivalence I mean that for a given NCA a CA can be constructed which would behave exactly the same (i.e. for a given configuration it would write the same stuff onto the grid). – rtur Jun 7 '15 at 10:06

I gave it a little more thought, this part of my question:

"NCAs can't be equivalent to CAs [..] possibly exponential growth of the required states doesn't fit to the CA definition"

is false. The number of states doesn't matter, It would still be the same lattice. E.g. Let $A$ be a CA on $Z$. The state of a cell $q$ is either $0$ or $1$, all cells are $0$ at first. Each cell sees only it's direct neighbours. Then consider this state transition function $\delta$:

+---------------------------------+
| $q_l$ | $q_t$ | $q_r$ | $q_{t+1}| |-------+-------+-------+---------| | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | +---------------------------------+  It doesn't matter whether I would describe this as a DFSM or NFSM, as long as both accept the same input string, e.g.$q_lq_tq_r$. Here is a NFSM and a DFSM version describing$\delta$, both accept the same string, accepting means$q_{t+1}\$ will be 1, else 0. Not drawn input combinations end in a rejecting state. While this is no proof I think it intuitively shows that CAs and NCAs are equivalent.

Nondeterministic CAs seem not studied very much in comparison to CAs, and don't seem to be cited on wikipedia. But they have been touched on, there is a natural way to define them. Analogously to all other automata or machine models, nondeterminism is just multiple or nonunique "next states" in the state table. Here is an example of study of them. The proof of equivalence in computations proceeds as with other machine models. The nondeterminism just allows multiple deterministic computational paths so to speak. However, they have different computational complexity capabilities as described in this paper.

If we consider a multifunction instead of A , we obtain the definition of a nondeterministic cellular automaton (NCA). Generally speaking, evolutions of NCA are not uniquely determined by initial configurations. A behaviour of NCA may be described by a state transition network (look at ). It is a graph, each of whose nodes represents some configuration.

• I'm not sure why someone downvoted you, one reason might be your use of "computational complexity". It could have been misunderstood to mean "the one can compute more than the other". Thank you for the link. It still baffles me how so few researchers seem to care about NCAs, especially since Ozhigov mentions NCAs are simpler to programm and exhibit nice properties in regard to computational complexity (i.e. speed of computation) . I haven't read it through so I am not sure how valid his argument is (and even if, I'm out of my depth there :) ). – rtur Jun 7 '15 at 10:20
• historically CAs went through a burst of research interest/ excitement but now that they are seen to be Turing equivalent maybe some of the novelty has worn off. while providing a unique angle unf the model does not seem to nec make study of computation any easier. – vzn Jun 7 '15 at 15:32