New version of this book

Recursive functions

In mathematics we express operations that we cannot possibly perform. Consider the statement . To determine if this statement is true we would need to take every integer x and see if there exists any integer y such that is true. If there is any integer x for which we cannot find such a y the statement does not hold. Clearly there is no general way to determine if such a statement is true. We can define functions in ZF through relationships of the form where A defines a unique y for every x. However if A contains any quantifiers then there is no general way to compute the function. In the 1930's several proposals were made to characterize what is meant by a mathematical algorithm  , i.e., a mathematical procedure that could be carried out in a finite number of steps to compute any value of a function. These attempts were all shown to be equivalent. The fascinating thing about this is that we need so little machinery to fully characterize mathematical algorithm. Any computer, if it had access to potentially infinite storage, would qualify as a universal TM   . That is for any algorithmically computable or recursive function there is a program for that computer that will compute each value of the function in a finite time.

An important implication of this is that we can Gödel number  , i.e., assign a unique integer to every possible recursive algorithm. All we need to do is concatenate the bits that describe the program Programs typically have parameters and we can arbitrarily divide up the memory into program area and data area. To allow for arbitrarily large programs and arbitrarily large input we can think of the memory as an infinite tape with a center mark. The program is written on one side of the mark and the initial parameter on the other. For any specific program and parameter we can easily compute the Gödel number of a program with no parameter that will perform exactly the same steps. The distinction between input and program is arbitrary. We can just as easily encode the input in the program. We define as a numbering of all programs with no parameter and as a Gödel numbering of programs with a single parameter.

Theorem. There can exist no program (recursive algorithm) D with a single parameter n such that if halts in a finite time and if it never halts. This is often referred to as the halting problem  .

Assume there is such an algorithm. We can use this algorithm to construct a new function such that if halts and if loops forever. We have a specialized version of the halting problem for programs that have their own own Gödel number as input. If we can solve the general halting problem we can solve this specialized version. The specialized version allows us to apply a simple version of the diagonal argument that is crucial to Gödel 's proof and many related proofs.

From we construct that loops for ever if . We can compute m such that . Consider . By the definition of , if and only if halts. From the construction of , (which is ) loops forever if . Thus we conclude that loops forever if halts. The assumption that exists is false and the theorem is proved.

Theorem. There is a set that is recursively enumerable but not recursive  .

The proof is trivial once one understands that one can with a single recursive process simulate all recursive processes  . For example one can for each n simulate the first n recursive processes for n steps. Eventually you will simulate every step for every recursive process. As soon as one of these halts you can output the Gödel number of this process. Thus the Gödel numbers of recursive processes that halt are recursively enumerable. We have already proven that this set is not recursive. We cannot decide with a recursive algorithm what numbers do not belong to this set.

New version of this book