Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 36Slide 38Slide 39Slide 41Slide 42FORMAL LANGUAGES, AUTOMATA, AND COMPUTABILITY15-453* Read chapter 4 of the book for next time * Lecture9x.pptREVIEWA Turing Machine is represented by a 7-tuple T = (Q, Σ, Γ, , q0, qaccept, qreject): Q is a finite set of statesΓ is the tape alphabet, a superset of Σ;   Γq0  Q is the start stateΣ is the input alphabet, where   Σ  : Q  Γ → Q  Γ  {L, R} is the transition funcqaccept  Q is the accept stateqreject  Q is the reject state, and qreject  qacceptCONFIGURATION: (1) tape contents, (2) current state, (3) location of read/write head.11010q700110A TM recognizes a language iff it accepts all and only those strings in the language.A TM decides a language L iff it accepts all strings in L and rejects all strings not in L.A language L is called Turing-recognizable or recursively enumerable iff some TM recognizes L.A language L is called decidable or recursive iff some TM decides L.A language is called Turing-recognizable or recursively enumerable (r.e.) if some TM recognizes it.A language is called decidable or recursive if some TM decides it.Theorem: If A and A are r.e. then A is decidable.Given:a Turing Machine TMA that recognizes A anda Turing Machine TMR that recognizes A, we can build a new machine that decides A.How can we prove this?•Run TMA and TMR in parallel. (Or more precisely, interleave them.)•One of them will eventually recognize the input string.•If TMA recognizes it, then accept.•If TMR recognizes it, then reject.A TM that decides { 0 | n ≥ 0 }High-Level Idea.•Repeatedly divide the number of zeros in half until it becomes an odd number.•If we are left with a single zero, then accept.•Otherwise, reject.2nWe want to accept iff:•the input string consists entirely of zeros, and•the number of zeros is a power of 2.A TM that decides { 0 | n ≥ 0 }1. Sweep from left to right, cross out every other 0.(Divides number in half.)2. If in step 1, the tape had only one 0, accept.3. Else if the tape had an odd number of 0’s, reject.4. Move the head back to the first input symbol.5. Go to step 1.PSEUDOCODE:2nC = {aibjck | k = i×j, and i, j, k ≥ 1}Exampleaaabbbbcccccccccccc3 3×4 = 124C = {aibjck | k = i×j, and i, j, k ≥ 1}High-Level Idea.For each occurrence of a : {For each occurrence of b : {Delete an occurrence of c.}}C = {aibjck | k = i×j, and i, j, k ≥ 1}1. If the input doesn’t match a*b*c*, reject.2. Move the head back to the leftmost symbol.3. Cross off an a, scan to the right until b. Sweep between b’s and c’s, crossing out one of each until all b’s are out. If too few c’s, reject.4. Uncross all the b’s. If there’s another a left, then repeat stage 3.If all a’s are crossed out,Check if all c’s are crossed off.If yes, then accept, else reject.PSEUDOCODE:C = {aibjck | k = i×j, and i, j, k ≥ 1}aabbbccccccxabbbccccccxayyyzzzcccxabbbzzzcccxxyyyzzzzzzTURING-MACHINE VARIANTSTuring machines can be extended in various ways, but so long as a new TM only reads and writes a finite number of symbols in each step, an old TM can still simulate it!Example: Turing machines with multiple tapes.Input comes in on one tape, andother tapes are used for scratch work.MULTITAPE TURING MACHINES : Q  Γk → Q  Γk  {L,R}kFINITE STATE CONTROLTheorem: Every Multitape Turing Machine can be transformed into a single tape Turing MachineFINITE STATE CONTROL0 01FINITE STATE CONTROL0 01###...Theorem: Every Multitape Turing Machine can be transformed into a single tape Turing MachineFINITE STATE CONTROL0 01FINITE STATE CONTROL0 01###...THE CHURCH-TURING THESISAnything that can be computed by algorithm (in our intuitive sense of the term “algorithm”)can be computed by a Turing Machine.We can encode a TM as a string of 0s and 1s0n 1 0m 1 0k 1 0s 1 0t 1 0r 1 0u 1…n statesm tape symbols (first k are input symbols)start stateaccept statereject stateblank symbol( (p, a), (q, b, L) ) = 0p10a10q10b10( (p, a), (q, b, R) ) = 0p10a10q10b11Similarly, we can encode DFAs, NFAs, CFGs, etc. into strings of 0s and 1sADFA = { (B, w) | B is a DFA that accepts string w }ANFA = { (B, w) | B is an NFA that accepts string w }ACFG = { (G, w) | G is a CFG that generates string w }So we can define the following languages:ADFA = { (B, w) | B is a DFA that accepts string w }Theorem: ADFA is decidableProof Idea: Simulate B on wACFG = { (G, w) | G is a CFG that generates string w }Theorem: ACFG is decidableProof Idea: Transform G into Chomsky Normal Form. Try all derivations of length 2|w|-1ANFA = { (B, w) | B is an NFA that accepts string w }Theorem: ANFA is decidableUNDECIDABLE PROBLEMSw  L ?accept rejectTMyesnow  Σ* L is decidable (recursive)w  L ?acceptreject or no outputTMyesnow  Σ* L is semi-decidable (recursively enumerable, Turing-recognizable)Theorem: L is decidable if both L and L are recursively enumerableThere are languages over {0,1} that are not decidable.If we believe the Church-Turing Thesis, this is major: it means there are things that formal computational models inherently cannot do.We can prove this using a counting argument. We will show there is no function from the set of all Turing Machines onto the set of all languages over {0,1}. (Works for any Σ.)Then we will prove something stronger: There are semi-decidable (r.e.) languages that are NOT decidable.Turing MachinesLanguages over {0,1}Let L be any set and 2L be the power set of LTheorem: There is no map from L onto 2LProof: Assume, for a contradiction, that there is an onto map f : L  2LLet S = { x  L | x  f(x) } We constructed S so that, for every elem x in L, the set S differs from f(x):S ≠ f(x) because x  S iff x  f(x)Cantor’s TheoremTheorem: There is no onto function from the positive integers to the real numbers in (0, 1)12345:0.28347279…0.88388384…0.77635284…0.11111111…0.12345678…:Proof: Suppose f is such a function:[ nth digit of r ] =286151 if [ nth digit of f(n) ]  1 0 otherwisef(n)  r for all n ( Here, r = 0.11101... )Let Z+ = {1,2,3,4…}. There exists a bijection between Z+ and Z+  Z+(1,1) (1,2) (1,3) (1,4) (1,5) …(2,1) (2,2) (2,3) (2,4) (2,5)