Week 12 - Halting problem

Statement

Halting problem

Given a programme with an input . Does ever terminate?

Link to original

We want to show that that this problem is computationally impossible or in other words it is undecidable.

Undecidable problem

Undecidable problem

A problem is undecidable if there is no algorithm that solves the problem on every input even given unlimited resources.

Link to original

The Halting problem is undecidable

Statement

Lemma

The Halting problem is undecidable.

Proof

Suppose we have an algorithm that solves the Halting problem on every input. Call this which returns true or false based on if terminates.

Define the following programme .

Harmful(J):
	Input: Some problem J
	Output: Null
1. If Terminator(J,J)
	1.1. Then goto 1
	1.2. else reutrn

What is ?

If then by definition is an infinite loop - contradicting .

If then by definition terminates after 1 step - contradicting .

Therefore no such programme can exist and we have the Halting problem is undecidable.

Link to original