5.4. Halting problem

We have seen above that most of the tasks are algorithmically unsolvable and in general, to decide whether a task can be solved by an algorithm is not obvious at all. One would think, however, that a if is a given Turing machine and is a word, then the decision whether terminates on or not, is somewhat simpler. A more precise definition of this task is the following.

Halting problem

Let  be given by its program  and let  be a word.
Decide whether  terminates on  or not.

There are two different approach of the halting problem: decide on a particular case or decide in general.

The first case is simpler, since separate methods can be used for different arguments.

The second case seems to be much more difficult. Here one have to find a general proving method, which works for every Turing machine and every input word. Since a proof is a sequence of well defined steps, thus a unified algorithm should be found. Related to the problem, the next theorem can be stated and proven.

Theorem 5.20.

There are no Turing machine, which can decide on every
Turing machine  given by its program  and every word
, whether  terminates on  or not.

Proof

The proof is indirect.

Assume that there exists a Turing machine , which can decide on every Turing machine given by a program and every word , whether terminates on the input or not. If terminates on then it returns the answer , otherwise it returns the answer . For simplicity, we may assume, that the input of is given in the form .

Accordingly to the above notations, let

- be the universal Turing machine,

- a Turing machine, which copies the content of tape to the tape .

Let be the following:

accepts the word if and only if accepts it, i.e. , since if does not terminate on a word, it cannot be accepted. Since forwards a word to if it found to be terminate, thus the computation is finite, any way, i.e. terminates on every input word . But this would mean that , which does not hold. The contradiction is because of our wrong (indirect) assumption. ✓

One may define a simpler version of halting problem.

Decide, whether a Turing machine  given by its 
program  teminates on the empty input or not.

Although the task seems to be simpler, the answer is the same.

Theorem 5.21.

There are no Turing machine, which can decide on every
Turing machine  given by its program ,  whether 
 terminates on the input  or not. 

Proof

The proof is indirect again.

Assume that there exists a Turing machine , which can decide on every Turing machine given by its program , whether terminates on or not.

Let be a Turing machine, which writes its input tape the word . This Turing machine is rather simple, since one need only state, e.g. and the transition function can me defined as where , if is odd and , if is even.

Let be a Turing machine, which creates the program of for the input word . In addition, the following Turing machines are used:

- a Turing machine, which copies the content of tape to the tape .

- starting from the rear end of tape copies everything to the tape until the first symbol

- deletes everything on tape from the end until the first sign . (The symbol itself is erased, too.)

- if the tapes and contain the Turing machines and , then it produces to the tape the program of the Turing machine . This is not a difficult task, too, since the two programs should be concatenated only and transition from the final state of the first to the initial state of the second should be defined.

Let be the following:

Clearly, terminates on every input.

If the input is a word in the form , then does the following:

1. copies to tape

2. copies the content of tape behind the symbol (i.e. the word ) to tape

3. creates the program of the Turing machine for the word to the first tape.

4. removes from tape the part behind , i.e. only remains

5. from the Turing machine programs on tapes and it creates the concatenated program to tape .

6. it observe, whether the Turing machine on tape terminates on the empty input or not.

The Turing machine created in step 5 is such that if it gets the empty word as an input, then it writes first the word to its tape and then operates as the original . I.e. it terminates on the empty input if and only if terminates on .

However, this means that accepts a word if and only if terminates on . But then solves the general halting problem, which is impossible. Hence our indirect assumption is wrong.