- Why is this technique we used to prove undecidability diagonalization?
- Think of a table of Turing machines and inputs in which Turing machine i has Turing
machine i as its input
- Think of a table of Turing machines and inputs in which Turing machine i has Turing
machine i as its input
- Last page of section 4.2
- L is decidable iff L and complement of L are both recognizable
- Proof given in book
- So if L undecidable then L or its complement is unrecognizable
- Example: co-ATM aka complement of acceptance
- L is decidable iff L and complement of L are both recognizable
- Examples / discussion
- Is the Halting Problem (Halt) Turing recognizable? What about co-Halt?
- Recognizer for Halt(M,w)
Run M on w Accept - So by theorem, co-Halt must be unrecognizable
- Recognizer for Halt(M,w)
- Can you prove unrecognizability by diagonalization?
- Try proving co-Halt unrecognizable by diagonalization
- Assume CH( M, w ) recognizes co-Halt, i.e., accepts if M does not halt on w (or if M isn’t an encoding of a Turing machine at all)
- Construct PARADOX( M ) as
PARADOX(M) Run CH( M, M ) If CH accepted Accept Else Loop forever - Contradiction: CH cannot correctly analyze PARADOX(PARADOX)
- Is the Halting Problem (Halt) Turing recognizable? What about co-Halt?
- Reduction
- Example: proving HALT undecidable by reduction
- Assume H(M,w) decides halting problem for machine M and input w
- Create A(M,w) to decide acceptance problem for M and w
A(M,w) If H(M,w) accepts Run M on w If M accepts, accept Else reject Else Reject
- Read introduction to chapter 5 and section 5.1 up to but not including
“Reductions via Computation Histories”
- Page 215 through top 2/3 of page 220