foundations of mathematics Recursive definitions

Peano had observed that addition of natural numbers can be defined recursively thus:x + 0 = x, x + Sy = S(x + y). Other numerical functions null^k → null that can be defined with the help of such a recursion scheme (and with the help of 0, S, and substitution) are called primitive recursive. Gödel used this concept to make precise what he meant by “effectively enumerable.” A set of natural numbers is said to be recursively enumerable if it consists of all f(n) with n ∊ null, where f ∶ null → null is a primitive recursive function.

This notion can easily be extended to subsets of null^k and, by a simple trick called arithmetization, to sets of strings of words in a language. Thus Gödel was able to assert that the set of theorems of mathematics is recursively enumerable, and, more recently, the American linguist Noam Chomsky (b. 1928) could say that the set of grammatical sentences of a natural language, such as English, is recursively enumerable.

It is not difficult to show that all primitive recursive functions can be calculated. For example, to calculate x + y when x = 3 and y = 2, making use of Peano’s recursive definition of x + y and of the definitions 1 = S0, 2 = S1, and so on, one proceeds as follows:

3 + 2 = S2 + S1 = S(S2 + 1) = S(S2 + S0)

= SS(S2 + 0) = SSS2 = SS3 = S4 = 5.

But primitive recursive functions are not the only numerical functions that can be calculated. More general are the recursive functions, where f ∶ null → null is said to be recursive if its graph is recursively enumerable—that is, if there exist primitive recursive functions u, v ∶ null → null such that, for all natural numbers x and y, y = f(x) if and only if, for some z ∊ null, x = u(z) and y = v(z).

All recursive functions can be calculated with pencil and paper or, even more primitively, by moving pebbles (calculi in Latin) from one location to another, using some finite set of instructions, nowadays called a program. Conversely, only recursive functions can be so calculated, or computed by a theoretical machine introduced by the English mathematician Alan Turing (1912–54), or by a modern computer, for that matter. The Church-Turing thesis asserts that the informal notion of calculability is completely captured by the formal notion of recursive functions and hence, in theory, replicable by a machine.

Gödel’s incompleteness theorem had proved that any useful formal mathematical system will contain undecidable propositions—propositions which can be neither proved nor disproved. Church and Turing, while seeking an algorithmic (mechanical) test for deciding theoremhood and thus potentially deleting nontheorems, proved independently, in 1936, that such an algorithmic method was impossible for the first-order predicate logic (see logic, history of: 20th-century logic). The Church-Turing theorem of undecidability, combined with the related result of the Polish-born American mathematician Alfred Tarski (1902–83) on undecidability of truth, eliminated the possibility of a purely mechanical device replacing mathematicians.