Decidable Languages Prof. Busch - LSU 1 Recall that: A language L is Turing-Acceptable if there is a Turing machine M that accepts L Also known as: Turing-Recognizable or Recursively-enumerable languages Prof. Busch - LSU 2 For any string w : w L M halts in an accept state w L M halts in a non-accept state or loops forever Prof. Busch - LSU 3 Definition: A language L is decidable if there is a Turing machine (decider) M which accepts L and halts on every input string Also known as recursive languages Prof. Busch - LSU 4 For any string w : w L M halts in an accept state w L M halts in a non-accept state Every decidable language is Turing-Acceptable Prof. Busch - LSU 5 Sometimes, it is convenient to have Turing machines with single accept and reject states q accept q reject These are the only halting states That result to possible halting configurations Prof. Busch - LSU 6 We can convert any Turing machine to have single accept and reject states New machine Old machine q accept x x ,R x x ,R x x ,L x x ,R Multiple accept states For each tape symbol x One accept state Prof. Busch - LSU 7 Do the following for each possible halting state: New machine Old machine qi x x , R For each qi Multiple reject states q reject For all tape symbols x not used for read in the other transitions of q i One reject state Prof. Busch - LSU 8 For a decidable language L : Decider for L q accept Input string q reject Decision On Halt: Accept Reject For each input string, the computation halts in the accept or reject state Prof. Busch - LSU 9 For a Turing-Acceptable language L : Turing Machine for L q accept Input string q reject It is possible that for some input string the machine enters an infinite loop Prof. Busch - LSU 10 Problem: Is number x prime? Corresponding language: PRIMES {1, 2, 3, 5, 7, } We will show it is decidable Prof. Busch - LSU 11 Decider for PRIMES : On input number x : Divide x with all possible numbers between 2 and x If any of them divides x Then reject Else accept Prof. Busch - LSU 12 the decider for the language solves the corresponding problem Decider for PRIMES q accept Input number x (Input string) YES is x prime? (Accept) q reject (Reject) Prof. Busch - LSU NO 13 Theorem: If a language L is decidable, then its complement L is decidable too Proof: Build a Turing machine M that accepts L and halts on every input string ( M is decider for L ) Prof. Busch - LSU 14 Transform accept state to reject and vice-versa M M q accept q reject qa qa q reject q accept qr qr Prof. Busch - LSU 15 Turing Machine M On each input string w do: 1. Let M be the decider for L 2. Run M with input string If M If M w accepts then reject rejects then accept Accepts L and halts on every input string Prof. Busch - LSU END OF PROOF 16 Undecidable Languages An undecidable language has no decider: each Turing machine that accepts L does not halt on some input string We will show that: There is a language which is Turing-Acceptable and undecidable Prof. Busch - LSU 17 We will prove that there is a language L: • is not Turing-acceptable (not accepted by any Turing Machine) • L L is Turing-acceptable the complement of a decidable language is decidable Therefore, L is undecidable Prof. Busch - LSU 18 Non Turing-Acceptable Turing-Acceptable L L Decidable Prof. Busch - LSU 19 A Language which is not Turing Acceptable Prof. Busch - LSU 20 Consider alphabet Strings of {a } {a } : a , aa , aaa , aaaa , a 1 a 2 a 3 Prof. Busch - LSU a 4 21 Consider Turing Machines that accept languages over alphabet {a } They are countable: M 1, M 2 , M 3 , M 4 , (There is an enumerator that generates them) Prof. Busch - LSU 22 Each machine accepts some language over {a } M 1, M 2 , M 3 , M 4 , L ( M 1 ), L ( M 2 ), L ( M 3 ), L ( M 4 ), Note that it is possible to have L(M i ) L(M j ) for i j Since, a language could be accepted by more than one Turing machine Prof. Busch - LSU 23 Example language accepted by M i L ( M i ) { aa , aaaa , aaaaaa } 2 4 6 L ( M i ) {a , a , a } Binary representation a L(M i ) 1 0 a 1 2 a 3 0 a 4 1 Prof. Busch - LSU a 5 0 a 1 6 a 7 0 24 Example of binary representations a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Prof. Busch - LSU 25 Consider the language i i L { a : a L ( M i )} L consists of the 1’s in the diagonal Prof. Busch - LSU 26 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 4 L { a , a , } Prof. Busch - LSU 27 Consider the language i i i i L L { a : a L ( M i )} L { a : a L ( M i )} L consists of the 0’s in the diagonal Prof. Busch - LSU 28 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 1 2 L { a , a , } Prof. Busch - LSU 29 Theorem: Language L is not Turing-Acceptable Proof: Assume for contradiction that L is Turing-Acceptable There must exist some machine M k that accepts L : L(M k ) L Prof. Busch - LSU 30 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: M k M 1 ? Prof. Busch - LSU L(M k ) L 31 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 1 Answer: a L(M k ) M k M1 1 Prof. Busch - LSU a L(M 1) 32 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: M k M 2 ? Prof. Busch - LSU L(M k ) L 33 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 2 Answer: a L(M k ) Mk M2 2 Prof. Busch - LSU a L(M 2 ) 34 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: M k M 3 ? Prof. Busch - LSU L(M k ) L 35 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 Answer: a L(M k ) Mk M3 3 Prof. Busch - LSU a L(M 3 ) 36 Similarly: Mk Mi for any i Because either: i a L(M k ) i or i a L(M k ) i a L(M i ) a L(M i ) the machine M k cannot exist L is not Turing-Acceptable Prof. Busch - LSU End of Proof 37 Non Turing-Acceptable L Turing-Acceptable Decidable Prof. Busch - LSU 38 A Language which is Turing-Acceptable and Undecidable Prof. Busch - LSU 39 We will prove that the language i i L { a : a L ( M i )} Is TuringAcceptable There is a Turing machine that accepts L Undecidable Each machine that accepts L doesn’t halt on some input string Prof. Busch - LSU 40 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 4 L { a , a , } Prof. Busch - LSU 41 Theorem: The language i i L { a : a L ( M i )} Is Turing-Acceptable Proof: We will give a Turing Machine that accepts L Prof. Busch - LSU 42 Turing Machine that accepts L For any input string w • Compute i , for which w a i • Find Turing machine M i (using the enumerator for Turing Machines) • Simulate M i on input a i • If M i accepts, then accept w End of Proof Prof. Busch - LSU 43 Observation: Turing-Acceptable i i L { a : a L ( M i )} Not Turing-acceptable i i L { a : a L ( M i )} (Thus, L is undecidable) Prof. Busch - LSU 44 Non Turing-Acceptable Turing-Acceptable L L Decidable L? Prof. Busch - LSU 45 Theorem: Proof: If i i L { a : a L ( M i )} is undecidable L is decidable the complement of a decidable language is decidable Then L is decidable However, L is not Turing-Acceptable! Contradiction!!!! Prof. Busch - LSU 46 Not Turing-Acceptable Turing-Acceptable L L Decidable Prof. Busch - LSU 47 Turing acceptable languages and Enumerators Prof. Busch - LSU 48 We will prove: (weak result) • If a language is decidable then there is an enumerator for it (strong result) • A language is Turing-acceptable if and only if there is an enumerator for it Prof. Busch - LSU 49 Theorem: if a language L is decidable then there is an enumerator for it Proof: Let M be the decider for L Use M to build the enumerator for L Prof. Busch - LSU 50 ~ Let M be an enumerator that prints all strings from input alphabet in proper order Example: alphabet is { a , b } a b aa ab ba (proper order) bb aaa aab ...... Prof. Busch - LSU 51 Enumerator for L Repeat: ~ 1. M generates a string w 2. M checks if w L YES: print w to output NO: ignore w This part terminates, because L is decidable Prof. Busch - LSU 52 Enumerator for L ~ M Give me Enumerates all strings of input alphabet next string string w i M If M accepts w i then print w i to output output All strings of Generates all Strings in alphabet L Tests each string if it is accepted by M Prof. Busch - LSU 53 Example: L {b , ab , bb , aaa ,....} ~ M w1 w2 w3 a b aa ab ba bb aaa aab M reject accept reject accept Enumeration Output b ab reject accept accept bb aaa reject Prof. Busch - LSU END OF PROOF 54 Theorem: if language L is Turing-Acceptable then there is an enumerator for it Proof: Let M be the Turing machine that accepts L Use M to build the enumerator for L Prof. Busch - LSU 55 Enumerator for L ~ M M Enumerates all strings of input alphabet in proper order Prof. Busch - LSU Accepts L 56 NAIVE APPROACH Enumerator for L ~ Repeat: M generates a string w M checks if w L YES: print w to output NO: ignore w Problem: If w L machine M Prof. Busch - LSU may loop forever 57 BETTER APPROACH ~ Generates first string w M 1 M ~ M executes first step on w1 Generates second string w 2 M executes first step on w 2 second step on w1 Prof. Busch - LSU 58 ~ M Generates third string M w3 executes first step on w 3 second step on w 2 third step on w1 And so on............ Prof. Busch - LSU 59 String: w1 Step in computation of string w2 w3 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 Prof. Busch - LSU w 4 60 If for any string w i machine M halts in an accepting state then print w i on the output End of Proof Prof. Busch - LSU 61 Theorem: If for language L there is an enumerator then L is Turing-Acceptable Proof: Using the enumerator for L we will build a Turing machine that accepts L Prof. Busch - LSU 62 Input Tape w Turing Machine that accepts L Enumerator for L w wi Give me the next string in the enumeration sequence Compare If same, Accept and Halt Prof. Busch - LSU 63 Turing machine that accepts L For any input string w Loop: • Using the enumerator of L , generate the next string of L • Compare generated string with w If same, accept and exit loop End of Proof Prof. Busch - LSU 64 By combining the last two theorems, we have proven: A language is Turing-Acceptable if and only if there is an enumerator for it Prof. Busch - LSU 65

Descargar
# Languages and Finite Automata