HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are deterministic and nondeterministic Cellular Automata equivalent?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
equivalentarecellularautomatadeterministicnondeterministicand

Problem

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 ?

Solution

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.

Context

StackExchange Computer Science Q#43306, answer score: 4

Revisions (0)

No revisions yet.