Algebraic Automata Theory
Algebraic Automata Theory MAD 6616
Popular in Course
Popular in Mathematics Discrete
verified elite notetaker
verified elite notetaker
PSY - 0010
verified elite notetaker
verified elite notetaker
verified elite notetaker
This 7 page Class Notes was uploaded by Elizabeth Haley on Wednesday September 23, 2015. The Class Notes belongs to MAD 6616 at University of South Florida taught by Natasa Jonoska in Fall. Since its upload, it has received 46 views. For similar materials see /class/212665/mad-6616-university-of-south-florida in Mathematics Discrete at University of South Florida.
Reviews for Algebraic Automata Theory
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: 09/23/15
March 31 2005 MAD 6616 ALGEBRAIC AUTOMATA THEORY NOTES 8 TURING MACHINES AND THE HALTING PROBLEM INSTRUCTOR NATASA JONOS KA 1 TURING MACHINES Up till now our discussions were concentrated on FSA or the so called nite memory machines We know the language of all binary strings divisible by 3 is regular Similarly we can construct a FSA that accepts binary strings that are divisible by p where p is any prime number In all these cases the states play the role of a memory Each state remembers what is the remainder of the number read so far But if we make an attempt to construct a FSA accepting all binary strings which are prime numbers we would need potentially in nite number of states ie in nite memory since for every prime number p and every number n such that p2 g n we should check whether n is divisible by p Clearly this can not be done by a FSA For that matter we enter the world of Turing machines Again we allow only nite number of internal states but we are able to acquire the in nite memory by allowing beside the in nite tape for writing the input from which our machine can read also our machine to write symbols on the tape and to move forward and backward Let A be a nite set of symbols We assume that B is not an element of A and we will use B to denote the blank symbol on the tape The symbols R and L will be used to denote the action of the machine to move right and left respectively De nition 11 Turing Machine A deterministic Turing machine is a quadruple M Q qoT 6 where Q is a nite set of states go 6 Q is the initial state T Q Q is the set of terminal states and 6 Q X A U gt A U B U RL X Q is a partial function of transitions lf 6qa where q E Q and 04 E A U B is not de ned we say that the Turing machine TM stops in state q scanning the symbol a We will assume that before each computation the TM is in a starting con guration that is the head scans the rst blank symbol on the left of the leftmost symbol of the input string and the TM is in state qo BBB Ba1a2akBBBB qo De nition 12 con guration A con guration ofa TM is a word in set BAQAB where A A U The initial con guration is the word quBa1akB where ai E A We call x a1a2 ak input of the TM Each con guration represents the whole content of the tape Any cells of the tape that are before the rst blank in the con guration and after the last blank are blank as well 1 De nition 13 con guration change We write wu E Aabb E A 1 BwaqbwB F Bwaq bwB if 6qb bq 2 BwaqbwB F Bwabq wB if 6qb Rq 3 BwaqbwB F BwqabwB if 6qb L q We will write l for the transitive and reflexive closure of F The borderline con guration changes are de ned as 39 BqawB F BqBawB if 6qa L q Bqu F BquB if 6qB Rq We de ne TM s by specifying the function 6 either by a table or by listing the fourtuples determined by it For example both of the following speci cations of 6 de ne the same TM 1 2 5q07BR7q1 qoBqu 5q071 L43 qo 1Lq3 5q17B17q2 qulqz 5q171R7q1 qi 13 5q27B17q0 qulqo 5q271 quz q2 13 6q3BBl quBl 5q371 L7q qs 1Lq3 In the above example Q q0q1q2 qg l and T The alphabet is A Each quadruple oz anq ie 6q a X q is called a move of M There are three different moves 1 q cc q if M is in state q and scans c E A U B then write c and change to state q 2 q ch in M is in state q and scans c E A U B then move to the right and change to state q 3 q ch if M is in state q and scans c E A U B then move to the left and change to state q We say that M is in halting position if it is in state q and scanning symbol c but 6q c is not de ned A sequence of moves a0a1a2 is a computation of the TM M if 040 qoBXq for X E A U B RL q E Q and for all i gt 0 when oz chq then Oil1 has fourth symbol equal to q and the symbol currently scanned on the tape is c c E A U A computation may be nite or in nite A computation 040 3 is nite if M is in halting position after the move 0 Let f B a A be a partial function We say that a TM M computes f strictly if the alphabet of M is a subset of B and there is a nite computation for every input on which 1 is de ned such that after the initial con guration Bx By T the nal con guration has the form T qO q where fz y qi E T and y contains no blanks ie BqOBmB l Bq fzB Example 14 The above example computes m 2 where A 1 and m is written in unary base 1 notation Exercise 15 Construct a TM which computes strictly the following functions on natural numbers where the natural number m is represented unary as 1 1 95 y 2 990 y where Way m 7 y zfz gt y and WW 0 zfz S y 3 m y where m and y are written in unary notation with the input BmBy We say that a TM M accepts a word w if there is a nite computation 040 0 of M with input w and 04k q cX q where q E T The language recognized by the TM M is the set of words w that are accepted by M and is denoted by NOTE It is signi cant to note that a TM halts whenever the input is accepted however for words that are not accepted the TM may halt in a non terminal state or it may never halt Example 16 The following table determines a TM which accepts the language anbnl n 2 1 over the input alphabet A a b q0 q1 q2 q3 q4 qs B qu B l a W2 3 Lq4 b 5 W4 04 3 Rq1 3 3 3 Lq4 3 The terminal state of this TM is X It is easy to see how the computation is executed The state ql changes one a into 04 and moves to state qg The state qg searches for the corresponding b Then qg changes to qg and changes b into 3 Then M changes state to q4 and 7goes back7 to search for the next a If there are more as then b s then M halts in state qg If there are as after b s then M halts either in state qg or in state q5 If there are more b s following a s then M halts in state q5 The only accepting strings are those with number of as followed by the same number of b s Try to nd the computation sequences of M with input strings aabb aab aaba b abb Proposition 17 Euery regular language is recognized by a turing machine Proof Note that for every DFA we can nd an equivalent TM by de ning the transition function 6 in TM to be 6qa R Aq a where A is the transition function of the DFA So every regular language is accepted by a TM By the example above we can see that the class of languages accepted by TM s is greater than the class of regular languages De nition 18 lstape TM A Turing machine with k tapes is afourtuple M Q qo T 6 where Qq0T are the same as for TM and 6 is a function 6 Q x AK AUBR Lk X The initial con guration in a k tape TM is always written on the rst tape in the standard initial con guration way The notion of recognizing a word language by a TM is de ned accordingly Observation 19 For euery k 2 1 the class of languages recognized by k tape TM is the same as the class of languages recognized by a single tape TM Proof sketch Assume that M is a k tape TM We construct a single tape TM M over al phabet Ak with set of states Q Qk with initial state q0q0 and terminal states T t t lt E T The transitions are de ned by function 6 in the following way For each transition 6q a1 ak Xl Xk q we have a sequence of transitions 6q q q 04 ak X1a2 ak qq q 5q 7qq7X1a2ak X17X2w7ak7q q qq 5q 7q qu X17X2 7Xk717ak X17X2 Xk GAG761 q Excersise prove that the two TM are equivalent D 2 RECURSIVELY ENUMERABLE LANGUAGES AND THE HALTING PROBLEM De nition 21 recursively enumerable A language L Q A is called recursiuely enu merable if there is a Turing machine M such that L De nition 22 recursive A language L Q A is recursiue if there is a Turing machine M that halts on euery input w E 14 and L Clearly every recursive set is recursively enumerable re Proposition 23 Every regular language is recursive Proof By the note above for every DFA there is an equivalent TM recognizing the same language Since every DFA halts on every input so does the corresponding TM Proposition 24 The complement of a recursiue language is recursive Proof Let L be a recursive language and let M be a TM such that L We can construct a TM M which recognizes the complement LC in the following way Let t be a state which is not in the set of states of M The set of terminal states of M is t and the transition function is de ned in the following way If 6q a is not de ned and q is not a terminal state of M we de ne 6 q a a t in M For every other transition 6qa 6 qa Then M is a TM which halts on every input and such that L0 LM exercise D Proposition 25 UL and L0 are both re then L and hence LC is recursive Proof Let M and M0 be TM that recognize L and LC respectively Let w E A Since w is precisely in one of L or L0 we know that precisely one of M or M0 halts on input w We can construct a TM M which simulates computations ofM and M0 at the same time We imagine that we have two tapes and two heads for scanning symbols for each tape respectively The input alphabet will be extended by A x A such that we say that M scans a b if the head scans a on the rst tape and scans the symbol 1 on the second tape The set of states of M is Q x Q0 U 31 32 U Q x do we assume that Q O Q0 0 The initial state is go q The state qqc is terminal iff q E T or go do The states 31 and 82 are such that 31 accepts the input from the rst tape and writes it on the second and 82 returns M in the beginning position with both tapes containing the same input and ready to simulate the computations of M and MC simultaneously The state dc checks whether MC halts in a nonterminal state in which case the input is a word in L The transition function 5 of M is de ned as follows I rewrite input on both tapes 6q07 q87 B7 B R7 R7 817 6317 0 7 B av a7 817 6317 0 7 1 R7 R7 817 for all a 6 end of input 531 B B L L 32 ll return to the start position with same input on both tapes 582a7a Llevszlv 8827B7B RvR7q17qf39 lll simulate the computation ofM and M0 on both tapes Mme 550 01710 61 600 if 661 E MN and W c no me 5q7q07 550 777 BL Wch if 5amp5 774 and 50qc 50 is not de ned and qc Tc Exercise M halts on every input and w E LM iff w E L D Corollary 26 IfL is re but not recursiue then LC is not re Note that the proof of Proposition 25 intuitively uses two tapes7 but the same simulation can be made on only one tape over the alphabet of fourtuples where the rst element is a marker pointing to the element scanned by the rst head7 and the third element is a marker pointing to the element scanned by the second head The second and the fourth elements are symbols on the rst and second tape respectively In general7 having a Turing machine with n tapes is equivalent to having one tape Turing machine over an alphabet of 2n tuples7 such that the odd symbols represent markers pointing to the symbols read by each of the heads of the n tapes and the even symbols represent are the symbols of the tapes De nition 27 decidable We say that the question whether w E L Q A is decidable ifL is recursiue A partial function f A a B is computable if there is a TM that halts on every input and on input z E A produces output x 6 B So equivalently7 for L Q A we say that it is decidable whether w E L for each w E A if and only if the function f A a 01 de ned with 1 if w E L Hw T 0 otherwise is computable This problem is called membership problem for L So the membership problem for L is not decidable if complement of L is not re A usual technique of showing that a problem is not decidable is to show7 by diagonalization7 that its complement is not re We will illustrate this on the halting problem for TM ie we will show that the halting problem for TM is not decidable7 or in other words7 the membership problem for the language LM w lM halts on input w is not decidable Note that 1 every TM is equivalent to a TM with only one terminal state 2 if A is the input alphabet of a TM and f A a a7 b is an injective morphism7 then fA is a code7 so every word in A can be encoded in alphabet a7 b in a unique way7 and the TM is equivalent to a TM over alphabet a7 b First we construct the universal TM We assume that a TM M has alphabet a7b and Q q1 qn1l is the set of states with ql being the initial state and l being the unique terminal state We write 0102 03 for a7 b7 B respectively and X17 X27 X37 X47 X5 for a7 b7 B7 B7 L respectively A move quj Xk q will be written by 01107 10k10l Since every TM is given by a set of moves7 we encode a TM in the follo ng way 111code of move111code of move211 11code of movemlll Clearly there is more than one code for each TM since the order of the moves determining TM is not important Note also that the set 3M x is a code of M is a pre x code Let w be a binary string Since the binary word encoding M is a natural number the set of TM is countable and we can order all TM in a sequence M1M2 In the same way we can order 101102 where w is the binary string equal to the code of Mi Consider I I 7 0 if Mi accepts wa Pol17107 1 otherwise Now consider the language K Q 0 1 de ned in the following way K ltIgtM wi 1 Proposition 28 K is not 726 Proof Assume that K is re Then there is a TM M M for some i such that K Consider wi lf wi E K then ltIgtMiwi 0 which implies wi is not in K lf wi K then ltIgtMi wi 1 and by de nition of K wi E K Contradiction in both casesll B Let w be any binary string A concatenation of a code for a TM M and w will be denoted with M w De ne U MwlM is a TM and M accepts w U is called the universal language The Halting Problem Given a TM M and a word w is M w in U le is w accepted by M By the de nition the halting problem is decidable iff the language U is recursive We answer that question with the following Proposition 29 U is not recursz39ue Proof sketch If U were recursive then there is a TM M that halts on every input and recognizes U Then M halts on every input Mlwi here we take that w is the binary code of M as above and it accepts Miwi iff Mi accepts wi We alter M to M which only acceptable input is Miwi It is simple to check such input since the set of strings L ml Mz is a code of M is recursive exercise We can use two tapes If the rst tape has input Mi wi we can rewrite on the second tape Mi wiR and by simultaneous reading on both tapes we can check whether M w Mi wiR Then M halts on every input and accepts the language Kc So K0 is recursive which is a contradiction to the Propositions 24 and 28 Essentially the TM M consists of a sequence of three consecutive machines M1 check whether z is a pre x of input of M that is a code for some TM M2 check whether the input satis es M w Miwi M3 M D We have seen that there are recursive and non re languages But is there a distinction between the class of recursive languages and the class of re languages This question is answered with the following proposition Proposition 210 The language U is 726 Proof sketch We will construct a threetape TM M which will accept the string M w iff M accepts w On the rst tape we write the inuput Mw and we check whether this is a right input ie we check whether the string has a code of a TM as a pre x The second tape will play the role of the tape of M and the third tape will keep truck of the current state of M that has to be executed a After checking that the input is correct we rewrite the string w on the second tape that is the string immediately after the second 111 Then we initialize the third tape to hold 0 which is the code of the rst state ql b Check whether the third tape has the code 0 which is the code of the nal state 1 If the third tape has 0 then halt and accept the string c Let c 1 2 3 be the symbol currently scanned on the second tape If the third tape has 07 then search the rst tape for a factor 11071101101110l in between the rst two strings 111 If such a factor does not exist then halt and reject lf 11071101101110l is found write ck if 1 g k g 3 on the second tape or move to the right left on the second tape if k 4 ie k 5 Write Ol on the third tape It is quite clear that M halts accepts with input w iff M halts accepts on input Mw and M doesn t halt on input w iff M doesn t halt on input M w E The previous proposition just es the name of U the universal language of the universal Turing machine constructed in the proof Now we have examples of recursive languages for example any regular language examples of re which are not recursive the universal language U by propositions 210 and non re languages the language K by Propositon 28 We say that P is a property of re languages if P is a set of re languages for example regular languages nite languages in nite languages We say that L has a property P if L E P We say that P is trivial if P Q or if P all re sets Proposition 211 Rices Theorem Every non trivial property of re languages is unde cidable So it is undecidible whether a re language is a empty b nite c regular d recursive
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'