recursive automata, or recursion mod 2.

70 Views Asked by At

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ then $l_{n+1}$ is the list $(a_1+a_2,a_2+a_3, \dots ,a_{n-1}+a_n,a_n+a_1)$ where all of the operations are done in $\mathbb Z_2$. In other words all the numbers in the lists are 1 or 0 and we use the rules $1+0=0+1=1$ and $1+1=0+0=0$.

The question is whether we can calculate what $l_n$ is for arbitrary values of $m$ and $n$.

Thank you very much in advance.

Regards.

1

There are 1 best solutions below

1
On BEST ANSWER

Your problem can be phrased in terms of the addition mod 2 cellular automaton (CA) as follows:

The alphabet is $\mathbb{Z}_2=\{0,1\}$ the integers mod 2, the transformation you apply to the list is the elementary cellular automaton RULE 102 whose rule sums the symbol and its right neighbour. Your list is the finite set of cells on which you apply the CA. As you are doing this cyclically, i.e. summing $a_i$ and $a_{i+1}$ for $1\leq i<m$ and at the very end summing $a_m$ and $a_1$, this corresponds to $m$-periodic boundary configurations, i.e. you start the CA with a periodic configuration of the form $c:=\ldots 0^{m-1}\,1\,0^{m-1}\,1\,0^{m-1}\,1\,0^{m-1}\ldots$ The list $l_n$ is then the $n$th row of the space-time diagram of this CA started with $c$.

Now what you are asking is exactly what the $n$th line of this space-time diagram looks like.

See: http://mathworld.wolfram.com/Rule102.html for some background.