Software [system] statistics Empirical analysis of the million or so lines of source code that make up Mathematica suggests that different functions—which are roughly analogous to different genes—rather accurately follow an exponential distribution of sizes, with a slightly elevated tail.

With material where parts can locally expand, but cannot change their shape, page 1007 showed that a 2D surface will remain flat if the growth rate is a harmonic function. The Riemann mapping theorem of complex analysis then implies that even in this case, any smooth initial shape can grow into any other such shape with a suitable growth rate function.

Other examples [of minimal systems] Minimal systems achieving particular purposes are shown on page 619 for Boolean functions evaluated with Nand s, pages 759 and 889 for Turing machines, page 1142 for sorting networks, and page 1035 for firing squad synchronization.

Randomness in Mathematica SeedRandom[n] is the function that sets up the initial conditions for the cellular automaton.

In all cases no Turing machines with the same number of states compute the same functions in fewer steps.

Most of the programs involve only built-in Mathematica functions, and so can be run in Mathematica without setting up any further definitions. … When subsidiary functions are used, these functions also typically need to be defined before the programs are run—even though in these notes I often show the necessary definitions after the programs.

An initial condition consisting of n white cells with one black cell in the middle can then be obtained with the function (see below for comments on this and other Mathematica functions) CenterList[n_Integer] := ReplacePart[Table[0, {n}], 1, Ceiling[n/2]] For cellular automata of the kind discussed in this chapter, the rule can also be represented by a list. … In general, the list for a particular rule can be obtained with the function ElementaryRule[num_Integer] := IntegerDigits[num, 2, 8] Given a rule together with a list representing the state a of a cellular automaton at a particular step, the following simple function gives the state at the next step: CAStep[rule_List, a_List] := rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛 A list of states corresponding to evolution for t steps can then be obtained with CAEvolveList[rule_, init_List, t_Integer] := NestList[CAStep[rule, #]&, init, t] Graphics of this evolution can be generated using CAGraphics[history_List] := Graphics[ Raster[1 - Reverse[history]], AspectRatio  Automatic] And having set up the definitions above, the Mathematica input Show[CAGraphics[CAEvolveList[ ElementaryRule[30], CenterList[103], 50]]] will generate the image: The description just given should be adequate for most cellular automaton simulations. … It is also possible to have CAStep call the following external C language program via MathLink —though typically with successive versions of Mathematica the speed advantage obtained will be progressively less significant: #include "mathlink.h" main(argc, argv) int argc; char *argv[]; { MLMain(argc, argv); } void casteps(revrule, rlen, a, n, steps) int *revrule, rlen, *a, n, steps; { int i, *ap, t, tp; for (i = 0; i < steps; i++) { a[0] = a[n-2]; /* right boundary */ a[n-1] = a[1]; /* left boundary */ t = a[0]; for (ap = a+1; ap <= a+n-2; ap++) { tp = ap[0]; ap[0] = revrule[ap[1]+2*(tp + 2*t)]; t = tp; } } MLPutIntegerList(stdlink, a, n); } The linkage of this external program to the Mathematica function CAStep is achieved with the following MathLink template (note the optional third argument which allows CAStep to perform several steps of cellular automaton evolution at a time): :Begin: :Function: casteps :Pattern: CAStep[rule_List, a_List, steps_Integer:1] :Arguments: {Reverse[rule], a, steps} :ArgumentTypes: {IntegerList, IntegerList, Integer} :ReturnType: Manual :End: There are a couple of tricky issues in the C program above.

[Rules implementing] other functions The first three pictures below show rules that yield 3n (no k = 3 rules yield 4n , 5n or n 2 ), and the last picture 2n - 2 (corresponding to doubling with initial conditions analogous to page 639 ).

Determinism in brains Early investigations of internal functioning in the brain tended to suggest considerable randomness—say in the sequence of electrical pulses from a nerve cell.

Undecidability and sets Functions that can be computed in finite time by systems like Turing machines are often called recursive (or effectively computable). Sets are called recursive if there is a recursive function that can test whether or not any given element is in them. Sets are called recursively enumerable if there is a recursive function that can eventually generate any element in them.