Undecidability in Mathematica In choosing functions to build into Mathematica I tried to avoid ones that would often encounter undecidability. And this is why for example there is no built-in function in Mathematica that tries to predict whether a given program will terminate. But inevitably functions like FixedPoint , ReplaceRepeated and FullSimplify can run into undecidability—so that ultimately they have to be limited by constructs such as $IterationLimit and TimeConstraint .

Like ordinary algebraic functions, Boolean functions can also be represented by a variety of kinds of formulas. … In general any given function will allow many DNF representations; minimal ones can be found as described below. Writing a Boolean function in DNF is the rough analog of applying Expand to a polynomial.

(Other appropriate primitives may conceivably be related to the solubility of Hilbert's Thirteenth Problem and the fact that any continuous function with any number of arguments can be written as a one-argument function of a sum of a handful of fixed one-argument functions applied to the arguments of the original function.) … If one has a table of choices, one can imagine generalizing this to a function of a real number. But to specify this function one normally has no choice but to use some type of finite formula.

[Patterns from] other integer functions The pictures above show patterns produced by reducing several integer functions modulo 2. … Note that GCD[m, n] yields a more complicated pattern (see page 613 ), as do JacobiSymbol[m, 2n - 1] (see page 1081 ) and various combinations of functions (see page 747 ).

[Patterns from] bitwise functions Bitwise functions typically yield nested patterns. (As discussed above, any cellular automaton rule can be represented as an appropriate combination of bitwise functions.) … Nesting is also seen in curves obtained by applying bitwise functions to n and 2n for successive n .

For rational functions f[x] , Integrate[f[x], {x, 0, 1}] must always be a linear function of Log and ArcTan applied to algebraic numbers ( f[x] = 1/(1 + x 2 ) for example yields π /4 ). Multiple integrals of rational functions can be more complicated, as in Integrate[1/(1 + x 2 + y 2 ), {x, 0, 1}, {y, 0, 1}]  HypergeometricPFQ[{1/2, 1, 1}, {3/2, 3/2}, 1/9]/6 + 1/2 π ArcSinh[1] - Catalan and presumably often cannot be expressed at all in terms of standard mathematical functions. … If f[n] is a rational function, Sum[f[n], {n, ∞ }] must just be a linear combination of PolyGamma functions, but again the multivariate case can be much more complicated.

Symbolic expressions Expressions like Log[x] and f[x] that give values of functions are familiar from mathematics and from typical computer languages. Expressions like f[g[x]] giving compositions of functions are also familiar. … But although this can be convenient when f is a discrete function such as a matrix, it is inconsistent with general mathematical and other usage in which for example Gamma[x] and Gamma[a, x] are both treated as values of functions.)

Logical functions of two arguments and their common names. … The first argument for each function appears on the left in the picture; the second argument on top. The functions are numbered like 2-neighbor analogs of the cellular automaton rules of page 53 .

Generating functions [for nested patterns] A convenient algebraic way to describe a sequence of numbers a[n] is to give a generating function Sum[a[n] x n , {n, 0, ∞ }] . 1/(1 - x) thus corresponds to the constant sequence and 1/(1 - x - x 2 ) to the Fibonacci sequence (see page 890 ). … Any rational function is the generating function for some additive cellular automaton.

Built-in cellular automaton function Versions of Mathematica subsequent to the release of this book will include a very general function for cellular automaton evolution.