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 , input (string)
Question: Does program terminate for every input ?

It is undecidable and semi-decidable.

Properties

Undecidability

Assume that the halting problem is decidable, i.e. there exists a program with the following properties:

• takes in 2 strings as input:
  1. : a program
  2. : the input for

1. produces the following output:
   1. true if program halts on input
   2. false if program does not halt on input

Given that exists, trivially, there exists a program that only takes one program as input, duplicates it and calls with those two (duplicate) program strings:

And again, we can generate another program using that does not hold if holds on :

First, we can observe:

1. halts on does not halt on input .
2. does not hold on halts on input .

What happens when runs with as input?

1. Case: halts on input . Then from observation (1) follows that does not hold on input , which is a contradiction.
2. Case: does not halt on input . Then from observation (2) follows that halts on input . We found another contradiction.

Therefore, that our initial assumption was wrong, i.e. there is no program 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.