Halting Problem

Implications of Halting Problem

(a) Programming

The Theorem of “Halting Problem” does not say that we can never determine whether or not a given program halts on a given input.

Most of the times, for practical reasons, we could eliminate infinite loops from programs. Sometimes a “meta-program” is used to check another program for potential infinite loops, and get this meta-program to work most of the time.

The theorem says that we cannot ever write such a meta-program and have it work all of the time. This result is also used to demonstrate that certain other programs are also impossible.

The basic outline is as follows:

(i) If we could solve a problem X, we could solve the Halting problem

(ii) We cannot solve the Halting Problem

(iii) Therefore, we cannot solve problem X.

(b) Artificial Intelligence (AI)

It has been tried to use the Halting Problem as an argument against the possibility of intelligent computers. The argument is as follows:

1. There are things computer cannot do
2. We can do those things
3. Therefore, we must be superior to computers.

The first premise given above is definitely TRUE. The second premise is generally supported by displaying a program which solves some subset of the Halting Problem, then describing a nice trick which is not incorporated into the program, that solves a slightly larger subset. There may well be valid arguments against the possibility of AI. This is not one of them.

Reduction to Halting Problem: In order to reduce a problem P to the Halting problem, look at the following steps:

1. Assume that you have an effective procedure—either a Turing machine or any kind of algorithm to solve problem P.
2. Show how to use the program for P to solve the Halting problem.
3. Conclude that problem P cannot be solved.

State Entry Problem: This problem otherwise called “dead code problem” is to determine whether Turing machine M, when given input w, ever enters state q. The only way a Turing machine M halts is if it enters a state q for which some transition function d(qi , ai ) is undefined. Add a new final state z to the Turing machine, and add all these missing transitions to lead to state z. Now use the assumed state-entry procedure to test if state z, is ever entered when M is given input w.

This will let us know if the original machine M halts. We conclude that it should not be possible to build the assumed state-entry procedure. Some unsolvable Problems are as follows:

1. Does a given Turing machine M halts on all input?
2. Does Turing machine M halt for any input?
3. s the language L(M) finite?
4. Does L(M) contain a string of length k, for some given k?
5. Do two Turing machines M1 and M2 accept the same language?

It is very obvious that if there is no algorithm that decides, for an arbitrary given Turing machine M and input string w, whether or not M accepts w. These problems for which no algorithms exist are called “UNDECIDABLE” or “UNSOLVABLE”.

Post’s Correspondence Problem: Let S be a finite alphabet, and let A and B be two lists of nonempty strings over S, with | A| =|B|, i.e., Post’s Correspondence Problem is the following. Does there exist a sequence of integers i1 , i2 , . .  im such that m  ≥ 1 and

Example: Suppose A = (a, abaaa, ab) and B = (aaa, ab, b). Then the required sequence of integers is 2, 1, 1, 3 giving

abaaa a a ab = abaaa aaa b.

This example has a solution. It will turn out that Post’s correspondence problem is insolvable in general.

Example 1: Prove that if L1 is not recursive, and there is a reduction from L1 to L2, then L2 is also not recursive.

Solution: Assume that L2 is recursive, as decided by Turing machine M2 and let T be the Turing machine that computes the reduction t. Then the Turing machine TM2 would decide L1. But L1 is undeciable—a contradiction.