1
$\begingroup$

In atlas.wolfram.com (see here http://atlas.wolfram.com/01/01/views/173/TableView.html, for example) we can get the algebraic form of any given elementary cellular automaton in 1D.

Is there a way to let Mathematica know the rule number and get as output the algebraic form of this rule (in 1D, 2D, or whatever other rule...)?

$\endgroup$
2
  • $\begingroup$ There's probably some built-in trick for this in Mathematica, but even writing a routine to do this from first principles shouldn't be that hard — the only non-trivial part would be converting boolean expressions from DNF (which you can read straight out of the rule table) into ANF. (Actually the expressions in your linked table don't really seem to be in ANF: they include e.g. $(1+p)(1+q)$ instead of the ANF $1+p+q+pq$. But ANF should be just as valid as what's listed in the table.) $\endgroup$ Dec 6, 2022 at 15:44
  • $\begingroup$ Hi @Ilmari, if I understand correctly, what you say is: read from the ruleplot the DNF and then convert it to ANF, right? If this is what you meant, imagine I want to create a table of 1000 cellular automata with the first column being their rule and the second their algebraic form...My problem still exists; how do I automate reading DNFs for arbitrary cellular automata? How do I give mathematica the rule and get the DNF? $\endgroup$
    – Kostas
    Dec 6, 2022 at 16:17

2 Answers 2

1
$\begingroup$

Just for the record, doing this is in fact really easy for the simple cases. It comes up often enough for me that I have a helper function:

anf[expr_] := BooleanConvert[expr, "ANF"] //. {And -> Times, Xor -> Plus, ! x_ :> x + 1}

Then for any CA consisting of a single rule number, you can use

anf[BooleanFunction[rule]]

e.g.

anf[BooleanFunction[30]] gives #2 #3 + #1 + #2 + #3 &,

or if you prefer, you could

anf[BooleanFunction[30]][a,b,c] to get a + b + c + b c.


For 1D cases with more neighbors, it's still an easy lift. All you need to do is add the number of inputs (so for the elementary 1-neighbor, that's $2\cdot 1+1=3$, for 2-neighbor, that's $2\cdot 2+1=5$) to BooleanFunction.

Illustrative example:

example screenshot

Here, I used the form CellularAutomaton[{ruleNum, numColors, numNeighbors}]. Since $2^{32}$ is the maximum with 2 colors and 2 neighbors (which again means 5 inputs), we have rule $2^{32}-2$ giving a system which is kind of an extended NAND, where it's true if one or more of the input cells is true, else false.

Comparing that to the lengthy ANF expression for it, you can see that it tracks since $2^5-1=31$ is the number of ways you can combine five things into subsets, omitting the empty set (which is our 00000 case), so it fits; basically, any of those five variables having any value would mean that expression gives true, and only if they're all false do you get false, just like we want.

$\endgroup$
3
  • $\begingroup$ Hi @Trev, your method is so much cleaner. Thanks a lot! Just a slight concern...For my method, if I want to find the rules for 1D 5-neighborhood CA (a, b, c, d, e) instead of the usual 3-neighborhood ones, I simply change tuples and lista. How would I adapt your code for this task? $\endgroup$
    – Kostas
    Dec 13, 2022 at 17:34
  • $\begingroup$ @KonstantinosSfairopoulos Added that case, hope it helps! $\endgroup$
    – Trev
    Dec 15, 2022 at 6:52
  • $\begingroup$ Hi @Trev! Thanks a lot! And indeed works for 2D CA as well and any other CA...that's so much better than my workaround:)... $\endgroup$
    – Kostas
    Dec 15, 2022 at 11:42
2
$\begingroup$

Thanks to @IlmariKaronen I realized that what I wanted was indeed really easy...

tuples = Tuples[{1, 0}, 3];
lista = {p, q, r};
values = Table[PadLeft[IntegerDigits[i, 2], 8], {i, 0, 255}];
processed = 
  Table[If[tuples[[i]][[j]] == 0, 1 - lista[[j]], lista[[j]]], {i, 1, 
    Dimensions[tuples][[1]]}, {j, 1, Dimensions[tuples[[i]]][[1]]}];
processedfull = 
  Table[Times @@ processed[[i]], {i, 1, Dimensions[processed][[1]]}];
allrules = 
 PolynomialMod[
  Expand[Table[
    values[[j]].processedfull, {j, 1, Dimensions[values][[1]]}]], 2]

This answers the question for 1D elementary CA, but can be easily adapted to any dimensional CA or neighborhood by adapting tuples and lista and the values-dimension from $2^{2^3}$ to any needs...

$\endgroup$

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.