But as we shall see, even these models appear quite sufficient to capture the behavior of a remarkably wide range of systems from nature and elsewhere—establishing beyond any doubt, I believe, the practical value of thinking in terms of simple programs.

And thus, for example, essentially as a consequence of randomness generation, a wide range of cellular automata show the simple density diffusion law on page 464 —whether or not their underlying rules happen to be simple.

fundamentally larger range if one allowed, say, four or five connections rather than just three.

And indeed the bottom pictures show a succession of networks that in effect have curvatures with a range of negative and positive values.

One might imagine perhaps that while there could in principle be methods of perception that would recognize features beyond, say, repetition and nesting, any single such feature might never occur in a sufficiently wide range of systems to make its recognition generally useful to a biological organism.

One might have assumed that among different processes there would be a vast range of different levels of computational sophistication.

And what this suggests is that a fundamental unity exists across a vast range of processes in nature and elsewhere: despite all their detailed differences every process can be viewed as corresponding to a computation that is ultimately equivalent in its sophistication.

But this book shows that there are actually a vast range of abstract systems based on simple programs that traditional mathematics has never considered.

And with it my hope is to share what I have done with as wide a range of scientists and non-scientists as possible.

A crucial feature of primitive recursive functions is that the number of steps they take to evaluate is always limited, and can always in effect be determined in advance, since the basic operation of primitive recursion can be unwound simply as f[x_, y___] := Fold[h[#1, #2, y] &, g[y], Range[0, x - 1]] And what this means is that any computation that for example fundamentally involves a search that might not terminate cannot be implemented by a primitive recursive function. … In enumerating recursive functions it is convenient to use symbolic definitions for composition and primitive recursion c[g_, h___] = Apply[g, Through[{h}[##]]] & r[g_, h_] = If[#1  0, g[##2], h[#0[#1 - 1, ##2], #1 - 1, ##2]] & where the more efficient unwound form is r[g_,h_] = Fold[Function[{u, v}, h[u, v, ##2]], g[##2], Range[0, #1 - 1]] & And in terms of these, for example, plus = r[p[1], s] . … From its definition, the function can be written as Fold[Fold[2^Ceiling[Log[2, Ceiling[(#1 + 2)/(#2 + 2)]]] (#2 + 2) - 2 - #1 &, #2, Range[#1]] &, 0, Range[#]]& Its first zeros are at {4, 126, 813, 966, 1166, 1177, 1666, 1897} .