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 12 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 Lecture 05 Turing Machines 1 SC on Amountli Gnlmlmls a Language Automata Grammars and Languages 10212008 The TM Model Climate nk taue warms 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 SC on Miami Gamma him 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 Finiter state control Control unit FSA with state set Q input character in cell under RW head initial state accept statei reiect state u rnarks R end urinput Fixed aipnabet rt u e mi input aipnabet 2 re rui Tape bounded on iett amp unbounded on right c SC on Miami Gamma him Output new state amp overstrike character amp head moves L or R Tape unit lei Imam gram 5 Q Finite length string ot characters With blanks uuuu to right CSC 473 Automata Grammars amp Languages 10212008 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 CSC 473 Automata Grammars amp Languages some TM M Such a TM is an acceptor or recognizerlorL A language L is Turing decidable iff w Recognizey D yes w 12mm e yes me me gt no procedure algorithm Note yes means enters qmm and halls no means enters q and halls reject c SC on Autumn39s awe him Turingdecidable vs Turingrecognizable A language L is Turingrecognizable iff L LM M need noii bulmlghli hall reieciing on some Strings g L for L LM for some TM M that halts on every input string accepts or rejects Such a TM is called a decideror agon rnm 10212008 Example aw R A 3e12 R Cec R A See dcued example 80 halls reieciing uhess accepting slate reached c SC on Autumn39s awe him A transitions not shown go to qm n n n BallL Acceptor for La b c anl bR Cad L Nl L l baa 1 W llllL I I I I I Acceptance Cont Sequence of configurations I0 h Il h I2 h is a computation of length time t Computation 0 F 1 F 2 F 2 How does a TM reject w 3 gnuCOEC1 h C2 inaiighiloop b qow C0 h C qumv a halting amp rejecting coniig c computation qow C0 h C h C2 never this a divergent computeron eliminate as we shall see c SC on Autumn39s awe him NOTE Can make1coincide Wiih nahrig Can eliminate a in lavor 01 b How7 Burthere is no algorithm to detect 0 and hI t is in a ght00p iff 3k 10 F 1t amp 1 JP k a config repeats 1 How does a TM accept w qow C0 h Ca gammy reaches a halting conlig i and no configuration repeats Call CSC 473 Automata Grammars amp Languages 10212008 Acceptance Cont Recognizers and Deciders summary M recognizes S Q S LM M decides S Q o S LM recognizes o Vw E S qo w t 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 to Atom awe Laws A Look Ahead sets Contexttree 3 PDArec B E Flog ul ar 3 Ftntte Automaton rec 39 AW ll ottmg Problem 3Tunngrracogqtzer for D Arm a3 recognizer forE n E C so to Atom awe Laws TM Extensions Church s Thesis Evidence for Church39s Thesis Church s Thesis ChurchTuring Thesis the effectively 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 Lts recogntzeo by a macntne tn one model there ts an algontnm to construct a macntne recogntztng Ltn the second and ytce verse whenever a luncllonfls computed by a macntne tn one model there ts an algontnm to construct a macntne compullngf tn the second and ytce verse l e stmutatton botn otrecttons by a Compiling atgontnm C so to Atom awe Laws CSC 473 Automata Grammars amp Languages 10212008 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 01 cell i I a in cell i01 tape 1 amp head1scanning cell i 5 ontrack1olcelli Tape alphabet is 139 1quotUW head sweeps L to Runtii gt E store k scanned chars in states Sweep R to L a mark changes Sweep L to Rthen Rto L to move head marks End cycle scanning cello 0123 up defB E ABCDEF tizQ xra Q xrxiLR m c 5cm Adam amatth 3 Nondeterministic TM A7tuple M QaZaFa sqoaquqw Transition lunction Transition function 52QgtltF4gt QXFXLR For each may 6 78 provides a set 01 choices 60171qublyD1vqZVb2gtDzv7773qdvdeDd 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 on Adam awe Languages Nondeterministic TM Acceptance we 2I qow aqmwyfor some 0376 1 we LM ltgt 3 sequence of con gurations qdwld t 1i F 12 t10 qmpi7 note the existentaquantilier wlS accepted itthere is some sequence 01 guesses that drive the H Hllal tape Conliguration to an accepting Conliguration A word w is not accepted iii every possibe computation starting With qow 1allS to enter an accepting Conliguration c SC on Adam awe Languages CSC 473 Automata Grammars amp Languages 10212008 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 nieces Computation Tree Chotce seguence gt 0h I2 hlw hiyal c SC to Atom Gamma nieces 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 readrot tiy 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 1m QED c SC to Atom Gamma nieces 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 10212008 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 CSC 473 Automata Grammars amp Languages 10212008 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 CSC 473 Automata Grammars amp Languages 10212008 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 CSC 473 Automata Grammars amp Languages 10212008 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 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 10212008 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 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'