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.