Factoring integers The difficulty of factoring is presumably related to the irregularity of the pattern of divisors shown on page 909 . … Typical running times for FactorInteger[n] in Mathematica 4 are shown below for the first 1000 numbers with each of 15 through 30 digits.

Implementation [of operators from axioms] Given an axiom system in the form {f[a, f[a, a]]  a, f[a, b]  f[b, a]} one can find rule numbers for the operators f[x, y] with k values for each variable that are consistent with the axiom system by using Module[{c, v}, c = Apply[Function, {v = Union[Level[axioms, {-1}]], Apply[And, axioms]}]; Select[Range[0, k k 2 - 1], With[{u = IntegerDigits[#, k, k 2 ]}, Block[{f}, f[x_, y_] := u 〚 -1 - k x - y 〛 ; Array[c, Table[k, {Length[v]}], 0, And]]] &]] For k = 4 this involves checking nearly 16 4 or 4 billion cases, though many of these can often be avoided, for example by using analogs of the so-called Davis–Putnam rules.

Cellular automaton combinators With k and s[k] representing respectively cell values 0 and 1 , a combinator f for which f[a -1 ][a 0 ][a 1 ] gives the new value of a single cell in an elementary cellular automaton with rule number m can be constructed as Apply[p[p[p[#1][#2]][p[#3][#4]]][p[p[#5][#6]][p[#7][ #8]]] /. {0  k, 1  s[k]} &, IntegerDigits[m, 2, 8]] //. crules where p = ToC[z[y][x], {x, y, z}] //. crules The resulting combinator has size 61, but for specific rules somewhat smaller combinators can be found—an example for rule 90 is s[k[k]][s[s][k[s[s[s[k][k]][k[s[k]]]][k[k]]]]] with size 16. To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules where num[n_] := Nest[inc, s[k], n] inc = s[s[k[s]][k]] One can recover the original list by using Extract[expr, Map[Reverse[IntegerDigits[#, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/.

Systems based on continuous numbers involve infinite sequences of digits which can readily be chosen at random (see page 154 ). But systems based on integers (including register machines) always deal with finite sequences of digits, for which there is no unique definition of randomness.

Powers of three in base 2 The n th row in the pattern shown can be obtained simply as IntegerDigits[3 n , 2] . … The sequence Mod[3 n , 2 s ] obtained from the rightmost s digits corresponds to a simple linear congruential pseudorandom number generator.

(c) is like (b), except that it has a specification of the number of digits at the front. … (e) uses a non-integer base derived from the Fibonacci sequence, with the property that a pair of black cells can appear only at the end of each number.

The number of steps before a machine with given rule halts can be computed from (see page 888 ) Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]] Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt. … Most machines compute functions that involve digit manipulations without traditional interpretations as mathematical functions. … Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.

And in general, the probabilities for all 8 possible combinations of 3 cells are given by probs = Apply[Times, Table[IntegerDigits[8 - i, 2, 3], {i, 8}] /. {1  p, 0  1 - p}, {1}] In terms of these probabilities the density at the next step in the evolution of cellular automaton with rule number m is then given by Simplify[probs . IntegerDigits[m, 2, 8]] For rule 22, for example, this means that if the density at a particular step is p , then the density on the next step should be 3 p (1 - p) 2 , and the densities on subsequent steps should be obtained by iterating this function.

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. In some earlier versions of Mathematica a considerably faster version of the program can be created by using the definition CAStep = Compile[{{rule, _Integer, 1}, {a, _Integer, 1}}, rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛 ] In addition, in Mathematica 4 and above, one can use CAStep[rule_, a_]:=rule 〚 8 - ListConvolve[{1, 2, 4}, a, 2]]] 〛 or directly in terms of the rule number num Sign[BitAnd[2^ListConvolve[{1, 2, 4}, a, 2], num]] (In versions of Mathematica subsequent to the release of this book the built-in CellularAutomaton function can be used, as discussed on page 867 .) 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.

Defining PM[s_] := IntegerDigits[Range[2 s - 1], 2, s] blocks of data of length m can be encoded with Join[data, Mod[data . Select[PM[s], Count[#, 1] > 1 &], 2]] while blocks of length n (and at most one error) can be decoded with Drop[(If[#  0, data, MapAt[1 - # &, data, #]] &)[ FromDigits[Mod[data .