The Halting Problem, which states that there isn't a function h(e, x) to decide whether the computation e halts on x, in its most famous version it is proved by Alan Turing to show that such Turing Machine can not exist. But this can also be proved, however less intuitive, by a method that is independent of any model of computation. Based on the knowledge of Recursive Functions

Primitive Recursive Function

Definition: Primitive Recursion

Define \overrightarrow{x_k} to be x_1,x_2,...,x_k. The Primitive Recursion Operator \rho is defined by \rho(g, h)=f provided that g(\overrightarrow{x_k}) is a k-arg function, h(\overrightarrow{x_{k+2}}) is a k+2-ary function, and f is a k+1-ary function such that:

\begin{aligned}
f(\overrightarrow{x_k}, 0)=&\ g(\overrightarrow{x_k})\\
f(\overrightarrow{x_k}, y+1)=&\ h(\overrightarrow{x_k}, y, f(\overrightarrow{x_k}, y))
\end{aligned}

The function f can be viewed as a function defined recursively on its predecessors' values. The base case, where the last argument of f is 0 is defined by function g; and the induction case, where the last argument of f is y+1 is defined by function h which use the value of f applied on the predecessor of y+1 as its last argument, effectively makes f defined recursively on its own values of predecessors of y+1

Definition: Primitive Recursive Function

A function f is said to be Primitive Recursive, if it's definition only makes use of the following operations(that the set of all primitive recursive functions are defined inductively by the following definitions):

  1. The constant zero function z(x)=0
  2. The successor function succ(x), which effectively returns the value of x+1, for simplicity purpose sometimes we'll write x+1 instead
  3. The projection function P_i^n(\overrightarrow{x_n})=x_i, which selects the i-th argument of P
  4. The composition operator \circ such that the k-ary function (f\circ \overrightarrow{g_m})(\overrightarrow{x_k}) is defined to be f(g_1(\overrightarrow{x_k}),...,g_m(\overrightarrow{x_k})), where f is an m-ary primitive recursive function and g is a k-ary primitive recursive function
  5. The primitive recursion operator \rho(g, h) where g and h are primitive recursive

There are a lot of functions that are primitive recursive, for example, both addition function and multiplication function are primitive recurisve. Meanwhile, the relations can also be primitive recursive, depending on whether its characteristic function is primitive recursive.

Definition: Primitive Recursive Relation

A k-ary relation T(\overrightarrow{x_k}) is said to be primitive recursive, if its characteristic function:

\mathcal{X}_T(\overrightarrow{x_k})=
\begin{cases}
1 &\text{if } T(\overrightarrow{x_k})\\
0 &\text{otherwise}
\end{cases}

is primitive recursive.

Theorem: Primitive recursive functions are computable
Proof sketch: Primitive recursive functions are computable in an intuitive sense: it is easy to see that the zero function, successor function, and projection function are all computable, then we can see that the computable functions are closed under primitive recursive operator, because computing a function that is defined by primitive recursive operator is just like a recursive function of which the parameter is strictly decreasing before reaching the base case along the recursive call, so the termination is guaranteed. ∎

Recursive Function

Theorem: Not all computable functions are primitive recursive

Proof: First, we are going to prove that the set of all primitive recursive functions are countable, we can use Godel Numbering to assign each primitive recursive function a unique natural number; the trick is to trace through the operation sequence (1 to 5) that function used to form itself and apply the numbering to that sequence1; since we can map every primitive recursive function to a natural number, we could say that the set of all primitive recursive functions are enumerable: for every natural number k, tries to decode it to see if it codes a primitive recursive function, if so, list it down; at last we can get an enumeration of primitive recursive functions. And since it is enumerable, it is countable.
  After proving the set of all primitive recursive functions are countable, we can use diagonalization to show that there exists at least one function that is computable but not primitive recursive. To start with, we need to mention two things: 1. The encoding and decoding of the primitive recursive functions are computable; the encoding function utilizes the exponentiation function and multiplication function which are both known to be computable, while the decoding function incorporates the sequence operations, including append, concat, and elementAt which are all known to be computable2. 2. The set of all primitive recursive functions are enumerable, which means each primitive recursive function inside it will have an ordinal number. Suppose that we have a function \varphi(i,x) which computes the i-th primitive recursive function f_i on x, i.e., \varphi(i, x)=f_i(x); we can show that this function is computable, because decoding i-th primitive recursive function is itself computable and after the decoding it's just executing the decoded f_i which is, by definition, primitive recursive. We can define the function h by:

\begin{aligned}
h(x)=&\ \varphi(x,x) + 1\\
=&\ f_x(x)+1
\end{aligned}

Now, this function is computable, since we know that \varphi is computable, addition is computable, and 1 can be written in succ(0)) which is computable. For each primitive recursive function f_i, h_i and f_i differs at i, i.e., h(i)\neq f_i(i) for every f_i, and since all the f_i constitute the set of all primitive recursive functions, we can say that h is computable but not primitive recursive. ∎

  To expand our view to all computable functions, we will introduce a new operator, namely the Unbounded Minimization Operator.

Definition: Unbounded Minimization Operator

If f(\overrightarrow{x_k}, z) is primitive recursive. The Unbounded Minimization Operator, or \mu-operator, written \mu z.f(\overrightarrow{x_k},z) is a operator that search for the least natural number z such that f(\overrightarrow{x_k}, 0),f(\overrightarrow{x_k}, 1),...f(\overrightarrow{x_k}, z) are all defined and f(\overrightarrow{x_k}, z)=0 if such z exists, otherwise undefined. This function is computable in the sense that you can start by testing z=0,1,2,3,..., but it's not primitive recursive by observing that no condition guarantees the search of z will terminate. Note that if we adopt its bounded version, that the search of z is limited below a certain cutoff y, then it will become primitive recursive.

Definition: General Recursive Function

A function is said to be General Recursive, Partial Recursive, Partial Computable, if it is defined using the five rules used to define the primitive recursive functions, plus the unbouned minimization operator. If the function is total, it is called Total Recursive Function or simply Recursive Function.

The Halting Problem

  As the start of this article, I use the phrase "the computation e". But this is not rigorous, what exactly is the "computation e"? To formalize this, we need Kleene's Normal Form Theorem, or Kleene's T Predicate.

Theorem: Kleene's T Predicate

There is a primitive recursive relation T(e, x, s) and a primitive recursive function U(s) such that if f is any partial recursive function, then for some e such that for every x, we have:

f(x)\simeq U(\mu s.T(e,x,s))

where the f \simeq g is a congruence states that for every x, either f(x) and g(x) are both undefined, or f(x)=g(x).

This theorem says that, every partial recursive function f has a godel number e, if f(x)\downarrow, which means f is defined at x, then there is a godel number s that "codes" the computation procedure of f(x), if you are familiar with computation models like Turing Machine or Lambda Calculus, you can think of s as a table that records each step (the character it reads/writes, the tape head goes left/right) of a turing machine, or the evaluation process of a lambda term. Then the function U will execute s like a "playback". In essential, U(\mu s.T(e,x,s)) can be read as "the function with godel number e is defined on x, and the computation is coded in s, find the least s, then execute it", and the execution either produces the same value as f(x), or is undefined together with f(x).
  The T predicate theorem shows that the set of all partial recursive functions are also countable, we can use the same way to start from 0, tries to decode it and see if it's a partial recursive function. We can also search through all natural numbers to find a particular number that codes a computation of the function with godel number e on input x.

  Now, we can define the Halting Problem on the basis of recursive functions. The original statement states that the function:

h(f,n)=
\begin{cases}
1 &\text{if function }f\text{ halts on }n\\
0 &\text{otherwise}
\end{cases}

is not computable. From the normal form theorem, we know that for every f there is a number e that codes it, let \varphi_e(x)\simeq U(\mu s.T(e,x,s)) be the partial recursive function that is coded by e. We have the following definition of halting problem:

Definition: Halting Function

The halting function h is defined by

h(e,n)=
\begin{cases}
1 &\text{if }\varphi_e(x)\downarrow \\
0 &\text{otherwise}
\end{cases}

Halting Problem: The Halting Function is not computable

Proof: Define the function d(e) to be:

d(e)=
\begin{cases}
1 &\text{if }h(e,e)=0 \\
\text{undefined} &\text{otherwise}
\end{cases}

The "undefined" here is actuall an abbreviation for some non-terminating operations, such as \mu x.x\neq x, which will never terminates since there is no x such that x \neq x. So actually d(e) is defined if and only if h(e,e)=0, that is, h(e,e) is undefined, which is:

  1. If \varphi_e(e) is defined or e does not code any function, then d(e) is defined.
  2. If \varphi_e(e) is defined, then d(e) is undefined.

If h is partial computable, then d must also be partial computable, which, by T predicate theorem, will have its own number e_d. Consider the value of h(e_d,e_d):

  1. If h(e_d,e_d)\downarrow, then by the definition of h we have e_d(e_d)\downarrow, by the definition of e_d we have d\simeq e_d, which means d(e_d) is also defined, but by definition of d, d(e_d) is defined only when h(e_d,e_d) is undefined. So we stuck in a contradictory situation where h(e_d,e_d) is undefined only if h(e_d,e_d) is defined.
  2. If h(e_d,e_d)\uparrow, then by the definition of h we have e_d(e_d)\uparrow, by the definition of e_d we have d\simeq e_d, which means d(e_d) is also undefined, but by definition of d, d(e_d) is undefined only when h(e_d,e_d) is defined. So we stuck in the contradictory situation again where h(e_d,e_d) is defined only if h(e_d,e_d) is undefined.

The result is that, as a conclusion, the number e_d cannot be the godel number of any computable function, this contradict with the premise that h is computable, because if h is computable then so is d, then by definition e_d must exist. So we must conclude that the function h cannot be partial computable. ∎


  1. This is a practical approach, as long as we don't mind that current computers are not fast enough such that it may take forever to compute the numbers, check dylech30th/PCF for the encoding and decoding algorithms and see how fast the output grows. ↩︎
  2. By utilizing the prime factorization, which can be defined using bounded minimization operator which is primitive recursive. ↩︎

欲少留此灵琐兮,日忽忽其将暮