The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations: Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}] The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.

One general class of models based on the work of Alan Turing in 1936 follow the operation of standard digital computers, and involve looking at real numbers in terms of digits, and using discrete processes to generate these digits. … Functions are usually considered computable in such models if one can take the procedure for finding the digits of x and get a procedure for finding the digits of f[x] . And with this definition all standard mathematical functions are computable—even those from chaos theory that excavate digits rapidly.

But the problem is that there is no telling how difficult it may be to compute the actual value of a number from the symbolic expression that is used to represent it. And in thinking about representations of numbers, it seems appropriate to restrict oneself to cases where the effort required to find the value of a number from its representation is essentially the same for Procedures for building up π from its base 10 and base 2 digit sequence representations.

Chaos Theory and Randomness from Initial Conditions…The details of these trajectories cannot be deduced quite as directly as before from the digit sequences of initial positions, but Paths followed by four idealized balls dropped from initial positions differing by one part in a thousand into an array of identical circular pegs. … In a physical version of the system with balls of the same actual size as on this page perturbations from the environment will inevitably be amplified to have a significant effect on the trajectories after roughly the number of bounces shown.

There seems to be no easy way to tell, but the picture below shows all the structures that I found by explicitly looking at evolution from the first twenty-five billion possible initial conditions. … The largest structure in the picture below starts from a block that is 30 cells wide. … The base 2 digit sequences of the numbers given correspond to the initial conditions in each case, as on the previous page .

Implementation [of finite automata for nested patterns] Given the rules for a substitution system in the form used on page 931 a finite automaton (as on page 957 ) which yields the color of each cell from the digit sequences of its position is Map[Flatten[MapIndexed[#2 - 1  Position[rules, #1  _] 〚 1, 1 〛 &, Last[#], {-1}]] &, rules] This works in any number of dimensions so long as each replacement yields a block of the same cuboidal form.

And so, for example, while the digits of π have a simple description in terms of traditional mathematics, the results in Chapter 4 suggest that outside of this framework they normally do not. And what this means is that if one saw a system that had the property of generating the digits of π one would be unlikely to think that this could represent a meaningful purpose—unless one happened to be operating in traditional mathematics. And so similarly, one would be unlikely to think that generating the center column from rule 30 could represent any sort of meaningful purpose—unless one was operating within the framework that I have developed in this book.

One can count the number of occurrences of each of the k b possible blocks of length b in a given state using BC[list_] := With[{z = Map[FromDigits[#, k] &, Partition[list, b, 1, 1]]}, Map[Count[z, #] &, Range[0, k b - 1]]] Conserved quantities of the kind discussed here are then of the form q .

Given only an output list NestList[Mod[a #, m]&, x, n] parameters {a, m} that generate the list can be found for sufficiently large n from With[{ α = Apply[(#2 . Rest[list]/#1) &, Apply[ ExtendedGCD, Drop[list, -1]]]}, {Mod[ α , #], #} &[ Fold[GCD[#1, If[#1  0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{ α , -1}, list]]]] With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]] .

Implementation of general cellular automata With k colors and r neighbors on each side, a single step in the evolution of a general cellular automaton is given by CAStep[CARule[rule_List, k_, r_], a_List] := rule 〚 -1 - ListConvolve[k^Range[0, 2r], a, r + 1] 〛 where rule is obtained from a rule number num by IntegerDigits[num, k, k 2r + 1 ] .