By allowing larger depths one can potentially find smaller formulas for functions. … If one chooses an n -variable Boolean function at random out of the 2 2 n possibilities, it is typical that regardless of depth a formula involving at least 2 n /n operations will be needed to represent it. A formula of polynomial size and logarithmic depth exists only when a function is the computational complexity class NC discussed on page 1149 .

And if one assumes that this is a general feature then one can formally derive for any a the result 1/2 (1 - g[a t InverseFunction[g] [1 - 2x]]) where g is a function that satisfies the functional equation g[a x]  1 + (a/2) (g[x] 2 - 1) When a = 4 , g[x] is Cosh[Sqrt[2 x]] . … But in general for arbitrary a there is no standard mathematical function that seems to satisfy the functional equation. … In addition, from a known replication formula for an elliptic or other function one can often construct an iterated map whose behavior can be expressed in terms of that function.

Nesting in bitwise functions See page 871 .

It turns out that there are 351 different functions that can be computed by one or more of the 4096 Turing machines with 2 states Examples of the behavior of a simple Turing machine that does the computation of adding 1 to a number. … The plot shows the number of steps that this takes as a function of the input number x .

Turing machines (b), (c) and (d) are ones that always compute the same function. … And it turns out that at least among 2-state 2-color Turing machines this is the only one that computes the function it computes—so that at least if one wants to use a program this simple there is no faster way to do the computation.

[Computational complexity of] finding outcomes If one sets up a function to compute the outcome after t steps of evolution from some fixed initial condition—say a single black cell in a cellular automaton—then the input to this function need contain only Log[2, t] digits.

The energy associated with each spin is then given by some function which depends on the configuration of neighboring spins. … But in generalizations of the Ising model with more complicated energy functions, the conditions to get a state of the lowest possible energy can correspond exactly to the constraints discussed in the main text. … Note that a rather different way to get a somewhat similar ground state is to consider a spin glass, in which the standard Ising model energy function is used, but multiplied by -1 or +1 at random for each spin.

With the development of lambda calculus in the early 1930s it became clear that given any expression expr such as x[y[x][z]] with a list of variables vars such as {x, y, z} one can always find a combinator equivalent to a lambda function such as Function[x, Function[y, Function[z, x[y[x][z]]]]] , and it turns out that this can be done simply using ToC[expr_, vars_] := Fold[rm, expr, Reverse[vars]] rm[v_, v_] = id rm[f_[v_], v_] /; FreeQ[f, v] = f rm[h_, v_] /; FreeQ[h, v] = k[h] rm[f_[g_], v_] := s[rm[f, v]][rm[g, v]] So this shows that any lambda function can in effect be written in terms of combinators, without anything analogous to variables ever explicitly having to be introduced. And based on the result that lambda functions can represent recursive functions, which can in turn represent Turing machines (see note above ), it has been known since the mid-1930s that combinators are universal. … With n represented by Nest[k, s[k][k], n] , however, s[s[s[s]][k]][k] serves as a decrement function, and with n represented by Nest[s[s],s[k], n] , s[s[s][k]][k[k[s[s]]]] serves as a doubling function.

For the generalization of rule 90, the values of the left and right cells are added together, and the value of the cell on the next step is then found by applying the continuous generalization of the modulo 2 function shown at the right.

The argument is based on showing that an algebraic function always exists for which the coefficients in its power series correspond to any given nested sequence when reduced modulo some p . … But then there is a general result that if a particular sequence of power series coefficients can be obtained from an algebraic (but not rational) function modulo a particular p , then it can only be obtained from transcendental functions modulo any other p —or over the integers.