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

_{H}= {<M> | <M> eventually halts with blank tape as input}

_{H}is not computable. We do this by reducing the universal language L

_{U}to L

_{H}where L

_{U}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 L_{U} 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 L_{H}. Thus f reduces L_{U} to L_{H} and
thus by the Lemma of Lesson 5, we have that L_{H} 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

_{P}= {<M> | L(M) is in P}

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