L7 - Halting Problem

Question 1

What was Hilberts statement?

Answer 1

Every mathematical problem must either resolve to a solution, or be proven impossible to solve via proof-of-impossibility of all solutions.

Question 2

Define the decision problem and who coined it…

Answer 2

Hilbert

Given a statement in a formal system, the statement can either be proven true or false by some procedure.

Question 3

Define the Halting problem

Answer 3

Give a universal machine P that executes a program Q with input T, can we be sure that Q will terminate in finite time…

Question 4

What type of problem is the Halting Problem?

Answer 4

Undecidable

Question 5

How can the Halting Problem be proven as undecidable?

Answer 5

Contradiction

Operate a ReverseHaltTester on the HaltTester → This will always lead to a contradiction. If HT returns true, the RHT will run infinitely and vice versa.

Question 6

Why is the Halting Problem considered Semi-decidable

Answer 6

Because termination is know for some inputs, but not all inputs.