The Halting Problems

Question 1

How to study the notion of Computability:

Answer 1

Look at theoretical models (formalizations) of the intuitive notion of computability

Why?
Shows the limitations of what is computable

Question 2

How to show that something is impossible:

Answer 2

• We’ve seen that this can be done using arguments by contradiction.
• But, to show that there is no computable / algorithmic solution for certain problems, we
  need to specify what counts as an computation / algorithm.
• Once we have settled this, we can use it to derive contradictions. . .

Question 3

What can a TM do when stated on a given input x?

Answer 3

They can
1. halt / terminate: TM( x ) ↓
2. loop / run forever: TM( x ) ↑

Question 4

How are TM recursively enumerable?

Answer 4

Only consists of a finite sequence of sumbols from a finite alphabet, they can be enumerated

(1) Assign them unique Godel numbers then list them in order of these numbers

(2) Try to come up with a way to generate all TMs

Question 5

What is the Halting Set?

Answer 5

Given an emuration T0, T1, T2, … of TM, define the follow set of natural numbers: K

K is the set of indices of TM that halts if the input of their own index in the enumeration. The HALTING set

Note: T2(5) means that it is TM 2 running input 5

Question 6

What is the big question (with the Halting Problem)?

Answer 6

Can you find a TM that decides for each number x ∃ ℕ, whether x ∃ K or x ∄ K?

Question 7

Conclusion of the Halting Problem

And diagonization proof (by contradiction).

Claim: set K of natural numbers cannot be decided by a TM
Assumption: (for the sake of contradiction) There a exists a TM that decides the set K

Answer 7

Conclusion: There is no TM that decides for each number x ∃ ℕ, whether x ∃ K or x ∄ K

The Halting Problem is not computable by n TM.

By Turing’s Thesis, it is uncomputable

Question 8

How can the set K be enumerated, by dovetailing?

Answer 8

Question 9

Structure of a proof by diagonalization:

Answer 9

1. Assume a claim about certain things.
2. Make a list of all these things (the ‘table’).
3. Define a new thing (of the same kind) using all the elements in this list.
4. Derive a contradiction from the fact that this thing itself should be in the list.