patternMinor
Are deterministic and nondeterministic Cellular Automata equivalent?
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 ?
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.
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.