Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's consider one dimensional cellular automaton. It is build upon its rule, i.e. a function $f : S^3 \rightarrow S$, where $S = \{0,1\}$. The case described is the elementary cellular automaton, because the rule-function has 3 bits wide input.

The automaton transforms its infinite rows using the rule. Let's limit the rows to pseudo-infinite ones, i.e. left end of row is connected to right end, and the row length is $N$, a finite number.

The question: each row has its unique successor – the result of multiple productions of $f$. This defines a new function. Let's denote it as $F$. The function takes whole row as input, and outputs whole new row. Are such functions $F$ – i.e. based on basic functions like $f$ – investigated in some mathematics topic? I am interested in properties of such functions.

share|cite|improve this question
Computability theory, it would seem to me, as this is very close to the idea of a Turing machine and can in fact be simulated with one, although I'm not sure about the other way around. After I finish my computability theory homework I might get to it. – Alex Becker Jan 17 '12 at 20:04
This function doesnt look very interesting. It has a finite domain and range, {1,2,3,...,2^N}. And will eventually enter a cycle of period at most 2^N. – TROLLKILLER Jan 17 '12 at 20:46
Yes; you could look into symbolic dynamics and shift spaces, and the Curtis–Hedlund–Lyndon theorem, which characterizes cellular automata as a particular kind of morphism between shift spaces. – mjqxxxx Jan 17 '12 at 21:47
mjqxxxx: that is exactly the answer for my question. Thanks! – Mooncer Jan 18 '12 at 2:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.