David Evanshttp://www.cs.virginia.edu/evanscs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 14: Lecture 14: ChurchChurch--Turing ThesisTuring ThesisReminder: PS4 is due TuesdayAlonzo Church (1903-1995)Alan Turing (1912-1954)2Lecture 14: Church-Turing ThesisMenu• Finish computing model for TM• The Most Bogus Sentence• Robustness of TM Model (Church-Turing Thesis)3Lecture 14: Church-Turing ThesisTuring Machine. . .Infinite tape: Γ*Tape head: read current square on tape, write into current square,move one square left or rightFSM: like PDA, except:transitions also include direction (left/right)final accepting and rejecting statesFSM4Lecture 14: Church-Turing ThesisTuring Machine Formal Description. . .FSM7-tuple: (Q, Σ, Γ, δ, q0, qaccept, qreject)Q: finite set of statesΣ: input alphabet (cannot include blank symbol, _)Γ: tape alphabet, includes Σ and _δ: transition function: Q × Γ → Q × Γ × {L, R}q0: start state, q0 ∈ Qqaccept: accepting state, qaccept∈ Qqreject: rejecting state, qreject∈ Q(Sipser’s notation)5Lecture 14: Church-Turing ThesisTuring Machine Computing Model. . .FSMq0input_ _ _ _blanksInitial configuration:x x x x x x xx∈ΣTM Configuration: Γ* × Q × Γ* tape contentsleft of headtape contentshead and rightcurrentFSM state6Lecture 14: Church-Turing ThesisTM Computing Modelδ*: Γ* × Q × Γ* → Γ* × Q × Γ*δ*(L, qaccept, R) → (L, qaccept, R)δ*(L, qreject, R) → (L, qreject, R)The qacceptand qrejectstates are final:7Lecture 14: Church-Turing ThesisTM Computing Modelδ*: Γ* × Q × Γ* → Γ* × Q × Γ*. . .FSMqau, v ∈ Γ*, a, b ∈ Γubvδ*(ua, q, bv) = δ*(uac, qr, v) if δ(q, b) = (qr, c, R)δ*(ua, q, bv) = δ*(u, qr, acv) if δ(q, b) = (qr, c, L)Also: need a rule to cover what happens at left edge of tape8Lecture 14: Church-Turing ThesisTM Computing Modelδ*: Γ* × Q × Γ* → Γ* × Q × Γ*. . .FSMqau, v ∈ Γ*, a, b ∈ Γubvδ*(ua, q, bv) = δ*(uac, qr, v) if δ(q, b) = (qr, c, R)δ*(ua, q, bv) = δ*(u, qr, acv) if δ(q, b) = (qr, c, L)δ*(ε, q, bv) = δ*(ε, qr, cv) if δ(q, b) = (qr, c, L)Do we need a rule for the right edge of the tape?9Lecture 14: Church-Turing ThesisTM Computing Modelδ*: Γ* × Q × Γ* → Γ* × Q × Γ*A string w is in the language of Turing Machine T ifδ*(ε, q0, w) = (α, qaccept,β)A string w is not in the language of Turing Machine T ifδ*(ε, q0, w) = (α, qreject,β)Does this cover all possibilities?10Lecture 14: Church-Turing ThesisTermination• DFAs, DPDAs:– Consume one input symbol each step– Must terminate• NFAs:– Equivalent to DFA: must terminate• Turing Machine:– Can move left and right: no “progress” guarantee11Lecture 14: Church-Turing ThesisPossible Outcomes1. Running TM M on input w eventually leads to qaccept.2. Running TM M on input w eventually leads to qreject.3. Running TM M on input w runs forever (never terminates).12Lecture 14: Church-Turing ThesisRecognizing vs. Deciding• Turing-recognizable: A language L is “Turing-recognizable” if there exists a TM M such that for all strings w:– If w ∈ L eventually M enters qaccept– If w ∉ L either M enters qrejector M never terminates• Turing-decidable: A 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.13Lecture 14: Church-Turing ThesisDecider vs. Recognizer?Deciders alwaysterminate.Recognizers can run forever without deciding.14Lecture 14: Church-Turing ThesisDecidable and Recognizable LanguagesDecidableRecognizableDo we know this picture is right yet?15Lecture 14: Church-Turing ThesisThe Most Bogus Sentence Guesses• “Intuitive notion of algorithms equals Turing machine algorithms.”• “Some of these models are very much like Turing machines, but others are quite different.”• “Think of these as 'virtual' tapes and heads,” on page 149. The quotation marks around virtual imply that the tapes and heads are not virtual, which is false.• “If you feel the need to review nondeterminism, turn to Section 1.2 (page 47).” (By this point, one should have a firm grasp of nondeterminism.) • “Proving an algorithm doesn't exist requires having a clear definition of algorithm.”• “For mathematicians of that period to come to this conclusion [(Hilbert’s 10th Problem’s accepted solution)] with their intuitive concept of algorithm would have been virtually impossible.”I don’t find any of these statement bogus.16Lecture 14: Church-Turing ThesisA bogus sentence (but not the one I had in mind)• “To show that two models are equivalent we simply need to show that we can simulate one by the other.”ABFor set equivalence, need to show A ⊆ B and B ⊆ A.For machine equivalence, need to show A can simulate B and B can simulate A.Winner: David Horres17Lecture 14: Church-Turing ThesisThe Most Bogus Sentence“A Turning machine can do everything a real computer can do.”Winners: Erin Carson, Emily Lam, Ruixin Yang,On the first page!18Lecture 14: Church-Turing ThesisThings Real Computers Can DoGenerate HeatStop a DoorProvide an adequate habitat for fish19Lecture 14: Church-Turing ThesisComputational Thing Most Real Computers Can Do (that Turing Machines can’t)Generate randomness20Lecture 14: Church-Turing ThesisChurch-Turing Thesis21Lecture 14: Church-Turing ThesisAlonzo Church’s “Less Successful”PhD StudentsMartin DavisStephen KleeneSee http://www.genealogy.ams.org/id.php?id=8011 for full listRaymond SmullyanHartley RogersMichael RabinDana ScottJohn Kemeny22Lecture 14: Church-Turing ThesisAlan Turing (1912-1954)• Published On Computable Numbers, with an Application to the Entscheidungsproblem (1936)– Introduced the Halting Problem– Formal model of computation (now known as “Turing Machine”)• Codebreaker at Bletchley Park– Involved in breaking Enigma Cipher• After the war: convicted of homosexuality (then a crime in Britain), committed suicide eating cyanide apple23Lecture 14: Church-Turing Thesis24Lecture 14: Church-Turing ThesisChurch-Turing Thesis• As stated by Kleene:Every effectively calculable function (effectively decidable predicate) is general recursive.“Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it...”Yes, this is circular: everything calculable can be computed by a TM,and we define what is