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.

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.