CS 172: Computability and ComplexityTuring Machines&The Church-Turing HypothesisSanjit A. SeshiaEECS, UC BerkeleyAcknowledgments: L.von Ahn, L. Blum, M. BlumS. A. Seshia 2Notes about this Lecture• This lecture was done on the whiteboard• We include here a synopsis of the notes written on the board, plus the slides used in class– Review this alongside Sections 3.1 and 3.3 of SipserS. A. Seshia 3Notes - 1• Informal description of Turing machine (TM)• What’s different from a DFA– Input tape is infinite– Input head can both READ and WRITE– Input head can move LEFT and RIGHT– Has both ACCEPT and REJECT states and accepts/rejects rightaway (does not need to reach end of input)S. A. Seshia 4Notes - 2• Let L = { w #w | w ∈∈∈∈ {0,1}*}• Give a high-level description of a TM that accepts an input if it is in L, and rejects if not.• See Sipser 3.1 for detailsS. A. Seshia 5Notes - 3• Formal definition of Turing Machine: a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject) • Main points:– Σ ⊂⊂⊂⊂ Γ– Blank symbol is in Γ, but not in Σ– δ : Q ×××× Γ  Q ×××× Γ ×××× {L, R} – Special case: when rd/wr head is at left end of the input tapeS. A. Seshia 6Notes - 4• Configurationu q v -- TM is in state q with uv on the tape andthe head on the first symbol of v Ciyields Cjif δ takes the TM from configCito CjStart, accepting, rejecting configurations• Acceptance: TM accepts w if ∃∃∃∃ sequence of configurations C1, C2, …, Ckwhere1. C1is the start configuration2. Ciyields Ci+1(1 I k-1)3. Ckis an accepting configurationS. A. Seshia 7A TM recognizes a language if it accepts all and only those strings in the languageA TM decides a language if it accepts all strings in the language and rejects all strings not in the languageA language is called Turing-recognizable or recursively enumerable if some TM recognizes itA language is called decidable or recursiveif some TM decides itS. A. Seshia 8A language is called Turing-recognizable or recursively enumerable (r.e.)if some TM recognizes itA language is called decidable or recursiveif some TM decides itrecursivelanguagesr.e. languagesS. A. Seshia 9Design a TM that decides L = { 0 | n ≥ 0 }2nNote: Elements of L encode powers of 2 in UNARY!• Think about how you would decide whether a given number is a power of 2 (in decimal) • Then translate that procedure over to work in UNARY• Main idea: “repeated division by 2”S. A. Seshia 100 → , R → , Rqacceptqreject0→x, Rx→x, R → , Rx→x, R0→0, Lx→x, Lx→x, R → , L → , R0→x, R0→0, R → , Rx→x, R{ 0 | n ≥ 0 }2nq0q1q2q3q4(move back to Left end)(move Right)(mark Left end)(premature end-of-input)S. A. Seshia 11Do this at HomeL = { w#w | w ∈∈∈∈ {0, 1}*} Construct the TM that decides L (check with Sipser Example 3.9)S. A. Seshia 12Church-Turing Hypothesis• Intuitive notion of algorithms = Turing machine algorithms• “Any process which could be naturally called an effective procedure can be realized by a Turing machine”S. A. Seshia 13Hilbert and his 10thProblem• In 1900: Posed 23 “challenge problems” in Mathematics• The 10thproblem:Devise an algorithm to decideif a given polynomial has an integral root.• We now know: This is undecidable!– Needed a definition of “algorithm”, which was given by Church and Turing (independently)S. A. Seshia 14For Next Class• Read Sipser 3.1, 3.2, 3.3– Practice writing down high-level descriptionsof Turing machines, as he