Cycles and zeta functions The number of sequences of n cells that can occur repeatedly, corresponding to cycles in the network, is given in terms of the adjacency matrix m by Tr[MatrixPower[m,n]] . These numbers can also be obtained as the coefficients of x n in the series expansion of x ∂ x Log[ ζ [m, x]] , with the so-called zeta function, which is always a rational function of x , given by ζ [m_, x_] := 1/Det[IdentityMatrix[Length[m]] - m x] and corresponds to the product over all cycles of 1/(1 - x n ) .

One can think of each Turing machine as computing a function f[x] of the number x given as its input. … Most machines compute functions that involve digit manipulations without traditional interpretations as mathematical functions. … The number of distinct functions that can be computed is about 315,959 (or 457,508 for {f[x], t[x]} pairs).

With evolution functions f i and f j the requirement for the emulation to work is f j [a j ]  InverseFunction[ ϕ ][f i [ ϕ [a j ]]] In the main text the encoding function is taken to have the form Flatten[a /. rules] —where rules are say {1  {1, 1}, 0  {0, 0}} —with the result that the decoding function for emulations that work is Partition[ ã , b] /. … Various questions about encoding functions ϕ have been studied over the past several decades in coding theory. … In the most general case the encoding function can involve an arbitrary terminating computation (see page 1126 ).

Functions [computed by Turing machines] The plots below show the values of the functions f[x] for x from 0 to 1023 computed by the Turing machines on pages 761 and 763 .

Nand expressions If one allows a depth of at most 2n any n -input Boolean function can be obtained just by combining 2-input Nand functions. … The pictures below show the distributions of numbers of Nand operations needed for all 2 2 n n -input Boolean functions. … First, expressions containing progressively more Nand operations were enumerated, and those for functions that had not been seen before were kept.

It turns out that any rule for blocks of black and white cells can be represented as some combination of just a single type of operation—for example a so-called Nand function of the kind often used in digital electronics. And given this, one can imagine finding for any particular rule the formula that involves the smallest number of Nand functions.

Reversible logic In an ordinary Boolean function with n inputs there is no unique way to tell from its output which of the 2 n possible sets of inputs was given. But as noted in the 1970s, it is possible to set up systems that evaluate Boolean functions, yet operate reversibly. … Of the 24 possible reversible s = 2 gates, none can yield anything other than additive Boolean functions (as formed from Xor and Not ).

Each collection of such functions can be obtained from lists of vectors representing 1D Walsh functions by using Outer[Outer[Times, ##] &, b, b, 1, 1] , or equivalently Map[Transpose, Map[# b &, b, {2}]] . … The components of the vectors for 1D Walsh functions can be ordered in many ways. … Walsh functions can correspond to nested sequences.

[Universal] recursive functions The general recursive functions from page 907 provided an early example of universality (see page 907 ). That such functions are universal can be demonstrated by showing for example that they can emulate any tag system. … Any fixed number of steps of evolution can thus be emulated by applying a primitive recursive function.

With maps based on piecewise linear functions the regions of parameters in which chaotic behavior occurs typically have simple shapes; with maps based, say, on quadratic functions, however, elaborate nested shapes can occur.