patternMinor
How Cellular Automata is related to Automata Theory?
Viewed 0 times
theorycellularautomatarelatedhow
Problem
I have read about Automata Theory where it is about the study of abstract machines and automata.
And i know that an abstract machine takes the input, process it and create the output, just like Conway's Game of life.
But, what a formal defination can relate it to Cellular Automata, what about Elementary Cellular Automata, can it related also?
And i know that an abstract machine takes the input, process it and create the output, just like Conway's Game of life.
But, what a formal defination can relate it to Cellular Automata, what about Elementary Cellular Automata, can it related also?
Solution
There's no particular relationship. "Automaton" just means "machine" and it's unfortunate that we use the term "automata theory" to describe the study of one particular kind of automaton, rather than using a more specific name. (You can imagine a parallel universe in whcih automotive engineering is called "machine theory" and other mechanical engineers are standing around saying, "We build machines, too!")
Having said that, I assume there's some relationship between cellular automata and automata-theory automata. It's well-known that some automata are Turing complete, in the sense that you can code up a Turing machine as an input to the automaton, set it running and decode what the cellular automaton does as being the operation of the Turing machine. It would not be surprising (to me, as a non-expert in cellular automata) if there are cellular automata that have the same expressive power as regular expressions, i.e., if there are cellular automata that can simulate automata-theory automata but not simulate anything more powerful.
Having said that, I assume there's some relationship between cellular automata and automata-theory automata. It's well-known that some automata are Turing complete, in the sense that you can code up a Turing machine as an input to the automaton, set it running and decode what the cellular automaton does as being the operation of the Turing machine. It would not be surprising (to me, as a non-expert in cellular automata) if there are cellular automata that have the same expressive power as regular expressions, i.e., if there are cellular automata that can simulate automata-theory automata but not simulate anything more powerful.
Context
StackExchange Computer Science Q#47969, answer score: 6
Revisions (0)
No revisions yet.