# Is it possible to find a CellularAutomaton behind a sequence of 2D Tables

Maybe this is a hard question, maybe not. Whoever knows the answer can help me a lot starting working on CA theory.

Let's suppose I have a sequence

a[n_] := Table[f[i, j], {i, -n, n}, {j, -n, n}]


for some known function $f$. And let's make it simple: $f$ takes only the values $0$ and $1$.

Is there a way to find a cellular automaton that will create the same table--that is, to generalize the approach demonstrated by Michael E2 in his answer to the question about how to generate a certain type of nested array?

For reference, the code he presented was the following:

Grid[CellularAutomaton[{
670410854876259114171370389518449844628889143930760386943729872789478228151265\
8462491554691453382697921609151728673186802143641955019044568101339107753983,
2, {1, 1}}, {{{0}}, 1}, {{{9}}}] /. 1 -> "*"]


According to this Wikipedia entry (also A New Kind of Science), the number system used by CellularAutomaton is called Wolfram Code.

Inspired by the 1D system, this is how I think the 2D system works.

First we generate all 2D 9-neighbor cases:

baseSet = Tuples[{1, 0}, {3, 3}];


Then we apply the transformation rules on the baseSet one-by-one, and combine the result list into a single integer:

FromDigits[ruleFn[#, 1] & /@ baseSet, 2]


6704108548762591141713703895184498446288891439307603869437298727894782281512658462491554691453382697921609151728673186802143641955019044568101339107753983

• Yep, that's basically what I did, except I used Tuples[{1, 0}, {3, 3}]. +1 – Michael E2 Jun 12 '13 at 4:57
• @MichaelE2 Thanks. 2D Tuples is better :) – Silvia Jun 12 '13 at 5:03

The answer is "yes," any function you can represent in a computer can also be represented by a cellular automata. This is because some CAs are "universal Turing machines," which means that anything that can be computed algorithmically can be computed by the CA. Perhaps the best known example is a CA called the game of life.

This is only an existence statement, however, it is not going to lead to a nice algorithm for finding a simple CA to represent any given function. Steven Wolfram (one of the main people behind Mathematica) was an early expert in CAs and has written extensively about the subject in "New Kind of Science," which you can read on line.

• Thanks Bill. I am not convinced though there is always a way. The reason is that as i understand, we can create a countable family of CA's correct ? But the set of possible functions f is uncountable. So for the example above there isn't any 1-1 correspondence. So maybe i have to restrict the valid functions... I would like to think more on that... – tchronis Jun 11 '13 at 18:21
• @tchronis I think "only" those Turning computable functions can be computed by a universal Turing machine thus a universal cellular automata. You may also be interested in the Church–Turing thesis. – Silvia Jun 11 '13 at 18:55
• @tchronic -- the OP stated that his function was binary-valued, so there are only a countable number. – bill s Jun 11 '13 at 19:26
• bill... tchronis is the OP. :) – J. M. is in limbo Jun 12 '13 at 4:19
• 0x4A4D -- from the post: "let's make it simple: f takes only the values 0 and 1." If he wants to change the question, the answer may be different! – bill s Jun 12 '13 at 4:59