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.

home | consulting | videos | book | QM FAQ | contact |