8
$\begingroup$

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 -> "*"]
Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

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

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$
    – tchronis
    Commented Jun 11, 2013 at 18:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Silvia
    Commented Jun 11, 2013 at 18:55
  • $\begingroup$ @tchronic -- the OP stated that his function was binary-valued, so there are only a countable number. $\endgroup$
    – bill s
    Commented Jun 11, 2013 at 19:26
  • $\begingroup$ bill... tchronis is the OP. :) $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jun 12, 2013 at 4:19
  • $\begingroup$ 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! $\endgroup$
    – bill s
    Commented Jun 12, 2013 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.