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 ?
Asked By : rtur
Answered By : babou
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43306
0 comments:
Post a Comment
Let us know your responses and feedback