1
$\begingroup$

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language?

In probabilistic cellular automata, are the cells considered nondeterministic finite automata, Is there a language associated with this as well, and is it too considered a regular language?

$\endgroup$
2
  • 1
    $\begingroup$ To start with, on which alphabet would you like to work? $\endgroup$
    – J.-E. Pin
    Aug 28, 2013 at 6:34
  • $\begingroup$ I'm unsure which languages and their alphabets are appropriate. From what I recall, it definitely wouldn't be a context-free language. Do you have a recommendation for a language and an alphabet to represent Conway's Game of Life or any other cellular automata? $\endgroup$
    – user91967
    Aug 28, 2013 at 10:34

2 Answers 2

2
$\begingroup$

Too long for a comment.

If you wish to express a single cell to be expressed as finite automaton (and provide the connection between them in some other way), then with some particular choice of input it is possible to encode as a regular language. For example, each step the automaton could be feed 8 symbols $0$ or $1$ that represent the state of its neighbors (and knowing if it had accepted or no the previous turn, it could accept or not at current step).

On the other hand, if it were to work "by itself", then no, Conway's Game of Life is Turing-complete, and as such impossible to express as a finite state automaton. The space for Conway's Game is infinite, so it still might be possible to express it with some infinite state automaton, whatever that is.

I hope this helps $\ddot\smile$

$\endgroup$
1
  • $\begingroup$ In a 2D Game of Life grid, each cell is dependent upon its neighbors, each new generation should cause the cell to be fed the state of its four neighbors. This sounds like a finite state automata. Are you aware of a language which can be used to represent these states? Would you have to create one, and how would you formalize this language? I'm completely new and have so many questions! :) Thanks for your answer $\endgroup$
    – user91967
    Aug 28, 2013 at 10:44
0
$\begingroup$

In dimension 1, any cellular automaton can be seen as a finite state transducer. Therefore, for instance, the language of all finite words than can appear in some configuration after 1 step of the evolution of the CA is always a rational language. Same result for n steps.

In dimension 2, you can somehow still view the CA as a finite state transducer in order to prove that the set of words that can appear in a horizontal line is also a regular language.

With probabilistic automata, the basic idea is to add weights to the finite state transducers considered above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .