Halting Problem

computation

Definition

Halting Problem

The halting problem is a decision problem that asks for an algorithm to determine, for any given program and its input, whether the program will eventually halt or run forever.

Instance: program $\Pi$, input (string) $I$
Question: Does program $\Pi$ terminate for every input $I$?

It is undecidable and semi-decidable.

Properties

Undecidability

Assume that the halting problem is decidable, i.e. there exists a program ${\Pi }_h$ with the following properties:

• ${\Pi }_h$ takes in 2 strings as input:
  1. $\Pi$: a program
  2. $I$: the input for $\Pi$

1. ${\Pi }_h$ produces the following output:
   1. true $⟺$ if program $\Pi$ halts on input $I$
   2. false $⟺$ if program $\Pi$ does not halt on input $I$

Given that ${\Pi }_h$ exists, trivially, there exists a program ${\Pi }_h^{\prime }$ that only takes one program as input, duplicates it and calls ${\Pi }_h$ with those two (duplicate) program strings:

$${\Pi }_h^{\prime }(\Pi :\text{String}):=\{\begin{array}{l}\text{return}{\Pi }_h(\Pi ,\Pi )\end{array}$$

And again, we can generate another program ${\Pi }_h^{\prime \prime }$ using ${\Pi }_h^{\prime }$ that does not hold if $\Pi$ holds on $\Pi$:

$${\Pi }_h^{\prime \prime }(\Pi :\text{String}):=\{\begin{array}{ll}\text{while}(\text{true})\text{do}\{\}& \text{if}\Pi \text{holds on}\Pi \\ \text{return false}& \text{else}\end{array}$$

First, we can observe:

1. $\Pi$ halts on $\Pi$ $⟹$ ${\Pi }_h^{\prime \prime }$ does not halt on input $\Pi$.
2. $\Pi$ does not hold on $\Pi$ $⟹$ ${\Pi }_h^{\prime \prime }$ halts on input $\Pi$.

What happens when ${\Pi }_h^{\prime \prime }$ runs with ${\Pi }_h^{\prime \prime }$ as input?

1. Case: ${\Pi }_h^{\prime \prime }$ halts on input ${\Pi }_h^{\prime \prime }$. Then from observation (1) follows that ${\Pi }_h^{\prime \prime }$ does not hold on input ${\Pi }_h^{\prime \prime }$, which is a contradiction.
2. Case: ${\Pi }_h^{\prime \prime }$ does not halt on input ${\Pi }_h^{\prime \prime }$. Then from observation (2) follows that ${\Pi }_h^{\prime \prime }$ halts on input $H_h^{\prime \prime }$. We found another contradiction.

Therefore, that our initial assumption was wrong, i.e. there is no program ${\Pi }_h$ that decides the halting problem. We can conclude:

The halting problem is undecidable.

Semi-Decidability

The halting problem is undecidable. We can write an interpreter which steps through the code and on termination, signals that the interpreted program terminated, and returns TRUE. Otherwise, it never halts. This complies with semi-decidability.