2
$\begingroup$

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.

  • 0
    Computability theory, it would seem to me, as this is very close to the idea of a [Turing machine](http://en.wikipedia.org/wiki/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.2012-01-17
  • 0
    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.2012-01-17
  • 1
    Yes; you could look into [symbolic dynamics](http://en.wikipedia.org/wiki/Symbolic_dynamics) and shift spaces, and the Curtis–Hedlund–Lyndon theorem, which characterizes cellular automata as a particular kind of morphism between shift spaces.2012-01-17
  • 0
    mjqxxxx: that is exactly the answer for my question. Thanks!2012-01-18

0 Answers 0