The Halting Problem

There are objects / entities which one can describe but which cannot exist.

1. The Halting Problem

A register machine decides the Halting Problem if for all , starting with and all other registers zeroed, the computation of always halts with containing , or ; moreover when the computation halts, iff the register machine program with index eventually halts when started with and all other registers zeroed.

Theorem: No such register machine exists.

1.1 Proof

Assume that we have an RM program that decides the Halting Problem:

1. Let be obtained by replacing by where is a register not mentioned in s program.
2. Let be obtained from by replacing each by .
3. Let be the index of 's program.
4. Now, started with eventually halts iff:
   • started with halts with iff:
   • started with halts with iff:
   • started with does not halt iff:
   • started with does not halt. This is a contradiction.

2. Enumerating Computable Functions

For each , let by the unary partial function computed by the register machine program with index . So, holds iff the computation of started with and all other registers zeroed halts with .

Thus, defines a surjection from to the collection of all computable partial functions from to . Hence, the collection of all computable partial functions from to is countable. This means that is uncountable, and contains uncomputable functions.

2.1 An Uncomputable Function

Let be the partial function . Thus:

Recall, means terminating, means never terminating.

If was computable, and hence:

• If , then , so , and .
• If , then , and .

This is a contradiction, so is uncomputable.

3. Undecidable Sets

Given a subset \chi_S\in\mathbb{N}\rightarrow\mathbb{N}$ is given by:

is decidable if its characteristic function is computable. Otherwise, is undecidable.

So is decidable iff there is a register machine with the property: , started with and all other registers zeroed halts with iff .

To prove is undecidable, show the decidability of would imply the the decidability of the Halting Problem.

3.1 An Undecidable Set

Proof that is undecidable:

• Suppose is a register machine that computes .
• From , we can construct a register machine :

• By assumption on , decides the Halting Problem.
• This is a contradiction, as the Halting Problem is undecidable.
• Therefore, does not exist, ( is uncomputable), and is undecidable.

3.2 Another Undecidable Set

Proof that is undecidable:

• Suppose is a register machine that computes .
• From , we can construct a register machine :

• By assumption on , decides .
• This is a contradiction, as is undecidable.
• Therefore, does not exist, ( is uncomputable), and is undecidable.