4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ No relation other than the name and the finite number of states. $\endgroup$
    – Yuval Filmus
    Oct 7, 2015 at 5:31
  • 1
    $\begingroup$ @YuvalFilmus that's actually not entirely true. I.e. cellular automata may have infinite number of states. I.e. instead of discrete values they may produce continuous output and have some real-valued function as their transition function. $\endgroup$
    – wvxvw
    Oct 7, 2015 at 7:54
  • 1
    $\begingroup$ Actually, automata theory also makes use of automata with an infinite number of states. Here is an example: a subset of $A^\omega$ is closed iff it is accepted by a deterministic (possibly infinite) Bûchi automaton in which all states are final. $\endgroup$
    – J.-E. Pin
    Oct 8, 2015 at 8:26

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

You can actually see cellular automata as various ways to generalize the automata studied by automata theory. While automata studied in automata theory typically have only one reading (and possibly writing) head, have access to a single cell of memory storage at a time (per storage), cellular automata may use multiple reading/writing heads and read multiple cells of the memory storage per operation. Also, unlike other automata, cellular automata may output more than one symbol per operation.

But traditional texbooks on automata theory don't treat cellular automata as a member of the automata family. Cellular automata didn't see much practical use and, maybe because of that, it doesn't have a kind of established hierarchy and a host of theorems covering each aspect as does the automata of automata theory.

There's also a "personal" aspect of this relation. Stephen Wolfram, the person who invested a lot of effort into popularizing the subject has done so with a lot of controversy. He might have been overly "enthusiastic" about his research, while the rest of scientific community responded with patronizing and diminishing commentary (something you might be familiar with from visiting popular social Q&A sites). And so much so that today, for "serious" figures in the said scientific community embracing cellular automata into the family of automata would be too embarrassing (and nobody likes that, yikes!)

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.