Self-Halting Problem

Introduction

This piece of code produces a sequence of values called the Collatz sequence. Every input that has been tried causes this program to halt. Since we don’t know if this program halts for every possible input, we cannot calculate an upper bound, but we can show that the lower bound is W(log n).

Even though computers are powerful devices, they also have limitations. For instance, it would be nice to know a priori whether or not a program would go into an infinite loop. One theoretically important problem that cannot be solved or is not decidable by any (Turing) computer is the Self-Halting problem. In 1936, Alan Turing demonstrated that the Self-halting problem is unsolvable. The Self-halting problem tells us that in general, there will never be a program that can determine if another program will halt given a specified input. For instance, we do not know for sure if the following piece of pseudo-code halts on every possible input:

while (x > 1) do

if (x is odd) do

x = 3 * x + 1

else do

x = x / 2

The Self-Halting problem involves determining whether a program will ever terminate. The proof idea of the Self-halting problem is that a machine is unable to verify or halt on its own descriptive input. We can ask, given a machine and its description as input does this machine halt? We will see below by contradiction that it does not halt. Thus, a computer cannot solve the general problem of software verification, that is, determining for any program whether it terminates for all possible inputs. Therefore, the Self-Halting problem for Turing Machines is not Turing-computable in terms of the Church-Turing thesis. Below we have two formulations of the Self-halting proof. The first one is by Sipser and the second one is by Taylor.

Sipser Formulation

We have a Turing machine H, which takes as input a representation or description of another Turing machine M and an input word w, such as in the following:

{

accept if M accepts w

reject if M rejects w

H(áM, wñ) =

We construct a new Turing machine D with H as a subroutine, where D calls H to determine what M does when the input to M is its own description áMñ. D then does the opposite of what M (or H) does. So, we have:

D(áMñ) = opposite[H(áM, áMññ)]:

Where D runs H on input áM, áMññ, and outputs the opposite of what H outputs.

D(áMñ) =

Then if we run D with its own description áDñ as input, D(áDñ) = opposite[H(áD, áDññ)], we have a contradiction.

D(áDñ) =

The contradiction is that when D rejects its own description áDñ (which means H yields a rejection) we get an acceptance by definition of D since D wants to produce the opposite of H. But how can we have an acceptance when D rejected áDñ? And so, we can never know for sure whether this halts or not.

\ Neither TM D nor TM H can exist. ΢

Taylor Formulation

Let us represent the Self-Halting problem, P_s, as a (number-theoretic) function and show that P_s is not Turing-computable. The proof is in three steps and is a contradiction. This proof closely resembles Gregory Taylor’s from Models of Computation and Formal Languages.

First Step

Suppose we have an enumeration of Turing Machines <TM₀, TM₁, TM₂, ..., TM_n> such that TM₀ has the smallest Gödel number and increases accordingly. Now, lets say that TM_n computes on a tape starting from the left, with a string of n + 1 1's representing n where n is a natural number. If TM_n halts with a value representation, given it's own Gödel number as input, then we shall say that TM_n self-halts.

So, we ask is there an algorithm for determining if TM_n self-halts for n ≥ 0?

Second Step

Every Turing Machine can compute a (partial unary number-theoretic) function called the everywhere-undefined function. We can write a unary function ƒ_n computed by TM_n. We now can further enumerate Turing-computable functions <ƒ₀, ƒ₁, ƒ₂, ..., ƒ_n>. Thus, ƒ_n(n) is either defined or undefined.

So, we now ask is there an algorithm for determining if ƒ_n(n) is defined for n ≥ 0?

Third Step

We can clearly show where ƒ_n(n) can be defined and cannot be defined. For instance, if ƒ₃(n) = n³, then ƒ₃(3) = 3³ which equals 27, a self-halting value. Where as ƒ₂₀(n) = 10 - n would be undefined for n = 20 and for any n > 10, thus not self-halting. So now we can formulate P_s.

Ps(n) = {

ƒn(n) + 1      if ƒn(n) is defined 0                      if ƒn(n) is undefined

The significance of this formulation is to show that we have an algorithm that successfully calculates P_s (as long as the Self-Halting problem is solvable.)

So, we then ask if P_s, as just defined above, is effectively computable?

Contradiction

P_s is not Turing-Computable by contradiction. Suppose that a Turing Machine TM computes P_s. Let g be the Gödel number of TM so that TM = TM_g and P_s = ƒ_g. Now, lets say that P_s takes g as input, which results in either 0 or ƒ_g(g) + 1. If P_s(g) = ƒ_g(g) + 1 we would have ƒ_g(g) = P_s(g) = ƒ_g(g) + 1, which is not correct. Also, if in the other case, P_s(g) = 0 implies that ƒ_g(g) is undefined. However, since P_s = ƒ_g by contradiction P_s(g) cannot be undefined. Therefore, no Turing Machine can compute P_s.

΢

Full-Halting Problem

The Full Halting Problem for Turing Machines can follow the same iterative logic as the Self-Halting problem for Turing machines. Let us represent the Full-Halting problem, P_f, as a (number-theoretic) function and show that P_f is not Turing-computable. The final step would yield the following total number-theoretic function:

Ps(n, m) = {

ƒn(m) + 1     if ƒn(m) is defined 0                    if ƒn(m) is undefined

The assertions is that FH* is not Turing-computable thus unsolvable.

Proof

Let's prove this assertion by contradiction. Let's say that P_f is Turing-computable. P_f(n, m) is defined for any n and m, thus we can say that P_f(n, n) is defined for any n, thus we have:

Ps(n, n) = {

ƒn(n) + 1     if ƒn(n) is defined 0                   if ƒn(n) is undefined

Now, we would like to compare the Full-Halting problem's definition to the Self-Halting problem's definition, namely P_f(n, n) = P_s(n), for all n. So, what this says is that P_s is now Turing-computable which we showed not to be the case for the Self-Halting problem. Therefore, by contradiction we show that P_f is not Turing-computable, thus by Church-Turing the Full-Halting problem for Turing Machines is not solvable.

€

Conclusion

The Self-Halting problem reduces to the Full-Halting problem because a solution to the Full-Halting problem would yield a solution to the Self-Halting problem. In terms of decidability, since the Self-Halting problem is reduced to the Full-Halting problem, but is not Turing-computable then the Full-Halting problem is at least as hard the Self-Halting problem. So, if the Self-Halting problem reduces to the Full-Halting problem and the Full-Halting problem is decidable then the Self-Halting problem is decidable, as well, which of course is found by contradiction, is not the case. Furthermore, again in terms of unsolvability, when the Self-Halting problem is undecidable and reduces to the Full-Halting problem, then the Full-Halting problem is also undecidable, as we have found to be the case.

Links

http://shakti.trincoll.edu/~rtaylor/thcomp/chapter8.ppt
http://hebb.cis.uoguelph.ca/~skremer/Teaching/CIS4600/Lectures/27460/
http://cs.engr.uky.edu/~lewis/texts/theory/unsolvability/reduce.pdf
http://www.cs.washington.edu/homes/csk/halt.html
http://www.wikipedia.org/wiki/Halting_problem
http://mathworld.wolfram.com/HaltingProblem.html
http://faculty.juniata.edu/rhodes/intro/theory2.htm
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/halt.html
http://mini.net/tcl/644