Monday, November 04, 2002

Foundations of Complexity
Lesson 6: The Halting Problem

Previous Lesson | Next Lesson

Last lesson we learned about using reductions to show problems are hard. Now consider the most famous of undecidable problems, the halting problem:

LH = {<M> | <M> eventually halts with blank tape as input}
We will now show that LH is not computable. We do this by reducing the universal language LU to LH where LU is the set of pairs (<M>,x) such that M(x) accepts.

Given <M> and x, consider the following program:
Replace input with x.
Simulate M on x.
If M(x) accepts then halt.
If M(x) does not accept then go into an infinite loop.

Let us call this program N. Note that M(x) accepts if and only if N halts on blank tape.

Now here is the important point. Consider the function f that given <M> and x, will produce the program N. Even though M(x) and N may not halt the actual procedure that converts <M> and x to N is computable. This is just converting one program to another.

So we have that (<M>,x) is in LU if and only if M(x) accepts if and only if N=f(<M>,x) halts on blank tape if and only if N is in LH. Thus f reduces LU to LH and thus by the Lemma of Lesson 5, we have that LH is not computable.

I consider the noncomputability of the halting problem to be the single most important result in theoretical computer science. There are some programs, of course, that are easy to determine whether or not they will halt. But in general, no matter how smart you are or fast the computers, it is simply impossible to analyze a piece of code and see if it will terminate.

Using similar techniques one can prove a general result known as Rice's Theorem: Every nontrivial property of the computably enumerable languages is undecidable. More formally
Rice's Theorem: Let P be any non-empty proper subset of the computably enumerable languages. Then the language

LP = {<M> | L(M) is in P}
is not computable.

For example the following languages are not computable:

  • {<M> | L(M) is empty}
  • {<M> | L(M) is computable}
  • {<M> | L(M) is finite}

No comments:

Post a Comment