Lecture Notes 26 Undecidability 1 Undecidabilty Read K & S 5.1, 5.3, & 5.4. Read Supplementary Materials: Recursively Enumerable Languages, Turing Machines, and Decidability. Do Homeworks 21 & 22. Church's Thesis (Church-Turing Thesis) An algorithm is a formal procedure that halts. The Thesis: Anything that can be computed by any algorithm can be computed by a Turing machine. Another way to state it: All "reasonable" formal models of computation are equivalent to the Turing machine. This isn't a formal statement, so we can't prove it. But many different computational models have been proposed and they all turn out to be equivalent. Examples: § unrestricted grammars § lambda calculus § cellular automata § DNA computing § quantum computing (?) The Unsolvability of the Halting Problem Suppose we could implement the decision procedure HALTS(M, x) M: string representing a Turing Machine x: string representing the input for M If M(x) halts then True else False Then we could define TROUBLE(x) x: string If HALTS(x, x) then loop forever else halt So now what happens if we invoke TROUBLE(“TROUBLE”), which invokes HALTS(“TROUBLE”, “TROUBLE”) If HALTS says that TROUBLE halts on itself then TROUBLE loops. IF HALTS says that TROUBLE loops, then TROUBLE halts. Either way, we reach a contradiction, so HALTS(M, x) cannot be made into a decision procedure.Lecture Notes 26 Undecidability 2 Another View The Problem View: The halting problem is undecidable. The Language View: Let H = {"M" "w" : TM M halts on input string w} H is recursively enumerable but not recursive. Why? H is recursively enumerable because it can be semidecided by U, the Universal Turing Machine. But H cannot be recursive. If it were, then it would be decided by some TM MH. But MH("M" "w") would have to be: If M is not a syntactically valid TM, then False. else HALTS("M" "w") But we know cannot that HALTS cannot exist. If H were Recursive H = {"M" "w" : TM M halts on input string w} Theorem: If H were also recursive, then every recursively enumerable language would be recursive. Proof: Let L be any RE language. Since L is RE, there exists a TM M that semidecides it. Suppose H is recursive and thus is decided by some TM O (oracle). We can build a TM M' from M that decides L: 1. M' transforms its input tape from à❑w❑ to à❑"M""w"❑. 2. M' invokes O on its tape and returns whatever answer O returns. So, if H were recursive, all RE languages would be. But it isn't. Undecidable Problems, Languages that Are Not Recursive, and Partial Functions The Problem View: The halting problem is undecidable. The Language View: Let H = {"M" "w" : TM M halts on input string w} H is recursively enumerable but not recursive. The Functional View: Let f (w) = M(w) f is a partial function on Σ* "M""w" pairsLecture Notes 26 Undecidability 3 Other Undecidable Problems About Turing Machines • Given a Turing machine M, does M halt on the empty tape? • Given a Turing machine M, is there any string on which M halts? • Given a Turing machine M, does M halt on every input string? • Given two Turing machines M1 and M2, do they halt on the same input strings? • Given a Turing machine M, is the language that M semidecides regular? Is it context-free? Is it recursive? Post Correspondence Problem Consider two lists of strings over some alphabet Σ. The lists must be finite and of equal length. A = x1, x2, x3, …, xn B = y1, y2, y3, …, yn Question: Does there exist some finite sequence of integers that can be viewed as indexes of A and B such that, when elements of A are selected as specified and concatenated together, we get the same string we get when elements of B are selected also as specified? For example, if we assert that 1, 3, 4 is such a sequence, we’re asserting that x1x3x4 = y1y3y4 Any problem of this form is an instance of the Post Correspondence Problem. Is the Post Correspondence Problem decidable? Post Correspondence Problem Examples i A B 1 1 111 2 10111 10 3 10 0 i A B 1 10 101 2 011 11 3 101 011 Some Languages Aren't Even Recursively Enumerable A pragmatically non RE language: L1={ (i, j) : i, j are integers where the low order five digits of i are a street address number and j is the number of houses with that number on which it rained on November 13, 1946 } An analytically non RE language: L2={x : x = "M" of a Turing machine M and M("M") does not halt} Why isn't L2 RE? Suppose it were. Then there would be a TM M* that semidecides L2. Is "M*" in L2? • If it is, then M*("M*") halts (by the definition of M* as a semideciding machine for L2) • But, by the definition of L2, if "M*" ∈ L2, then M*("M*") does not halt. Contradiction. So L2 is not RE. Another Non RE Language H Why not?Lecture Notes 26 Undecidability 4 Reduction Let L1, L2 ⊆ Σ* be languages. A reduction from L1 to L2 is a recursive function τ: Σ* → Σ* such that x ∈ L1 iff τ(x) ∈ L2. Example: L1 = {a, b : a,b ∈ N : b = a + 1} ß τ = Succ ß a, b becomes Succ(a), b L2 = {a, b : a,b ∈ N : a = b} If there is a Turing machine M2 to decide L2, then I can build a Turing machine M1 to decide L1: 1. Take the input and apply Succ to the first number. 2. Invoke M2 on the result. 3. Return whatever answer M2 returns. Reductions and Recursive Languages Theorem: If there is a reduction from L1 to L2 and L2 is recursive, then L1 is recursive. ττττ y ∈∈∈∈ L2?M1yesyes xy =τ(x)M2x ∈∈∈∈ L1?nono Theorem: If there is a reduction from L1 to L2 and L1 is not recursive, then L2 is not recursive. Reductions and RE Languages Theorem: If there is a reduction from L1 to L2 and L2 is RE, then L1 is RE. ττττ y ∈∈∈∈ L2?M1halthalt xy =τ(x)M2x ∈∈∈∈ L1? Theorem: If there is a reduction from L1 to L2 and L1 is not RE, then L2 is not RE.Lecture Notes 26 Undecidability 5 Can it be Decided if M Halts on the Empty Tape? This is equivalent to, "Is the language L2 = {"M" : Turing machine M halts on the empty tape} recursive?" L1 = H = {s = "M" "w" : Turing machine M halts on
View Full Document
Unlocking...