Class Note for C SC 473 at UA
Popular in Course
Popular in Department
This 11 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 24 views.
Reviews for Class Note for C SC 473 at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CSC 473 Automata Grammars amp Languages Theory of Computation Lecture 05 Turing Machines 1 sc m Amunml Gnlmlmls a Language 10312007 The TM Model Cinemas nk taue Haunts b1 m algorithms Arbitrary definition choice but standard Easy comparison with other models RAM etc Finitely describable just a formatted string FSA for each TM trivial C so on Autumn Gamma Laws Model of effectively computable procedurequot including all Primitive as possible math simplicity amp constructions 1 machine 1 procedure no stored program different Computes in discrete steps moves each step physically Simple complexity measures stepstime cesspace The TM Model Fll llte39 state control Control unit FSA with state set Q lrlput character lrl cell urlder RW head lnltlal state accept state relect state u marks R end urtnput FlXed alphabet rt u e r lrlput alphabet 2 re u Tape bounded on lett amp unbounded orl rlght C so on Autumn Gamma Laws Output rlew state amp overstrlke character amp head moves L or Ft Tape unit 9m Imam qreect E Q Flnlte length strlng ot characters wtth blanks uuuu to rlght Lecture 03 CSC 473 Automata Grammars amp Languages 10312007 TM Examples input and RM head left adjusted at start TM to scan R over nonblanks to halt over first blank MM 01 DR an 1 t R qme rr c SC on Atom came Laws TM Definition 1 tape deterministic TM A7tuple M Q32an sqosqquw Q ttmte set ot states lquotlimle tape alphabet blank Lttnpuf alphabet Egret Hi Transtttontunotton Qgtlt1quotgtQgtlt1quotgtltLR tntttat state 1105 Q haltacceptretect states qw tqwme Q Configuration Cuaqbv MVE 139 qE Q alas 1quot 1step yields relation P between configurations uaqby F uacq39v ltgt 5qbq39tct R WIFWIIU F uacq39 ltgt 5019112411 uaqbv l7 uq39aw ltgt 5qbq39cL Note Below says you mm move leltlrom tettmost cell although you don t really move leltl This conyentton makes accept reset the only haltstates 917v r q39cv w 5qbqcL qbv r Cq39v w 5qbqcR c SC on Atom came Laws Acceptance Move relation multistep F wef k is aoceptedbyMcgt qow P uqmwv Language recognized by M LMlWET3M7Vqu P quot awV TMrecognimble language a set S such that ETM M SLM Configuration I is hal ng EC C F C Nowhere to moyeztrom dellmllol iy only 2 ways to halt A reteottng or aooepttng configuration qumv qu v A configuration for which no move is defined Initial configuration qow we 2 Any halting configuration thhoutqmep ts nonaooeptng Can aways force nonracceptng hetng configs to be rejecting Fortmdefned Jqa y ustadd transitions to qwm c 5cm MW cement Lecture 03 2 CSC 473 Automata Grammars amp Languages 10312007 Turingdecidable vs Turingrecognizable A language L is Turingrecognizable iff L LM for some TM M M need riol bulmighli nali reieciing on some strings E L Such a TM is an acceptor or recognizerlorL A language L is Turing decidable iff L LM for some TM M that halts on every input string accepts or rejects Such a TM is called a decideror agori tnm w Recognizey D yes w 12mm e yes me me gt no procedure quotaigoriinmquot Note yes means enters qmm and nails no means enters q and nails reject cmumamuws Example if aw R A Bee R Cec R A I I I I I Nl L l bah 1 W llllL A transitions not snown go to qm See doued example 80 halls reieciing uness accepting siaie reacned c SCMBAmmvau amatth 5 Acceptance Cont Sequence of configurations I0 l7 II gt7 I2 l7 is a computation of length time t Computation Io F 1 F 2 F is in a ghtoopiff 31d0 l k amp 1k JP k a config repeats 1 How does a TM accept w qow C0 n Cd uqamprv 2 How does a TM reject w k1 t 3 govtCOEC1 gt7 C2 inaiigniloop b qow C0 n C qumv a nailing amp rejecting coniig c computation qow CO e C gt7 C2 never reaches a halting conlig i and no configuration repeats Call this a divergent computation NOTE Cari make i coincide Wiin naiting Cari eiiminaie a in lavor oi b How7 Butthere is no algorithm to detect 0 and eliminate as we shall see c SCMBAmmvau amatth 9 Lecture 03 3 CSC 473 Automata Grammars amp Languages 10312007 Acceptance Cont Recognizers and Deciders summary M recognizes S Q S LM M decides S Q o S LM recognizes o thz S qo w b qumv rejects amp halts MlS called a decideror egotrhm S is a Turingrecognizable language if there is some TM that recognizes it S is a Decidable language iff there is some TM that decides it NOTE every TM recognizes some language but only special TMs ones that halt for every input decide the language they recognize C so m We awe Laws A Look Ahead use sets 9quot 0 e c 3 Deciderto anxwer xs C 7 Contextlree 3 PDArec B Regular A 3 Fmtte Automaton r 3Tunngrracogqtzer for D ATM 39A H it P bl W 3 mg m m irecogmzerforE u E C so m We awe Laws TM Extensions Church s Thesis Evidence for Church39s Thesis Church s Thesis ChurchTuring Thesis the effectiver computable functions are those characterized by one the standard formalismsquot such as the TM Convenience of having alternate models Two models of computation are equivalent cgt whenever a language Lrs recognrzeo by a macnrne in one model there is an algontnm to construct a macntne recogntztng Lll l the second and vrce verse whenever a luncttonfts computed by a macnrne in one model there is an algontnm to construct a macntne compullngf W the second and vrce verse l e Srmutatron botn orrectrons by a compiling atgontnm C so m We awe Laws Lecture 03 CSC 473 Automata Grammars amp Languages 10312007 TM Extensions ktape TM Tapes simulated by one tape with k tracks amp soltware heads a in cell iol tape 1 a on track 1 ol cell i a in cell iottape 1 a head 1 scanning cell a on track 1 o1 celli Tape alphabetis 139 1quotUW head sweeps L to Runtii gt E storekscanned chars in states Sweep R to L a mark 0 1 Z 3 changes Sweep L to Rthen R10 L to move an head marks End cycle scanning cello D 1 z 3 52erqdqgtlt gt Qxf XlLJZV a b d e f B E ABCDEF 5Q gtltl39 gt Q xrxiLR m c 5cm Atom amatth 3 Nondeterministic TM A7tuple M QaZaFa sqoaqwoqw Transition lunction Transition function 52QgtltF4gt QXFXLR For each may 6 78 provides a set 01 choices 60111qublyD1v427b2vD2vryqdvbdgtDdl Acceptance means sequence of configurations leads to a configuration with state qampt o No use for reject state rejection is noth entering a state 0 Rejection means no posleve chain ofcon gula 39ons leads to one with qmepr o No next move is possible can have 5qa Q c SC or Atom awe Laws Nondeterministic TM Acceptance we 2I qow aqmwyfor some 0376 1 we LM lt23 sequence ofcon gurations IoWIo F I F 12 F1aqmp7 note the existentaquantilier wlS accepted itthere is some sequence o1 guesses that drive the H Hllal tape Conliguration to an accepting Conliguration A word w is not accepted ill every possibe computation starting With qow lallS to enter an accepting Conliguration c SC or Atom awe Laws Lecture 03 5 CSC 473 Automata Grammars amp Languages 10312007 Choice Numbers Choices for a given state and symbol 50mPiibiiDiiPzibziDzi awnibniD i 1 2 It For each 4 and a assign each choice in 314141 a number For each machine there is some largest number of choices for some transition call itb Strings over 123 b can be interpreted as deterministic directions for which choice to make from each configuration I qa c SC to Atom Gamma Laws Computation Tree ehoice seguence gt 0h I2 hlw hiyal c SC to Atom Gamma Laws NTM Equivalent to TM Theorem 316 IfL is accepted by an NTM N there is a DTM D constructable by algorithm that accepts L Proot simutate att possipte computations on Ntor att possipte choice strings and hatt it a sequence ot choices is touno that teaos to an accepting contiguration D has stapes readrot39tiy inputi Worktape simutating that otN and an enumeration tape 0n the iatteri enumerate att choice sequences in texicographic order L1 b1112 1b 2122 2b 111112 Main cycte generate the next choice seq 6 on the enum Tape Use this sequence to drtve computation otNtor a totat ot tct steps tt an accepting contiguration is reached D accepts and hatts tt the computation hatts retecttt tgi move to the next main cycie atter ctearing the Worktape Otherwtse move to the next main cycie atter ici steps iterate the main cycte Whtie an accepting contiguration has not been touno tt an accepting 6 exists D Wtii eventuaiiy tino it tt none exists the input Wtii not be accepted 80 LD rm QED c SC to Atom Gamma Laws Lecture 03 6 CSC 473 Automata Grammars amp Languages c SC on We awe Laws The Universal TM Any hardware TM M can be encoded as a formatted string software Encoding details M gt gtMgt below The UTM Ureads M w and simulates the action of M on w The UTM Uis one fixed finite machine capable of simulating any TM an interpreter For example Ureads um1M and gives the same result as for input MM We shall see that whenever universality exists unsolvability is an inevitable consequence 10312007 c SC on We awe Laws Canonical Encoding of TM M Let MQx2x1quotx5xqmqmp Qlqmq1x will Encode over 9 symbol alphabet l01 ob39ect in M encoding in M 1gt q 6q I biVli qo 010 0 11W q 601 1 501 a that D L 1R 2 Cqx ca CqkcalD 6 sequence of rsepatamd Setuples M 422 F iqmqmm sequence of separated substrings M M istring c SC on We awe Laws Canonical Encoding of TM Mcont Mistring isaword over 01117111111 Final encoding M is ASCII binary of that string Notational convention an encodingltMgt of a TM M isquot the binary representation of a natural number number M is called the Citadel number of M Conversely if e is a natural number Me is the TM with that Go39del number If e is a syntactically invalid code Me is bydefinition a TM that halts and prints 0 on every input Lecture 03 CSC 473 Automata Grammars amp Languages 10312007 UTM Construction Use 4 tapes input Uw program tape state tape w amp worktape ofM being simulated 1 Parse input copying to program tape If invalid put 0 on worktape and halt Else copy w to worktape amp put 0 on state tape simulating state0 2 While the state tape 1 do ti it the state tape contatns Cql count over to tuples tor that state m program M Use the character a under scan on the worktape 01 to scan to the correct 5nluple5q75a75qk75l77D a Overwnte the scanned character cm on the worktape by 4b and move the head direction D on the worktape at Copy the new state stnng 6qk trom the program tape to the state tape atter erasing the previous state stnng C so on New Gamma Laws UTM Construction 4 tapes M llw input to U tape to hold tape to hold state of M and worktape of M readronly tnput readronly program 01002 022227 state ot M worktape ot M C so on New Gamma Laws 2 State 3 Tape Symbol UTM httpwwwwolframsciencecomprizestm23 C so on New Gamma Laws Lecture 03 8 CSC 473 Automata Grammars amp Languages 10312007 TM Extensions Enumerators TM that prints out a list of strings separated by blanks Starts with an empty tape Defines a set of strings language Strings need not be unique repeated strings allowed Strings can be enumerated in no particular order Usuallydoes not halt runs on forever printing strings Finite or not an enumerator Edefines a set of strings Theorem 321 A language is Turingrecognizable iff it is enumerable by some enumerator Pf Must show 2 directions a language defined by an enumerator has a Turing recognizer and any TM recognizable language has an enumerator We will show there are algorithms for going in both directions c SC on Autumn Gamma Laws TM Extensions Enumerators cont d Enumerator gt Recggnizer LetA LE where E is an enumerator Using the code for E construct a recognizer M as follows M On input w t Conttnue runntng Eand output the next stnng r Pause E Compare r to w a it w 5 hell and accept Otnerwse ccnttnue at step t quot l Machine Mrecognizesjust those stringsA thatE enumerates c SC on Autumn Gamma Laws TM Extensions Enumerators cont d Recggnizer gt Enumerator LetA LM where M is a TM recognizer Using the code for M construct an enumerator E as follows Let SP 52 53 be a list of all strings in 2 ltis easy to build a routine that generates strings in lexical order 8 a b aa ah ha bb aaa E Ignore the input t lorz1t0mdo a Ruanorzsteps on each ct the tnputs 1 52 s a it any computatton sequence accepts an tnput s pnnt if out gt t E eventually enumerates every string M accepts Technique interleaving computationsquot c SC on Autumn Gamma Laws Lecture 03 9 CSC 473 Automata Grammars amp Languages 10312007 What is Effectiver Computable Early 1900s logicians sought a universal algorithm that would enable Automatic TheoremProvingquot Worked to find deciders to tell whether formulaslike Vy Pty a 0 lt gt 3thx a Q are logically true via a mechanical method Decision Problem for First Order Logic whether multivariable polynomial equations like 5X1y 10X 20 0 have integer solutions Hilbert39s 10 h Problem Want to decide any such questions by computation39 that is effectively performable39 with a finite number of computation steps Had no idea there were undecidable problems c so no Avatar came Laws Effectiver Computable cont d But what did effectively computablequot mean An intuitive notion you know it when you see it39 There were no programming languages or computers Each author had to pick a mechanically performablequot method to illustrate what was computable 1936 Alan Turing proposed Turing Machines 1936 Alonzo Church proposed ivcalculus 2 remarkable outcomes Both detinition methods proved to be equivalent agreed on what was a computable set or tunction Once a method was picked it was discovered that there must be undecdabe sets Eventually many more methods proved equivalent c 5cm Avatar swam 25 Cnmpubbility 7112 Evidence for Cl ll l ll Turing s Titan39s Godei amp Herbrand 1934 Kleene 1935 1 General Recursive Functions Markov 1954 Markov Algorithms Turing 1936 Church1936 TM Haicuius Phrasershucmre Type 0 Grammar1959 Any programming Shepherdson a Sturgis 1963 language to date Register MachinesRAM Post 1943 Eigot amp Robinson 1964 Canonical Systems RASPs For each pair otrepresentations there is a uniform algorithm commer for transsting one to the other c SCMBAmmuu swam 3 Lecture 03 10 CSC 473 Automata Grammars amp Languages Church Turing Thesis Thesis OED A proposition laid down or stated esp as a theme to be discussed and moved or to be maintained against attack a statement asserllol i tenet mmrve concept Turingrmechine ofegorithm egorithm ntuitive concept RAM ofegorirhm egorithm ntuitive concept Markov ofegorirhm egorithm All methods also agree on what is a decidable setquot and what is a recognizable setquot c sconAmnmu Gammath 10312007 Effectiver Computable cont d Both decision problems Hilberts 10 15 Order Predicate Calculus eventually shown to be undecidable In our terminology a decision problem is translated into a language The problem is decidable iff the language has a Turing decider None of the following languages have a decider they are undecidable languages Amm pl 17 is a multiivariable polynomial such that p 0 has an integer solution APC el e is a true formula theorem of the 1st order predicate calculus ATM ltMwgtM is aTM and we LM This last is called the Hal ng or Membership Problem c so on Autumn39s swat Laws Lecture 03 11
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'