FIT2014 Lecture Notes - Lecture 17: If And Only If, Halting Problem, Turing Machine
29 Jun 2018
School
Department
Course
Professor
Lecture 17 Undecidability
Halting Problem
Input: Turing Machine P, input x
Question if P is run with input x, does it eventually halt?
Theorem: The halting problem is undecidable. Proof is by contradiction and includes a more elaborate version
of the Liar Paradox. “This sentence is False.” If the person is speaking the Truth but it was saying the sentence
is False, it doesn’t make sense.
Proof: (by contradiction)
Assume there is a Decider, D, for the Halting Problem.
- So it can tell, for any P and x, whether or not P eventually halts after being given input x.
- So it can tell, for any P, whether or not P eventually halts after being given input P
Constructs another program (Turing Machine) E as follows
Input: P
Use D to determine what happens if P runs on itself.
If P halts (return yes), with input P : loop forever.
If P loops forever (returns no), with input P: Stop.
What happens when R is given itself as input?
We run D decider for the halting program. It was given an input E. It tells us whether E halt when E given itself.
E does halt then D is going to halt and E loop forevers. Contradiction.
Decider can’t loop forever!
What happens when E is given itself as input?
If E halts, for input E: then E loops forever, for input E.
If E loops forever, for input E: then E halts, for input E. Contradiction! Q.E.D.
There is not decider for the halting problem ☺
DIAGONAL HALTING PROBLEM (Undecidable)
Input: Turing machine P
Question: Does P eventually halt, for input P ?
Document Summary
Proof is by contradiction and includes a more elaborate version of the liar paradox. (cid:862)this se(cid:374)te(cid:374)(cid:272)e is false. (cid:863) if the perso(cid:374) is speaki(cid:374)g the truth (cid:271)ut it (cid:449)as sa(cid:455)i(cid:374)g the se(cid:374)te(cid:374)(cid:272)e is false, it does(cid:374)"t (cid:373)ake se(cid:374)se. Assume there is a decider, d, for the halting problem. So it can tell, for any p and x, whether or not p eventually halts after being given input x. So it can tell, for any p, whether or not p eventually halts after being given input p. Constructs another program (turing machine) e as follows. Use d to determine what happens if p runs on itself. If p halts (return yes), with input p : loop forever. If p loops forever (returns no), with input p: stop. We run d decider for the halting program. It was given an input e. it tells us whether e halt when e given itself.
