THE THEORY OF RECURSIVE FUNCTIONS

http://wormholetravel.net/math.html

We now turn to a development which at first sight appears to have nothing to Jo with formal systems. In fact, imagine that you have tired of the complexities "The metatheory and for diversion have turned to another book. The author of this different is familiar with the paradoxes of the infinite and the complexities  induced into math logic in order to get rid of them. However, he feels that both the paradoxes and complexities are unnecessary and that they are caused by the use of quantifiers which range over infinite domains. Such an author was  Thoralf Skolem, who after studying Principia Mathematica, wrote a paper with in alternative answer to the problems of the infinite. The paper — written in 1919 and  published in 1923 — is called The Foundations of Elementary Arithmetic Established by Means of the Recursive Mode of Thought, Without Use of Apparent Variables Ranging over Infinite Domains. The paper marked the beginning of the development of an area of maths whose importance is comparable to geometry or algebra. It is today called the theory of recursive functions. To understand the title of Skolem's paper, some background is needed. What Skolem calls the recursive mode of thought is exemplified in the use of math induction, which goes back at least as far as Pierre de Fermat (1601-1665) and Blaise Pascal (1623-1662), but it wasn't until the nineteenth century that the principle itself was studied, in particular by Frege, Dedekind, and Peano. All of them studied it with a view toward understanding the nature of number. Skolem's motivation was different; he thought he could use it as part of the foundation for arithmetic. This foundation was intended to be so certain and the inferences from it so indubitable, that not only wouldn't the paradoxes arise, but we would also be completely convinced that they could not arise. His motivation then was somewhat similar to Euclid's, that is, he wanted to start from statements indubitably true and proceed in such a way that doubts could never set in. His success has been such that not only has everyone accepted his work (even mathematicians and philosophers who have doubts about some parts of classical maths), but also his theory has become a paradigm of indubitable reasoning.

Skolem proceeds informally; in fact, he does not even use the axiomatic method. He assumes that the following notions are already understood; natural number, successors of x, substitution of equals for equals, and the recursive mode of thought. From these he attempts to define all arithmetic notions. By natural number Skolem means 1,2,3..., that is, the numbers used in counting. By successor of x he meant "the number coming after x, denoted by x". The substitution of equals for equals is an obvious rule, since here two expressions flanking an "equals" sign means that they denote the same object; in other words, we have transitivity. The expression recursive mode of thought refers to two things: first, all definitions are definitions by recursion and second, all proofs are by math induction.

We may begin to appreciate the philosophical importance of recursive func­tion theory if we compare the usual definition of divisibility with the one recursive arithmetic. The usual one is 

. As Skolem points out, "Such a definition involves an infinite task — that means one that cannot be completed — since the criterion of divisibility involves successive trials through the entire number sequence". To see this, consider a specific example, say, dividing 8 by 3.

We then have  which becomes   (8=3*8) V(8=3) V (8=3-2)

V(8=3*3) V(8=3*4) v(8=3*n) V... For each of the infinite number of disjuncts we would have to compute the multiplication and see whether the equality holds. Of course, after a certain point it becomes pointless to continue the computation, for we can be sure that the computation would not reveal an equality. At what point in general? It is clear that the number of disjuncts will never have to be more than one greater than the dividend. This is what is embodied in the recursive divination of divisibility:

The use here of the bound (apparent) variable is completely inessential, since it can be eliminated for any specific pair of numbers. In the theory of recursive functions, only free variables are used. The meaning of formulas with free variables is understood to be the same as that of the universal closure of the formulas. For example, x+y=y+x is equivalent in meaning to

We may summarize the situation by saying that while the usual definition f a function it explicitly by giving an abbreviation of that expression, the recursive definition defines the function explicitly only for the first natural number and then provides a rule whereby it can be defined for the second natural number, and then the third, and so on.

The philosophical importance of a recursive function derives from its relation to what we mean by an effective finite procedure, and, hence, to what we mean by  algorithm or dicision procedure. Algorithms had been used for thousands of  years (Euclid gives one for finding the greatest common divisor), but it wasn't until the twentieth century that an attempt was made to explicate exactly what an algorithm in general. Skolem's paper marked the first development of an area of maths which was to provide an adequate analysis of the concept of an effective finite procedure. Skolem's initial motivation, however, was not directly concerned with this; rather his interest was to avoid the paradoxes without epistemological complexity. This issue is important, but it is necessary first to see some application  of the theory in order to best appreciate why, after millenniums of disinterest, logicians turned to the problem of explicating the concept of an effective finite procedure.

We now come to the important definition: A function f is called primitive recursive if there is a finite sequence of functions ending with f such that each that each function is a successor, constant, or identity function, or is defined from preceding functions in the sequence by substitution or recursion. Observe that this definition slays quite close to Skolem's intention to assume only four notions: natural number (which corresponds with constant function), successor of x (which corresponds with successor function), substitution of equals for equals (which corresponds with definition by substitution), and the recursive mode of thought (which corresponds with definition by recursion). Only the identity function has been added because this function has been found convenient in subsequent work. But the addition is well within the spirit of Skolem's pioneering paper. The results of math logic suggest that our starting assumption should be what ever is necessary for the theory of recursive functions. In the past, philosophers have taken elementary arithmetic, elementary geometry, and elementary logic as paradigms of certain knowledge. By taking the theory of recursive functions as basic, we actually gain the equivalents of all three. For example, we might then treat math logic itself as a branch of the theory of recursive functions. Such an approach would require a different order to topics of discussion; in particular, the  elementary parts of recursive theory would come before any "logic". But there is a more profound reason for taking this theory as basis, namely, the impossibility of completely formalizing and thus axiomatizing this theory. It constitutes the intuitive theory which, while it resists all  formalization, is nevertheless  necessary for the very purpose of setting up formal systems. All it tempts to avoid this core theory and instead to derive it from something else appear to commit the fallacy of begging the question.