Description

Lecture 14: Church-Turing Thesis. David Evans http://www.cs.virginia.edu/evans. Alonzo Church (1903-1995). Alan Turing (1912-1954). Reminder: PS4 is due Tuesday. cs302: Theory of Computation University of Virginia Computer Science. Menu. Finish computing model for TM

Transcripts

Address 14: Church-Turing Thesis David Evans http://www.cs.virginia.edu/evans Alonzo Church (1903-1995) Alan Turing (1912-1954) Reminder: PS4 is expected Tuesday cs302: Theory of Computation University of Virginia Computer Science

Menu Finish figuring model for TM The Most Bogus Sentence Robustness of TM Model (Church-Turing Thesis)

Turing Machine . . . FSM Infinite tape: Γ * Tape head: read current square on tape, write into current square, move one square left or right FSM: like PDA, aside from: moves likewise incorporate bearing ( left/right ) last tolerating and dismissing states

Turing Machine Formal Description . . . FSM 7-tuple: ( Q , , Γ , δ , q 0 , q acknowledge , q dismiss ) Q : limited arrangement of states : input letter set (ca exclude clear image, _) Γ : tape letter set, incorporates and _ δ : move work: Q Γ Q Γ { L , R } q 0 : begin state, q 0 q acknowledge : tolerating state, q acknowledge q dismiss : dismissing state, q dismiss Q (Sipser\'s documentation)

Turing Machine Computing Model Initial setup: x . . . x _ spaces input FSM q 0 TM Configuration: Γ * Q Γ * tape substance left of head tape substance head and right current FSM state

TM Computing Model δ *: Γ * Q Γ * Γ * Q Γ * The q acknowledge and q dismiss states are last: δ *( L , q acknowledge , R ) ( L , q acknowledge , R ) δ *( L , q dismiss , R ) ( L , q dismiss , R )

FSM q TM Computing Model δ *: Γ * Q Γ * Γ * Q Γ * u , v Γ *, a , b Γ . . . a b v u δ *( ua , q , bv ) = δ *( uac , q r , v ) if δ ( q , b ) = ( q r , c, R ) δ *( ua , q , bv ) = δ *( u , q r , acv ) if δ ( q , b ) = ( q r , c, L ) Also: require a govern to cover what happens at left edge of tape

TM Computing Model δ *: Γ * Q Γ * Γ * Q Γ * u , v Γ *, a , b Γ . . . a b v u FSM q δ *( ua , q , bv ) = δ *( uac , q r , v ) if δ ( q , b ) = ( q r , c, R ) δ *( ua , q , bv ) = δ *( u , q r , acv ) if δ ( q , b ) = ( q r , c, L ) δ *( ε , q , bv ) = δ *( ε , q r , cv ) if δ ( q , b ) = ( q r , c, L ) Do we require an administer for the right edge of the tape?

TM Computing Model δ *: Γ * Q Γ * Γ * Q Γ * A string w is in the dialect of Turing Machine T if δ * ( ε , q 0 , w ) = ( α , q acknowledge , β ) A string w is not in the dialect of Turing Machine T if δ * ( ε , q 0 , w ) = ( α , q dismiss , β ) Does this cover all conceivable outcomes?

Termination DFAs, DPDAs: Consume one info image every progression Must end NFAs: Equivalent to DFA: must end Turing Machine: Can move left and right: no "advance" assurance

Possible Outcomes Running TM M on information w in the long run prompts q acknowledge . Running TM M on information w inevitably prompts q dismiss . Running TM M on info w runs perpetually (never ends).

Recognizing versus Choosing Turing-unmistakable : A dialect L is "Turing-conspicuous" if there exists a TM M with the end goal that for all strings w : If w L in the long run M enters q acknowledge If w L either M enters q dismiss or M never ends Turing-decidable : A dialect L is "decidable" if there exists a TM M to such an extent that for all strings w : If w L , M enters q acknowledge . On the off chance that w L , M enters q dismiss .

Decider versus Recognizer? Deciders dependably end. Recognizers can run always without choosing.

Decidable and Recognizable Languages Recognizable Decidable Do we know this photo is correct yet?

The Most Bogus Sentence Guesses "Instinctive idea of calculations equivalents Turing machine calculations." "Some of these models are particularly similar to Turing machines, however others are very extraordinary." "Think about these as "virtual" tapes and heads," on page 149. The quotes around virtual suggest that the tapes and heads are not virtual, which is false. "In the event that you want to survey nondeterminism, swing to Section 1.2 (page 47)." (By this point, one ought to have a firm handle of nondeterminism.) "Demonstrating a calculation doesn\'t exist requires having an unmistakable meaning of calculation." "For mathematicians of that period to arrive at this conclusion [(Hilbert\'s tenth Problem\'s acknowledged solution)] with their natural idea of calculation would have been for all intents and purposes inconceivable." I don\'t discover any of these announcement counterfeit.

A false sentence (yet not the one I had as a primary concern) "To demonstrate that two models are comparable we essentially need to demonstrate that we can mimic one by the other." Winner: David Horres B A For set identicalness, need to demonstrate A B and B A. For machine identicalness, need to indicate A can reenact B and B can reproduce A.

The Most Bogus Sentence "A Turning machine can do everything a genuine PC can do." On the principal page! Champs: Erin Carson, Emily Lam, Ruixin Yang,

Things Real Computers Can Do Generate Heat Provide a satisfactory territory for fish Stop a Door

Computational Thing Most Real Computers Can Do (that Turing Machines can\'t) Generate haphazardness

Church-Turing Thesis

Alonzo Church\'s "Less Successful" PhD Students Michael Rabin Hartley Rogers Raymond Smullyan Stephen Kleene Martin Davis John Kemeny Dana Scott See http://www.genealogy.ams.org/id.php?id=8011 for full rundown

Alan Turing (1912-1954) Published On Computable Numbers, with an Application to the Entscheidungsproblem (1936) Introduced the Halting Problem Formal model of calculation (now known as "Turing Machine") Codebreaker at Bletchley Park Involved in breaking Enigma Cipher After the war: indicted homosexuality (then a wrongdoing in Britain), conferred suicide eating cyanide Macintosh

Church-Turing Thesis As expressed by Kleene: Every viably measurable capacity (adequately decidable predicate) is general recursive . "Since an exact numerical meaning of the term adequately measurable (successfully decidable) has been needing, we can take this postulation ... as a meaning of it..." Yes, this is roundabout: everything measurable can be processed by a TM, and we characterize what is measurable as what can be figured by a TM.

Church-Turing Thesis Any mechanical calculation can be performed by a Turing Machine There is a TM-n relating to each processable issue We can display any mechanical PC with a TM The arrangement of dialects that can be chosen by a TM is indistinguishable to the arrangement of dialects that can be chosen by any mechanical registering machine If there is no TM that chooses issue P, there is no calculation that tackles issue P. These announcements are inferred by the Church-Turing postulation

Examples [Last class and PS4] Equivalence of TM and 2-stack deterministic PDA + ε - moves [PS4] Making the tape interminable in both bearings includes no power [Soon] Adding a second tape includes no power [Church] Lambda Calculus is comparable to TM [Chomsky] Unrestricted substitution language structures are equal to TM [Takahara and Yokomori] DNA is in any event as intense as a TM [Hotly Debated] Is the human mind equal to a TM? "Some of these models are particularly similar to Turing machines, yet others are very extraordinary." (not such a false sentence)

Charge Next week: what dialects can\'t be perceived by a TM? Perused Chapter 4: Decidability I don\'t think it has any to a great degree sham sentences, yet in the event that you discover one send it to me…