Slide 1Proofs of DecidabilityWhat Decidable MeansProofs of UndecidabilitySlide 5Proof by ReductionReduction ProofsConverse?Reduction PitfallsWhat “Can Do” MeansThe Halting ProblemIs HALTTM Decidable?Acceptance LanguageReducing ATM to HALTTMDeciding ATMEquivalence of DFA D and TM MEQDM Is UndecidableSlide 18Slide 19Rice’s TheoremWhich of these are Undecidable?Next ClassDavid EvansDavid Evanshttp://www.cs.virginia.edu/evanshttp://www.cs.virginia.edu/evanscs302: Theory of Computationcs302: Theory of ComputationUniversity of VirginiaUniversity of VirginiaComputer ScienceComputer ScienceLecture 17: Lecture 17: ProvingProvingUndecidabilityUndecidability2Lecture 17: Proving UndecidabilityProofs of DecidabilityHow can you prove a language is decidable?3Lecture 17: Proving UndecidabilityWhat Decidable MeansA language L is decidable if there exists a TM M such that for all strings w:–If w  L, M enters qAccept.–If w  L, M enters qReject.To prove a language is decidable, we can show how to construct a TM that decides it.For a correct proof, need a convincing argument that the TM always eventually accepts or rejects any input.4Lecture 17: Proving UndecidabilityProofs of UndecidabilityHow can you prove a language is undecidable?5Lecture 17: Proving UndecidabilityProofs of UndecidabilityTo prove a language is undecidable, need to show there is no Turing Machine that can decide the language.This is hard: requires reasoning about all possible TMs.6Lecture 17: Proving UndecidabilityProof by Reduction1. We know X does not exist.(e.g., X = a TM that can decide ATM )X2. Assume Y exists.(e.g., Y = a TM that can decide B)Y3. Show how to use Y to make X.Y4. Since X does not exist, but Y could be used to make X, then Y must not exist.7Lecture 17: Proving UndecidabilityReduction ProofsB reduces to AmeansYthat can solve B can be used to make Xthat can solve AThe name “reduces” is confusing: it is in the opposite direction of the making.Hence, A is not a harder problem than B.8Lecture 17: Proving UndecidabilityConverse?Ythat can solve B can be used to make Xthat can solve AA is not a harder problem than B.A reduces to BDoes this mean B is as hard as A?No! Y can be any solver for B. X is one solver for A.There might be easier solvers for A.9Lecture 17: Proving UndecidabilityReduction Pitfalls•Be careful: the direction matters a great deal–Showing a machine that decides B can be used to build a machine that decides A shows that A is not harder than B.–To show equivalence, need reductions in both directions.•The transformation must involve only things you know you can do: otherwise the contradiction might be because something else doesn’t exist.What does can do mean here?10Lecture 17: Proving UndecidabilityWhat “Can Do” Means•The transformations in a reduction proof are limited by what you are proving•For undecidability proofs, you are proving something about all TMs: the reduction transformations are anything that a TM can do that is guaranteed to terminate•For complexity proofs (later), you are proving something about how long it takes: the time it takes to do the transformation is limited11Lecture 17: Proving UndecidabilityThe Halting ProblemHALTTM = { <M, w> | M is a TM description and M halts on input w }Alternate statement as problem:Input: A TM M and input wOutput: True if M halts on w, otherwise False.12Lecture 17: Proving UndecidabilityIs HALTTM Decidable?•Possible “Yes” answer: Prove it is decidable•Possible “No” answer: prove it is undecidableDesign a TM that can decide HALTTM Show that no TM can decide HALTTM Show that a TM that could decide HALTTM could be used to decide ATM which we already proved is undecidable.13Lecture 17: Proving UndecidabilityAcceptance LanguageATM = { <M, w> | M is a TM description and M accepts input w }We proved ATM is undecidable last class.Since we know ATM is undecidable, we can show a new language B is undecidable if a machine that can decide B could be used to build a machine that can decide ATM.14Lecture 17: Proving UndecidabilityReducing ATM to HALTTM HALTTM = { <M, w> | M is a TM description and M halts on input w }ATM = { <M, w> | M is a TM description and M accepts input w }<M, w> is in ATM if and only if: M halts on input w and when M halts it is in accepting state.15Lecture 17: Proving UndecidabilityDeciding ATM•Assume HALTTM is decidable. •Then some TM R can decide HALTTM.•We can use R to build a machine that decides ATM:–Simulate R on <M, w>–If R rejects, it means M doesn’t halt: reject.–If R accepts, it means M halts:•Simulate M on w, accept/reject based on M’s accept/reject.Since any TM that decides HALTTM could be used to build a TM that decides ATM (which we know is impossible) this proves that no TM exists that can decide HALTTM .16Lecture 17: Proving UndecidabilityEquivalence of DFA D and TM MEQDM = { <D, T > | D is a DFA description, T is a TM description and L(T) = L(D) }Is EQDM decidable?17Lecture 17: Proving UndecidabilityEQDM Is Undecidable•Suppose R decides EQDM.•Can we use R to decide HALTTM?HALTTM = { <M, w> | M is a TM description and M halts on input w }EQDM = { <D, T > | D is a DFA description, T is a TM description and L(T) = L(D) }Given M and w, how can you construct D and T soR(<D, T>) tells you if M halts on w?18Lecture 17: Proving UndecidabilityEQDM Is UndecidableHALTTM = { <M, w> | M is a TM description and M halts on input w }EQDM = { <D, T > | D is a DFA description, T is a TM description and L(T) = L(D) }D = DFA that accepts all strings.T = TM that ignores input and simulates M on w, and if simulated M accepts or rejects, accept.19Lecture 17: Proving UndecidabilityEQDM Is UndecidableHALTTM = { <M, w> | M is a TM description and M halts on input w }EQDM = { <D, T > | D is a DFA description, T is a TM description and L(T) = L(D) }D = DFA that rejects all strings.T = TM that ignores input and simulates M on w, and if simulated M accepts or rejects, reject.20Lecture 17: Proving UndecidabilityRice’s TheoremAny nontrivial property about the language of a Turing machine is undecidable.Henry Gordon Rice, 1951Nontrivial means the property is true for some TMs, but not for all TMs.21Lecture 17: Proving UndecidabilityWhich of these are Undecidable?•Does TM M accept any strings?•Does TM M accept all strings?•Does TM M accept “Hello”?•Does TM M1 accept more