10 Chapter TURING MACHINES Teneo al 10.1. introduction 10.2. Turing Machine as Physical Computing Device 10.3. Formal Delinition of Turing Machine 10.4. Instantaneous Description 10.5. Transition Diagram 10.6. Turing Thesis 10.7. Turing Machine for Computing Functions 10.8. Turing Machine as Language Acceptors 10.9. Combining Turing Machine 10.10. Exensien of Turing Machine 10.11. Church's Thesis 10.12. Universal Turing Machines 10.13. The Halting valom 10.14, Undecidabilty/Decidabilty 10.15. Pushdown Automata with Two Stacks 10.1. INTRODUCTION We have seen that neither deterministic finite automata nor pushdown automata can be regarded as truly general models for computers, since they are not capable of recognising even such simple languages as {a"b"c"/n >= 0). Turing machine is the next model of computation under machine based approach and context-sensitive or phrase-structure grammar in the corresponding model under grammatical approach. In the 1930's (before advent of digital computers) several mathematicians began to think about what it means to be able to compute a function. Alenzo- Church and Alan turing independently arrived at equivalent conclusion. As we might phrase their common definition now. “A function is computable if it can be computed by a Turing Machine”. A Turing machine is a very simple machine, but logically speaking, has all the power of any digital computer. The Turing Machine (TM) is an abstract model created by Alan Turing (1912-1954), who was mathematician by trade and the inspiration behind the computers as we know them today. The impact of the turing machine and the theories around them were revolutionary in his time. Turing machine were used to show significant results since the foundation of mathematics aad are also highly relevant to computer science. Turing introduced Turing Machine to demonstrate the indecision of the halting problem. 10.2. TURING MACHINE AS PHYSICAL COMPUTING DEVICE In order to help our understanding of the subject-matter of TMs, we ca" visualize a TM as a physical computing devi f i ig device that dasa diagram as shown in Fig. 10.1 below : an eee 200— a LL 201 Minite tape Hoadwrite, head Finito control 4 systom Turing machin Fig. 10.1, According to this view of TM, it co: (A Tape, with an end on the left but infinite on the right sid is divided into squares or cells, with each cell c ' tape symbols including the blank symbol #. At finitely many cells of the tape that can cont: tape symbols is denoted by Tr. As the very first step in the sequence of operations of a TM, the input, as a finite sequence of input symbols is placed in the left-most cells of the tape. The set of the input symbols denoted by ¥, does not contain the blank symbol #. However, during operation of a TM, a cell may contain a tape symbol which ‘is not necessarily an input symbol. (ii) A Finite Control, which can be in any one of the finite number of states. The states in TM can be divided in three categories that (a) The initial state, the state of the control just at the time when TM starts its operations. The initial state is denoted by qo. (b) The Halt state, which is the state in which TM stops all further operations. The halt sate is generally denoted by ‘h’. The halt state is distinct from the initial state. Thus a TM has atleast two states. (c) Other intermediate states. (iii) A tape head is always stationed at one of the tape cells and provides communication for interaction between the tape and the finite control. The ead can read or scan the symbol in the cell under it. The symbol is ‘ommunicated to the finite control. The control taking into consideration the mbol and its current state decides for further course of action including : (a) The change of the symbol in the cell being scanned and/or (b) Change of its state and/or ‘i (© Moving the head to the left or to the right. The control may decide Not to move the head. a ; (iv) The course of action is called a move of the Turing Machine. In other ‘ords, the move is a function of current state of the control and the tape symbol its of he tape ‘apable of holding one of the any time, there can be only ain non-blank symbols. The set of202 THEORY OF AUTOMATA AND COMPUTATION being scanned. The change of symbol in the cell being scanned is called writing of the cell by the head. Initially, the Iwad scans the right-most cell of the tape. 10.3. FORMAL DEFINITION OF TURING MACHINE [RTU 2002, 2001) A Turing machine is a sixtape of the form ™ = (25,0, 8 4) where (i) Q is the finite set of states. (ii) ¥ is the finite set of non-blank information symbols, (iii) T is the set of tape symbols, including the blank symbol #. (iv) 8 is the next-move partial function from (QxT> (Q«I {L, R, Ni) where f = ¥ u #, ‘L’ denotes the tape Head moves to the left adjacent cell, ‘R’ denotes tape Head moves to the right adjacent cell and ‘N’ denotes Head does not move, that is continuous scanning the same cell. () qo € Q, is the initial state. (vi) h € Q is the ‘Halt State’, in which the machine stops any further activity. Let us discuss some move of the turing machine; (i) if q€ Q ce SZ and 8, c) = (qy b R), then Turing Machine (Tm) when in state q and currently scanning symbol c, will enter in state q, and move towards right adjacent cell after replacing ‘c’ with ‘b’ (ii) 8(qy, 2) = (gy, b, L) means that at present Tm is in state q, and scanning the symbol a, will enter in state q, and write ‘b’ in place of ‘a’ and move towards left adjacent cell. (iii) (gy, ¥) = (Gy, y, N) means that at present Tm is in state q,, scanning the symbol x, will enter state q, and write ‘y’ in the place of ‘x’ and remain stick with current position that it does’t move towards left or right. Let us see some example for the better understanding. Example 10.1. Consider the Turing Machine (Q, 5, I’, 8, qo, ht) defined below that erases all non-blank symbols on the tape, where the sequence of non-blank symbols does not contain any blank symbol # in-between : Q = IMM = = {a,b} Tr = (a,b, #} and the next move function is defined as follows : G : input symbol a b # # Here it is assumed that tape head is scanning right most non-blank symbo! first, for example, #ababbaa#. °ws INSTANTANEOUS DESCRIPTION 203 here are following differences j Le ces in Tape He, [RTU 2001] ‘ad of FA/PD, Aa g {) The cells of the tape of an EA op and Turing are never changed /written inty 8 PDA are only re: Bee erent ioe ly read/scanned but ‘as the cells of the t: : tape of TM he tape head of a (id However, the eee er @ PDA always moves from le! 5 owever the tape Of TM can mea eves ftom left to right as aces of FA and ‘sts,mentioned in () and (i) a e directions. tat ae role in decid the information in the tape J ols aren nena set y any role deciding future moves oe i fa cells arent scanned ; information contents of mation, but in the case c n of all the i i seanmied also play a pole in deciding future ae oie sanity ‘ifferent definitions of configuration or Instantaneous Deseristion (I eae ef a TM. escription (ID) in the The ID of a Turing machine is the information in respect of : (i) Contents of all the cells of the tape, sfarting from the right most cell upto atleast the last cell, containin; : ini all cells upto the cell being cco Sa ne (i) The cell currently being scanned by the machine and (iii) The state of the machine. For example, let us assume that Turing machine TM is at state q, scanning, the symbol g with the symbols on the tape as follows : lee lele[ lola ]ele ----- { on We can show the situation as follows : (ay, Htbdaftighkt) 10.5. TRANSITION DIAGRAM [RTU 2001] In some situations, graphical representation of the next-move partial function § of Turing machine may give better idea of the behaviour of TM in comparison to the tabular representation of 3. A Transition Diagram of the next-move functions of a TM is a graphical representation consisting of a finite number of nodes and directed-labelled arcs between the nodes. Each node represents a state of the TM and a label on an arc from one state (say q,) to a state (q) represents the information about the required input symbol say ‘a’ for the transition from 7; tO 42 to take place and the action on the part of the control of TM. The action part consists of (i) The symbol say ‘b’ to be written in the current cell and (i) The movement of the tape head. | The label of an arc is generally written a5 a/(b, ™), wherein is L, a x ig qDuting the designing procedure of tuning machine Tm any eee assumed to be written on input taple in following : #abbabbé orTHEORY OF AUTOMATON 204 that is Head is on eatreme right-blank in the starting and en aching starts processing the string at qy (starting state) then it is S4PPosed to rea first input symbol of the string, from right to left; as fellows + #abbabbt r gy (initial state of the machine) 2 ET, 8 dy Ml Solution. where Q = Mor Iv Fz I r= 101) r= (0, 1,4) and 5 be given by the following table 0 1 ‘ 9 = — (ay # R) n (ay 0, R) (ay #, R) | tN) % (gy 0, L) (qu 1, R) (h, #,.N) h - _ a The transition diagram for above TM will be as shown below, where we assume that ‘qq’ is the initial state and ‘h’ is a final state/half state. 14, R) 14(#, R) 4, N) #i(#, N) 0/0, L) Fig. 10.2. Example 10.3. Design a TM that recognizes the lan, i of even length over alphabet {a, b). Babee cect Solution. Let Turing machine is Tm = (Q, 5,1, 8, qy hi) = = {a, b} T = (a,b, 4 Q = (Gy ay hy Here hh is half state when machine halts i after accepti: initial state. Here next move partial function 8 is giventes fone peaCHINES NG MA wat 205 a b = 4% 0 | ity | anny i LY Ty, b, Ly . h ; ‘ Accept Here “Is for undefined move, We can construct the transition diagram a follows alfa, L) alfa, 1), bitb,L) #14, N) Fig. 10.3. Example 10.4. Design a Turing Machine that accepts the language of all strings which contain aba as a substring, Solution. Let Turing Machine is TM = (Q, 3, F, 8, qy I) = = (a, b} Tr = {a, b, # Q = (0 Gv Ga Hh Qo is initial state (qy a L) (qy a, L) (h, a, L) bi(b. L) Fig. 10.4.1y OF AUTOMATA AND COMPUTA, 206 THEOR Ton 10.6. TURING THESIS / any computational proces s captured within the class “The power of Turing Machines.” angen erraretand tne atae e vd that Turing thesis is just a conjec a theorg, It may be noted tha Gjuced from more elementary > logically de fa! », Turing thesis cannot be logi = falee, ff'a more er, the conjecture can be shown to be false © powers ¢ all the languages wh; ompt el is proposed that can recognize 4 ca aaa d py the FM model and also recognizes at Feast One mo language that is not recognized by the TM. : The Turing Machines are designed to pla different roles : (i) As accepting devices for languages, and PDAs. fs . (i) As a computer of functions. In this role, a TM represents a particular function. Initial input is treated as representing an argument of the function. And the (final) string on the tape when the TM enters the Halt state treated as representative of the value obtained by an application of the function to the argument represented by the initia] y atleast the following thre similar to the role played by Fa, string. (iii) As an enumerator of strings of a language, that outputs the strings of a language, one at a time, in some systematic order that is as a list. 10.7, TURING MACHINE FOR COMPUTING FUNCTIONS Turing machine can be used to compute functions. How is it possible ? First we see how to input a string to a turing machine. We adopt the following policy to input any string to a turing machine. The string W is presented in to the form of # W #, that is string, W is surrounded by blanks symbols from both sides and is placed on the left most square of tape, the head of turing machine is positioned at the right most blank symbol which immediately follows the string W. This is shown by an underscore that is we use an underscore to show the current position of machine head in the tape. A turing machine is said to halt on input ‘W’ if we can reach to a halting state ‘h’, after performing some operations, that is if, Ty = (Q, %,T, 8, qq h) is a turing machine then Tm is said to halt to on input W if and only if (q, # W #) yields to (h, # p #). Definition A function f(x) = y is said to be computable b ing machine Tm (Q. 5,1, 8, qo, S), if (S, #x#) # (h, #yy ihre x may tes ph alphabet 2," and y may be some alphabet Us and Ey, 3,05. Symbol # has its usual meanin; aaa ¥ after a finite number of steps. '8 as in automata, means string x yields © It means that if we sive input x to the turi i Ng machine ing machine gives output as a string if it computes the fare Sy ‘unction f(x) = y.pAcHines 207 Design a tur Je 10. 1% machi pap which compute the funct yn? +1 for each m that belongs to the set of natural numbers. sation. Given function is f(m) = m + 1, Here we represents input m0 sola a number of 1's on the tape, re we represents input sO” ¢ wpe we PS cxample m = 1; input will be #14, te n= 2; | be #Il# and 50 on. I put iF ilarly output can be seen by the number of I's on the tape tet Turing machine be Tm = (Q, 5, 6,6, qy h) Q = My, hh r= (1 4) where qyis initial state. (Gy # R) (h, 1, R) Here ¢ is input at any time. Let input be m = 3 that is tape situation is #/I1# Now let us process the given string. (Note : We are processing string from right to left). #111 q, + #IllRq, + #ll[lth Example 10.6. Prove that following function is computable fin) =n +2 Solution. We know that if any function is computable then there exist 2 turing machine for it. “so it will be sufficient to construct a turing machine to prove any function computable”. Let Turing machine for given function be Tm = (05.1, 8 Goh) Q = (or I de Hh r= (L# 4p is initial state and halting state is represented by “I. Transition relations are defined as follows = (qy, # RY (dz 1, R) (h, 1, R) its initialy turing machine is in qp state, when it reads / or # then it changes S encgitt !0 9; and moves towards right (right symbol is only blank). At q, it ntered with # and replace it by J, change its state to 42 and moves tow _ "wards right. At q,, # is replaced by I and machine halts after moving right.eve oS Let = 3 that is #il# then Tm, behaves as follows L lily, + MUNN ay + HULL; ye HITLLE I a turing machine that replace every 0 ang Lit, Example 10.7. Design every 1 with 0 in a binary string. Or q] is computable where w € {0, 1)* Prove that function So) the one’s complement of w. Solution. We want to design a turing machine that takes input as tn Nt then its output would be #010#. This machines can be designed by y* following idea; scan backwards through the input, replace every 0 with? the every 1 with 0, until the blank marking the left most sequence is fou; md order to leave the tape in its ind. In proper format, the machine must then retun head to the blank marking the right end of the input. mits Let Turing Machine is Tm = (Q, 2, T, 8 doh) = (do dv Mh (0, 1} = (0, 1, # and " Q z r 4p is initial state. 3 can be defined by following transition diagram. FG.) #4, N) ot, L) Fig. 10.5. Here J represent non-blank symbol (in this case either 0 or 1). Let input string be w = #101100# #101100 qy + #10110q91 #1011qg11 #101qg11 #109,0011 #1qo10011 #qq010011 #q,010011 #0q,10011 #019,0011 #010q,011 + #0100q,11 #01001q,1 + #0100119,# © ee oiool#l Tere tT TT TTT > |ao. _ _ jos. TURING MACHINE AS La 209 x wring, machine works as Hous whether a ot wt eto ring, ‘w able ives the exact information that a n automata ts only able to ac opt rth an be used for some difficult structure jo show that a string is accepted by ‘Turi ring w then Ht will leave symbol y on (S, hw) 8 (hy y th) and it will leave symbol 1 if w is not accepted, that is ; (Sw) (hon yy Now at this level we can compare, the | expression, context free grammar jetter); as follows in ANQUAGE ACCEPTORS, » Tangiiape Hua acceptor for a language Lif it is 0 the language Lor not. In this automata ¢ Har Lauata can given. But remember, ar languages and so, We will use » ns Machine or not. if Tm accepts a Ne tape and halts, that is belongs a turing, machine symbol “y’ and ‘n’ language accepted by the regular and type-0 grammar (I will introduced it ionding | Non-determi- Language What can | Example of defined by | Acceptor | nism = Det- closed under | be decided | application erminson Regular [Finite Yes Under union,] Equivalence,| Text editors, Expression] Automata Product, | emptiness, | sequential kleene star, | finiteness, |circuit intersection | member- complement | ship Pushdown Union, Emptiness | Programming automata product, | finiteness | language kleene star |member- | statements ship compilers Turing, machine, ‘Computers post machine IDPDA, nPDA Intersection, Kleene star. Fig. 10.6. Example 10.8. Design a turing machine that recognises the set of all Strings of 0’s and 1’s containing at least one 1- Solution. Designing such a turing macnn “designing this turing machine we will move tow: then halt. Let Turing machine be Tm = (Q, eis very simple. For the ds left until 1 is found, and | where Q = Mo av Mh r= (0,1 #) 5-101 4p is initial state ed by following transition diagram : ti 4nd transition relation 6 can be represenTHEORY OF AUTOMATA AND COMPUTATioy 210 wi, N) Fig. 10.7. Here halt state It is reached only when at least one 1 is encountered ang h works as accepted state. Let us process the string : #00011# H00011q) + #001q,1 + #009,11 + #0q,011 + #0q,0011 + h#000011# 10.9. COMBINING TURING MACHINE now we have seen only simple examples of turing machine that do not impress us, because we have said that turing machine are ultimate computers, that is turing machines are capable of carrying out complex calculations, in spite of their limited mode of operation. In this section we present a method to build complex turing machines by combining simple ones. In this respect a Simple Turing Machine can work as “function” for other complex turing machines. Now we see how to combine turing machine. Suppose Tm, is a turing machine that is not known to hang. Then Tm, can be made part of a large turing machine Tm as follows : Tm Prepares some string as input to Tm,, placing it near the right end of non- blank portion of the tape, passes control to Tm, with read/write head just beyond the end of that string and finally retrieves control from Tm, when Tm, has finished its computing. It is guaranteed that Tm, will never interfere with the operational computation of Tm. This is like a function, when we call a function (say Tm,) in the main function of a simple ‘C’ program the control simply returns to main program after function Tm,, performs its calculations. 10.9.1. Rules for Combining Turing Machines machine edPt 2 Braphical representation to show the combining of tins eaiviaen ever this representation is the same as that of a finite automat Sonnet Tae ines are like the states of the automata and these machines as machine to anothe aries as the states of automata. The connection from ‘ . machine is then seer! Not be pursued until the first machine halts; the ce they were left b arted from its initial state with the tape and head position y ¥y the first machine, Th's can be shown by the following fis4™ > 1m, —+ tm, ° Fig. 10.8., wi myn tarts comp Zi He 1 Puting (tha {when Tm, halts, control, now initial state in finite automata) yal . an Now consider the following m, tm, ROeS to mac chine Sm en, taba Tm, Fig. 109, 8 with machine current head pi halts, the c 8 to the symi This machine starts computin, the symbol on the tape under the the figure 10.9 shows when Tm, or Tm, respectively, accordin, which is @ or b or #. Here we are Boing to discuss certain symbols to represent simple machines These symbols will be used further, () Fig. 10.9 is the basic machine which moves tow during scanning any input (0) symbol. State ch, ( } alo, L) Fig. 10.10. (i) Fig. 10.10 is the basic machine moves towards right by one cell, when current input symbol is blank or non-blank (6). ( ) o(a, A) Fig. 10.11. (ii) Fig. 10.11 is the basic machine, which moves towards left till the first blank symbol is encountered. AF, L) Tm,. Now when Tm, halts, osition can be a, b or #. Taen ‘omtrol goes to machine Tm, Tm, bol under current head position ards left by one cell ange is also possible. aid, N Fig. 10.12. (iv) Fig. 10.12 is the basic machine, which moves towards right until the first blank symbol is encountered. H.R) #i(H, N) Fig. 10.13. - (%) Fig, 10.13 is the basic machine, which moves towards left until the first non-blank symbol is encountered. Hi, L) ie), Fig. 10.14. R fing MACHINES— 212 THEORY OF AUTOMATA AND COMPUTATION (vi) Fig. 10.14 is the basic machine, first non-blank symbol is encounteres we, which moves towards right until the de WHaN) Fig. 10.15. Example 10.9. Construct a turing machine that computes the following function. fn, m) =nem Solution. Let us decide the policy to show # 1, #II# represents 2 and so on. We assume and m) are written on the tape separated by #. Tha! and 3, the input string will be #I/#III#. Now we want to such a turing machine which gives output as follows £(2,3)=24+3=5. hat input numbers : I represents hat input numbers (that is n t is if we want to add 2 IDOLE + $ID When we analyse the output then it becomes clear that for constructing turing machine for f(n, m) = n + m, we have to remove #, which separates nand m. Infact resulting turing machine works as a left-shift machine (say SL). It shift the each symbol of m portion of input by one cell towards left. Let turing machine is Tm = (Q, 5, I, 8, qq, h) where = (or I Gar Gar ar HD = i = (L # 4MO 4o is initial state h is halt state and 8 is defined by following transition diagram. dil, R) HL) HAL) H(t, L)uRING MACHINES. Let us process a string #1114 * HIT gg + tit Iggt 114g 11 TING I #UHIg I HlltgydT #INdqyl #111119, #IIlIgyd #IIlIdq, #IIII#q, ITTIg gt #IITT#h Example 10.10. Design a Turing Machine which works as eraser. Solution. Let us first analysed the problem, here we want to design a turing machine which works as eraser, that is if we pass input #abb# then output should be ##, that is null string. Let the Turing machine be Tm = (Q, 5, I, 8, qo, hi) where Q = (or Gy = = F symbols Tan ery Te Te eT T = #u# qo is initial state and : Transition relation 8 is defined as follows : Wey HL) Fig. 10.17. Here it is preassumed that there is at least one non-blank symbol in the string, Now let us process the following string = Hababaq, + #ababg,# + #abag Ht + #abq Ht + #aq,# + Hgy# + Hh214 THEORY OF AUTOMATA AND COMPUTATION Example 10.11. Prove that following function is turing computable, ‘m~2, if m>2 fom = a ifms2 Solution. We know that if any function is turing computable then there exist a turing machine for it, so we have to design a turing machine of the f(m) function. For the input strings ## (m = 1), ##(m = 0) and #II# (m = 2) output will be #/# (m = 1). For the input string #IIII# (m = 4), output will be #1l# (m = 4 - 2 = 2, since m > 2). Let Turing machine be Tm = (Q, 3, 8, ©, qo") phere Q = (or Ir dar 95M Deu r={,a 4o is initial state and h is halting state. Transition relation 8 is defined as follows : #u(#,L) FIG, R) Fig. 10.18. Let us process the following string : #111 HIIIIqg + #INIg,# + #llq## + Hlth Let us process another string #/I# Hllqg + Hq, b agg Htgat + ith Example 10.12. Prove that following function is turing computable. n-1,n>0 fin) {5 »n=0 Solution. If function f(m) is turing computable then there exist a turing machine for it, so basically we have to design a turing machine for function f(x). This turing machine should give output ## for ## (n = 0) and #Il# for #111 (n = 3).| qypING MACHINES: | Ter Turing machine be 215 Tm = QE,1, 8, qy h) } where 1, Ht qo iS initial state and h is halting state Transition relation 8 is defined by following transition diagram : i Fig. 10.19. | Let us process the following string : i w = IIH HILL gy + HLTH H For string figot + Hth. i Example 10.13. Design a Turing machine for the following function : : faw =y Solution, Let us understand the meaning of f(x, y) = y, here we want to design a turing machine which takes input x = #1I# and y = #Ill# as string w= xy = #II#I1# on the input tape and output of the required turing machine is #III# that is y part of string. A 5 . / Now let us discuss the logic for this turing machine, consider the string #IIIII# move at extreme left and erase the x part and leave the tape head at extreme right. Let turing machine be : Tm = (0 3,1, 8 qh) (or Dy dar Far ( {L, #) %y is initial state and h is halting state. 8 is defined by the following transition diagram : where Fig. 10.20. HIT#lgy + #lltgg! b #llgy#l F #iqyf#lowe en t 216 THEORY OF AUTOMATA AND COMPUTATION tig Hd Algal j HH lggAT + HHH GST Wittig, + HMA G, + HHT, Example 10.14. Design a Turing machine for the following function fG,y) =x. , Solution. We can solve this problem in similar fashion as we have solved example 10.13. Here we have to design a turing which takes input w = xy (where x = #7l# and y = #Ill#) as string #II#III# and gives output #II# that is only x part of w and completely erase of part of w. Let Turing machine be Tm = (Q, 5,1, 8 qo!) Q = (MW ret r=({L4# 4o is initial state and h halt state we LY #4, N) Fig. 10.21. Let us process the string #I/#III# . HITHLLIgy + #ILELIgg# + #11 IG Ht 1} HIliggtHt# + #Ilth. Example 10.15. Design a Turing machine for the regular expression r=aa*. Solution. We have to design a turing machine which accepts strings which are in regular expression r. r = aa* It is collection of strings starts with ‘a’ followed by any number of a's and contain only a’s in the strings. Let turing machine is Tm = (Q, 2, T, 8, qy, h) Q={ =z = {a} Tr = (a, #) 4o is initial state and h is halt state 6 is defined as follows : al(a, L); 1g MACHINES ue 217 E y stand for yes string is acce e. Consider the string #aaait Haaagg + Haagya Hag,aa + fqyaaa + Yhaaat when we get Y at input cell, means that string is accepted. Example 10.16. Design a Turing machine for the language L = {(ab)"In 2 0} or for the regular expression r = (ab)*, solution. Let Turing machine be Tm = (Q, 5,1, 8 qh) Q = (or dy I) d = (a,b T = (ab, # 4p is initial state and h is halt state. ala, ) ; 'd here halt state Y, signifies as accepting stal Fig. 10.23. Note : All the move which are not shown, leads towards not accepting states. Let us pass a string w = #ababi 0 #ababqy + #abaq,b b tabqgab + Haq,bab + Hggabab + Yhabab Y: Stands for accept, Tm accepts string and halts. Example 10.17. Design a Turing machine which accepts the language L= fw e (a, b/w has equal number of a’s and b's) / Solution. The language L is the set,of strings (included null string) in Which every strings eil ‘b.but number of a’s and b's in the Ty strings either start by 4 oF ?. ‘sin tl String are Diwape equal That is turing-machine should accept strings like218 THEORY OF AUTOMATA AND COMPUTATION ab, aaabbb, baba, abab, and so on and it must re) abbb, abbab and so on. ‘The Turing machine that accepts Lis sh alla, F), alta, L), alla, bib. Ry am, b, abb, baa, own below : bib, U) ai. aiid, L) Wid. A) bib, U) Fig. 10.24. Y : Stands for Accept this machine changes one a and one b in two d's. It does so by scanning the the non-blank part of take two times from right to left, once for an ‘a’ and once for ‘b’, returning cach time to the right end of the tape before starting the next scan. This sequence is repeated until the supply of a or b is exhausted. Now if machine sees all d’s on the non-blank part then it halts that is, it accept the string. The move which are not available in the machine leads towards not accepting state. Following is the sequence of operation on string abba. Habbagy + #abbdqy Habbdttqy tabbdq, Habbqyd #abddq, tabddtq, Habddqy (one cycle is completed) Habdgyd Habgydd Hag,bdd ddbgydd tdbdggd tidbddgy Hdbddtiqy idbddq, dbdgad Adbgydd adddq,d dddddq, sddddtiq, In one main cycle, BS TTT Toret a Tet TT tart TT219 tddddq, s Hdddagd tddagdd b Hdggddd tqgddda + Yhdddd 1 le 10.18. Desi i ‘came “sign a Turing machine for the following languages : L = (a"b" 21) Solution. We are going to design a turing machine which 2007, 2005) caiin whi ; ; h accepts a set of strings In which every string starts with ‘a’ follow. PI H ; ed by , every string ends in equal number of b's a6 a's. No ‘a is encoumtered efter first ‘b' is read. It will not accepts the strings like €, a, aa, bb, ab, aabbb, aab fs eo on 1 @, aa, bb, ab, aabbb, aa ! Let required turing machine is } Tm {QE 1, 8, qo, h) Q = Wor 9 dar Ia hh = = (a, by} T = {a, b, # Qo is initial state and h is halt state. bib, L), alfa, R) aca L) bi(b, R) #1(#, ) al(#, R) aL Fig. 10.25. The moves which are unaddressed, leads towards rejecting states. Let us pass the string w = #ab# 4 Habqy + #aqy# fiquatt + Haga ft + tltig, + HiggHt + #Yh# Example 10.19. Design a Turing machine for the following languages : L = (w € {a, b, c}*/w has equal number of a’s, b’s and c’s}. Solution. We can solve this problem in similar fashion as example 10.17. Here turing machine start searching from right and first search ‘a’ then move to extreme right and this ‘a’ is repalced by d. Now machine search for ‘b’ and if find replace it by ‘d’ and again move on extreme right and searchi 220 THEORY OF AUTOMATA AND COMPUTATIoy corresponding ‘c’ and if find replace it by d, this completes one cycle. Thi process reepated and if all symbols are replaced by d's then string is accepteq and rejected in any other case. Turing machine is : a/(a, L), Fi. (a, L), ee di(d, L) bi(d, R) d/(d, L) ae. A) alla, L), bib, L), auld, U) HHH, L HG.) Fig. 10.26. Htebaqy + #cbditqy cbdgy Acbqyd tteddqy tedditq, Heddgs Hedge Heqgdd ttddqgdd tdddggd tddddg, Hddddiiq, tddddgy Hdddggd Hddqydd Hdqyddd #qgdddd Yhdddd Example 10.20. Design a Turing machine for the following language + L = {ab"n > 0) Solution. Here we want to design a Turing machine which accepts the language L which consist a set of strings in which every string w begins with single ‘a’ and followed by one or more b's, TTTTTI Tt rTttrtttTtTtE MACHINES URNS 221 arly Turing machine will a strings lil 4 Chet y Seca wd accept strings like abbbb, ab, and rejects strings i Here is required turing machine Fig. 10.27. The moves which are not shown are considered as rejecting states. w = #abbit #abbqy + #abq b Hag tit b tiggtttit + Yh# Example 10.21. Design a Turing machine which computes following function. f(w) = ww", where w® is the reverse of string w . (w € (a, b)*). [RTU 2001] Solution. Let input is #ab# then Tm should give output as #abbait. FG, RY HH, L) #1(#, N) H.R) ‘Alfa, L), BU(b, L) Fig. 10.28. Habgy + #aBHq, + #aBq3b + Haqgbb #Abq,b + #Abbq, + #Abb#A, + #Abbq;a + #Abq,ba + #Aggbba + #qqnbba222 THEORY OF AUTOMATA AND COMPUTATIQy, & Hagybba be Halyg gba + abbqya + Habbag, Habba, Habbatth b is Example 10.22. Design a Turing which works as copying machine (c), for w € (a, b)*. Solution. We want to desi input w = #ab# as Hab#ablt that is twit [RTU 2006) 1 a turing machine which gives output for + Tm #wtwit The transition diagram of turing machine will be as follows : i © Let w = #ab# is input then : WR) Alla, F), B10, F) Fig. 10.29. + #aggb b #tqgab #aq,b + #Abq, b HAbig, } #Ab#Hg, b #Abtigga b #Abgyia + #Ag,b#a + Habg,#a + aBiqya + faBHag, + aBHaig, + HaBiatg, + #aBHaggb + HaBHqab + #aBg,Hab b Habiiq,ab + #abtagyb b Habiabg, + tab abtqy } #abtabith,x! ants MACHINES: 2: 9.20: EXTENSION OF TURING MACHINES becomes clear that tu Now . ring machine can perform fai mputation. 1 order fo better understand their ae ert faily powerful cote the effect of extending the turing vel ne bowen, we shall Pe od ecg te Reaching model in various directions. i B Machine can in each instance be ated by the standard model. Such results increase ; spi machine i indeed the ultimate compa our cmtience tha ihe prose sion i nove io Move powerful automata. A side benefit by these results is) hat we shall feel free sub: equently to use the additional | features when designing turing machines to solve particular problems. ‘The extensions of Turing machine considered are : | a eae aries instead of one only, each tape having its The tape may be allowed to be infinite in both the directions. (iii) There may be more than one head scanning various cells of the tape. Two or more heads simultaneoush read the same cell or may attempt to write in the same cell. ¥ aid (iv) The tape may be K-dimensional, K > 2, instead of only one- dimensional. (v) For a given pair of current state and symbol under the Head, instead of atmost one possible move, there may be any finite, possible zero, number, of next moves. This is called Non-deterministic Turing Machine. 10.10.1. Multiple Tapes Turing Machine One can think of turing machines that have several tapes (see figure 10.29). Each tape is connected to the finite control by means of a read/write head (one on each tape). Tez bo ib debe Peis patho [oa ee Tape m 7 h 2 1 Finite ———>} Pa ‘Control W iF ; Fig. 10.30. The machine can in one step read the symbols scanned by all its heads nd then, depending on these symbols in current state, rewrite some of thoseoN 224 ‘THEORY OF AUTOMATA AND COMPUTATION scanned squares and move some to changing the state. For any fixed integer m 2 1 equipped with m tapes and corresp machine studied so far in this chapter m=1. of the heads to the left or right, in addition ing machine is a turing mach; |, an m-tape turing mac! ‘8 Machin, nding heads. Thus standard turin’ ig just an mi-tape turing machine, wit Definition Let m > 1 be an integer. ; ‘An m-tape turing machine is a six tuple machine as follows : Tm = (22,1, 5, doh) the finite set of states of the finite control The finite set of input symbols The tape symbol where [ = 5 u # halt state he Q The initial state, q ¢ Q The transition function is a function which maps : (Qx 3") > Qx (SUIL,R NI"). That is, for each state-q, and each m-tapes of tape symbols (a), a, ..., a,), B (Ay, Ay voy 0) = (P, (Dy, by «-by)), where P is, as before, the new state, and b, is the action taken by Tm at tape j. Computation takes place in all m-tapes of a m-tape Turing machine. Accordingly, a configuration of such a machine must include information about all tapes. where Example 10.23. Design an m-tape turing machine which works as copying machine. Solution. We have already solved this problem by the standard one-tape turing machine in example 10.22. Now we are free to use m-tape in the designing of turing machine. We will design a 2-tape turing machine, which takes input #w#t and gives output as Huw! Let us clear notations for the tapes first. For the first tape machines notations used will be written as R’ and L’ input symbol from tape-1 is read-out as o’. Similarly for the tape-2 notations of machines will be R* and L? and so on. Input which is read-out from tape-2 will be shown as 0”. This turing machine can be accomplished as follows : (1) Move the heads on both tapes to the right, copying each symbol on the first tape on to the second tape, until a blank is found on the first tape. The first square of the second tape should be left blank. (2) Move the head on second tape to the left until a blank is found. (3) Again move the heads on both tapes to the right, this time copyi8 symbols from the second tape on to the first tape. Halt when a blank is found on the second tape.ro 1 225 S shown in Fig. 10.30 as follows : 2 eae Wabtcen hat (hy Move-1 Moved Fig. 10.31, Here # R= OPO Cran) ind Ly = (Sem Move-3 ‘The sequence of actions can be pictured as follows : First tape #wit Second tape ## ‘After (move-1) : First tape #w# Second tape #wit After (move-2) : First tape #wif Second tape #w# After (move-3) ~ : First tape #wiwit Second tape #wit 10.10.2. Two-way Infinite Tape The extensions are distinguished from each other and from the standard Tm through different definitions of next-move relation 8 and of configurations for each of the extension. So here we discuss the extension only in terms of definitions of 8 and of configuration. Like standard Tm, in this case also, the next-move is given by 8 as a partial function from (Q xP) to (Q x Fx {L, R, N)) The following three points need to be noted in respect of configurations of Two-way Turing Machine. ( Configuration/Instantaneous Description. In standard Tm, if there are a number of left-most positions which contain blanks, then those are included in the configuration that is if the one-way configuration tape is of the form Habit d of HH. # & then the configuration in the standard Tm is written as : (qa, tabitcdefitt .. #) , hang Woven, in the two-way infinite tape Tm, both left-hand and right- inuous sequence of blanks on each of the right hand and left hand of sequence of non-blanks. Therefore, in case of two-way infinite tape, if * above string is on the tape then it will be in the form. (qy, # HH ab # cdef HH #)|D COMPUTATIO) RY OF AUTOMATA AN! IN 226 THEO! (ii) No Ceasing of operation withow no left end of the tape, therefore, there is no left-end of the tape. eres (ii) The empty Tape configuration, When at some point of time all the cells of the Tape are #’s and the state is say 4 config ay tape may be denoted as : | Halting. In this case, as there jg possibility of jumping off the then @#) g # is shown in the ne d 1 does not provide an: in configuration. w model of computer to y additional where only the current cell containin Despite the fact that, it is possible move left as far as required. The mode computational capability. 10.10.3. Multiple Heads Turing Machines In order to simplify the discussion, we assume Heads on the tape. The tape is assumed to be one-way infinite. We explain xample. Let the content of the the involved concepts with the help of an e 4 tape and the position of the two heads that is H; and H,, be as given below: Hap ctd ¢ fit. Hoth Further, let the state of the Tm be 4. The move function of the two-head one-way turing may &(state, symbol under Head1, symbol under Head2) = (New state, (Sj, My), (Sz, Mz) where §; is the symbol to be written in the cell under H, (the ith Head) and M, denotes the movement of H;, where the movement may be L, R or N and further L denotes movement to the left, R denotes movement to the right of the current cell and N denotes ‘no movement of the Head’. Two special cases of the 8 function defined above, need to be considered : (i) What should be written in the current cell when both Heads are scanning the same cell at a particular time and the next moves (S,, M,), (Sy Mz) for the two heads, are such that S, # S, that is symbol to be written in current cell by H, is not same as symbol to be written in current cell by H. In such a situation, a general rule may be defined, say, as whatever is to be done by H, will take precedence over whatever is to be done by Hy. (ii) For two-head one way tape, a configuration shall be called hanging if 8(q, symbol under H,, symbol under H,) = (q,, (S,, My), (Sz, M,)) is such that either (a) Symbol under H, is in the left-most cell and M, is L, that is movement of H, is to be to the left, that there are only two be defined as or (b) Symbol under H, is in the left-most cell and M, i: is vel it Of Hy is to be to the left. Eb CRS eye The above discussion can be further extended easily to the case when number of Head: more than two. The pow i the use of extra heads. Ty ape ne game caea a8 MACHINES nor v K-dimensional Turing Mac! ‘again 10 facilitate the understanding, of the basic id tO only Two-dimensional Ty s involved, let us nitially only Two-dimensional Turing Machine. Then these ideas can generated to K-dimensional case, where K > 2. : sill eee ease of two-dimensional n the cas sional tape as shown below, we assume that the rfunded on the left and the bottom, fe assume, that fhe * 4 3 0 1 2 3 4 5 Fig. 10.32. Each cell is given an address say (i, j) where i is the row-number of the call and j is the column number of the cell. ‘A configuration of a two-dimensional Tm at a particular time may be described in terms of finitely many of the triplets of the form, (iy, fy c) where for each such triplets of the form, (iy iy, c) where for each such triplet (i, #2) isthe address of a cell and c denotes the contents of the cell. Only these cells we included in an ID, for which, the contents, are non-blank symbols. In the configuration or ID, order of the cell which are included in an ID, Row Major Ordering is to be followed, that is first all the elements in the iw with least index are included in the 1D, followed by the elements of the ew with next least index and so on. Within cells of each row, the cell with ew contents and having least column number is included first followed by the non blank cell with next least column number and so on. Lege Q, Che F- tA, that is Cy is a non-blank tape symbol. The configuration at a particular instant is denoted by (Gq, (Hy Hh) kgs ae Caps lr dar Cig) Ge jv Gy) where each of C,,, Cj, «is non-blank and these are the only non-blank on the tape. a __ Also (H,, H,) denotes the location of the cell currently being scanned that is the cell under the Head. 10.105. Non-deterministic Turing Machine [RTU 2007, 2002] We have already seen that when finite automata are allowed to act non- deterministically no increase in the computational power, but that non- determinism in push down automata are more powerful than deterministic es. sant’® £2" also imagine turing machine that acts non-deterministically. In andard Tm, to each pair of current state (excePt the halt-state) and the symbol ard scanned, there is a unique triplet comprising of the next state, unique on in terms of writing a symbol in the cell being scanned and the motion,228 THEORY OF AUTOMATA ANO COMPUTATION Oe if any, tothe right oF lel, However, in ease of NDTM (non deterministic turing, machine), to each pair (ya) with gas current state and a" as symbol being scanned, there may be a finite set of triplets (4), am); 4 1, 2, .) of possible moves, The set of triplets may be empty that is for some particular (j,2) the Tim may not have any next move, Or alternatively the set {( 4m) may have mote than one triplet, meaning thereby that the NDTM in the state and scanning symbol ‘a’ andl can choose next move from the set [(y a, m)} ‘of next moves, From the above discussion it can be easily understood that standard Tim isa special case of the NDTM in which for each (q, a) the set ((q, a), m)} in next moves is a singleton set or emply. {mn onder to define the concept of NDTM and a configuration in NDTM, We assume that the tape is one-way infinite, Proper non-determinism means that al some slage, there are alleast two next possible moves. Now, if we engage two different machines to work out further possible moves according to each of these two moves, the two can work independent of each other, This means non-determinism allows parallel computation, Definition. A non-deterministe Turing machine isa six tuple (Q, 5,1, , fy Hi) where Q : set of states % : set of input symbols TP’: set of tape symbols 5: (Q xP) power set of (Q x Px IL, R, NI) 4q + initial state and 1: hutstate, re Q The concept of a configuration is same as in case of standard Tm. But the Concept of ‘yield in oe step’ denoted by Tm has different meaning, Here one configuration may yield more than one configuration. Example 10.24. Construct an NDTM which accepts the language {a'b" :m2 1, m2 1}, that is language of all strings over (a, , at least one ‘a’ and one ‘b’ and all a's precede all b's, Solution. The diagrammatic representation ofthe required NDTM is given below : (tally tape head is at leftmost symbol, that is’) [nthe proposed NDTM, as the motion of the head is always to the right except in the Halt state therefore, R is not mentioned in the labels in the diagram below : ala bb gag bb Fig, 1033, in which there is aswrins MACHINES 229 rere the label /y on an are denotes ; at if symbol 0 C1 q o ements of the call are lo be replaced ae in the current cell is “x may be defined as i Formally the proposed ND" : M = Uo. dale la, Be ta, by HL, 8, doy Hh pore 8 is defined a8 follows : pio 5(qo, a) " (qa 4 R), (qs a, RY) 8(qq, b) = empty 5(q,, a) = empty 81 &) = (gy, b, R), (h, b, N)} If the machine has no move, then it halts without accepting the string. When turing machines are allowed to act non-deterministically, is there any increase in computational power ? We must first define what it means for a non-deterministic turing machine to compute some thing. Since a non- deterministic machine could produce two different outputs or final states from the same input, we have to be careful about what is considered to be the end result of a computation by such a machine. For a non-deterministic machine to decide a language and compute a function, we require that all of its computations halt; we achieve this by assuming that there is no computation containing after ‘m' steps, where m is an “upperbound” depending on the machine and the input. For Tm to decide a language, we only require that at least one of its possible computations end up accepting the input. For a non-deterministic turing machine to compute a function, we require that all possible computations agree on the output. If not, we would not be able to decide which one is the right value of the function. 10.10.6. Recursively Enumerable and Recursive Languages [RTU 2002] When a Turing machine executes an input, there are four possible outcomes of execution. Then Tm (i) Halts and accept the input (i) Halts and rejects the input (iii) Never halts (fall into loop), or (iv) Crash. We also know that the language accepted by Tm is known as recursively enumerable and the set of recursive languages is subset of recursive numerable set. The set of recursively enumerable languages are precisely those languages that can be listed (enumerated) by a turing machine. Basically, if a Tm can fenerate all the strings in a language, another Tm can accept all the strings are not in the given language. (Strings that are not in the language may ® tejected or may cause the turing machine to go into an infinite loop). ever !Rguage is recursive if there exists a Turing machine that accepts lana? Stting of the language and rejects every string that is not in the Buage. So, we are sure about the rejection of the strings with are not in the ‘giv 8iven recursive language. Res,230 THEORY OF AUTOMATA AND COMPUTATION Rocursively Enumerable Languages pees Fig. 10.34. Theorem 10.1. Ifa language L is recursive, languages. Proof. A language is recu machine that accepts every string of the I if there is a Tm that accepts every string of the language strings that are not in the language. ; So, every recursive language is also recursiv statement of the theorem is true. 10.10.7. Turing Machine as Enumerators We have viewed turing machines as recognizers of languages and as computers of functions on the non-negative integers. There is a third useful view of turing machines, as generating devices. Consider a multi-tape turing machine Tm that uses one tape as an output tape, on which a symbol, once written, can never be changed, and whose tape head never moves left. Suppose also that on the output tape, Tm writes strings over some alphabet ©, separated by a marker symbol #. We can define L(Tm), the language generated by Tm, to be set of w in ¥* such that w is eventually printed between a pair of #’s on the output tape. Note that unless Tm runs forever, L(Tm) is finite. Also, we do not require that words be generated in any particular order, or that any particular word be generated only once. If L is L(Tm) for some turing machine Tm, then L is an regular set and conversely. The recursive sets also have a characterization in terms of generators. So finally we can say that : “To enumerate a set means to list the elements one at a time. To stay that a set is enumerable should mean that there is an algorithm for enumerating it, so far, we have seen Turing machines as recognizers of languages and as computers of functions on the positive integers. There is another purpose a Tm can serve. It can be a generating device. A Turing machine Tm is said to be generating or enumerating if we are able to produce each word of any languae L separated by blank symbol (initially tape is empty). The order of the strings is not important and any string may be repeated indefiitely. Theorem 10.2. If any language L is generated by the Turing machine, then L is accepted by some other turing machine. then it is recursively enumerable vely enumerable if there exists a Turing anguage and a language is recursive and does not accept ely enumerable. Hence, or If any language is generated by the Tm then L is recursively enumerable- Proof. Let Tm, be a turing machine which generates L. Now let us construct another turing machine Tm, which accepts L and Tm, is havin a?n eee Tin,, except that every time # is written Hatton on Tm, pauses while Tm, compare its input sted just before #. . s ec #. If they are same, 1 epts ‘ise TM, continues to simulate Tm,. yore, geen Tez acceP ove! santa ct Clearly Tm, accepts an input string if and only if it is generated by Tm,. L(Tm,) = L(Tm,) gener So ing language by Tm, theorem 10.3. If the language L is accepted by some Turing machine is recursive enumerable) then L is generated by some Turing machine. proof. Let Tm, is a Turing machine which accepts the language L. We aay define another Turing machine Tm, which generate the words over om ‘After each new word is generated, we run a simulation of it on the machine Tm,. If Tm, accepts, we print out the word on the tape inside #’s. If Tm, does not accepts, We skip it and go on to the next possi jlity from the word enerator TM,- Again, we apply the same method for the next word and we get list of words separated by # on the tape of Tm. Unfortunately, this method works if Tm, is guaranteed to halt on all inputs (either in final or non final states). However, it may possible that Tm, will Toop forever for some words, in such case we shall stuck waiting forever, and we cannot go on to test the next possible input string. To overcome this situation, we adopt the canonical order on 3*. The canonical order (ot lexicographical order or alphabetical order) over ¥ = (a, bis (¢, a, by aa, tb, ba, bb, aaa, aab, ab, ..) and over 3 = (0, 1], we define canonical order as {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, Let us number the possible input strings as w,, w2, .. in the usual canonical order. Let us assume that Tm, has four tracks. In second track it generates, in order, all the integers. Let at some point in the operation of Tm,, track 2 has the number 1 on it, Now on track 3 we generate, one by one, all possible strings from w, to w,, Each time we generate another input string, we copy the string from track’3 to track 4 and simulate the running of Tm, on it. But We run simulation for exactly 7 steps unless Tm, halts before. If m steps have Tot been enough to halt Tm, we do not waste more effort on this input string at this iteration. We erase track 4 and we go back to track 3 and generate the Text input string to be tested. However, if the input string is accepted within "steps, then we print the string on track between #s. we still erase the track 4 and go back to track 3 for the next input string to be tested. When we go back to track 3 to get the next string, we have to be sure that Br have not already tried all the input strings uP to w,. In order to be sure “this we must keep a counter on track 2 telling is How many strings we next andeed produced. If we have not gone up to ae ‘ve do pes fone ua"'® and repeat the process. However, if we find that we ave alee y track 3? 0 Our limit w, then what we must do is erase this track and incremen Ick 2 Track 2 ow has the contents 1 + 1 on it. We begin again fo generate 85 on track 3 from w, to W, , 1 and one by one simulate on track 4 the Ng of them on Tm, for we generate all the strings on track 3 exactly +1 (ies232 THEORY OF AUTOMATA AND COMPUTATIO, are neither accepted nor re cre | they arg abandoned temporarily. If they are accepted hey ela : on peal they have been printed on track 1 already. ie emu eee wefan ale ey input string begins at the start State of Tm, even’ May ibe niatenetre re already simulated the first 1 steps of the processing. May bi PS Were nop trick. If Tm, neither accepted no, enough, but the n + 1 steps will do the ee rejected in n + 1 steps, then we erase back 4 and ge npi Ea case from tracks 3, unless we have already generated up to w, , 1, In which caso we erase tracks 3 and increment tracks 2 ton + 2. Clearly, the only strings that appear on track 1 are thejwords that have been discovered to already be in L by having been accepted Tm,. Theorem 10.4. L is recursive if and only if there is a Turning machine that enumerates L in canonical order. : Proof. First we prove if L is recursive then there is a Turning machine that enumerates L is canonical order. We prove this by constructive algorithm, Let L is the recursive language accepted by the Turning machine Tm, clearly Tm, halts on every input. Now, we construct Tm, such a way that Tm, generates the words in canonical order, one at a time, on one of its track, Then Tm, simulates Tm, on that word. If Tm, accepts that word, Tm, print that word on the other track, separated by #’s It should be clear that Tm, will finish processing each word after a finite time because Tm, never enters into infinite loop (L is recursive and Tm, halts for every words). It is clear that Tm, enumerate the words in Lis canonical order. Now, we prove the converse i.e. if L is a language enumerated by some turing machine in canonical order then L is recursive. Let Tm, be Turing machine that enumerates the words of L in canonical order. We make a Turing machine Tm, that accepts L and rejects L’. Into Tm, we input the strings w to be tested. We then simulate the running of Tm, until its output (words of L) are longer than w. This will takes a finite amount of time. Now, we simply check to see whether w is among the words generated thus far by Tm,. If it is, we accept it; if not, we reject it. It is clear that all strings are either accepted or rejected ie., there is a complete decision procedure and hence L is recessive. steps this lie. Again, if they 10.10.7.1, Non recursively Enumerable Languages As we have seen that there are pumping lemma’s to show that certain language is not regular or context free language. Unfortunately, there is no such pumping lemma for recursively enumerable languages because according to church’s thesis any conceivable algorithm can be implemented by Turing machines. But there are languages to which no turing machine can accept. We show that such language exist by the certain theorems only and those languages are called non-recursively enumerable languages, 10.41. CHURCH'S THESIS What function can not be computed by turing machines ? This is verY surprising, It is believed that there are no functions that can be defined bY humans, whose calculation can be described by any well-defined mathematic algorithm that people can be taught to perform, thet cannot be computed by Tm’s. The Tm is believed to be the ultimate calculating mechanism.A NG MACHINES wort La) other ¥ Fj nf ean be represented as a turing Mate ie ensidered an algoritnn 1 Alonzo Church (93g This statement is called Church’s No computational p thes 7 's onal many sophisticated ‘s for Nreving it. Coa Sane Statement was slightly. diffecont becouse his pis WAS P slightly before the turing invented his machines. Church actually said that any machine that ean deve be able to perform all conceivable algori ° ti wilgans had called recursive funetions and comperable hee ee ene ind computable functions. Tm’s can 1] that Church asked, so they are oj il Sie ot machine Church descrineds ne possible model of the universal Unfortunately, Church's thesis can not be a theorem in mathematics pecause ideas such as “can ever be defined by humans” and “algorithm that people can taught to perform” are not part of any known mathematics. There are no arioms that deal with “people”. 40.12. UNIVERSAL TURING MACHINES [RTU 2007, 2003, 2002] We can consider turing machine in both ways : The turing machine is an “un programmable” piece of hardware, specialized at solving one particular problem, with instructions that are “hard-wired at the factory”. We shall now take the opposite point of view. We shall argue that turing machines are also software. That is, we shall show that there is a certain “generic” turing machine that can be programmed, about the same way that a general purpose computer can, to solve any problem that can be solved by turing machine. The “program” that makes this generic machine behave like a specific machine ‘Tm will have to be a description of Tm. In other words, we shall be thinking of the formalism of turing machines as a programming language, in which we cant write programs. Programs written in this language can then be interpreted by universal machine that is to say another program in same language. ee tain list of operations To begin, we must present a general way of specifying turing machines, so that their descriptions can be used as input to other turing machines. Universal turing machines ‘U’ takes two arguments, a description of a machine Tm, “Tm”, and a description of an input string w, “w”. We want U tohave the following property : U halts on input “Tm” “w" if and only if Tm halts on input w. U Cm" “w") = “m 0)". It is the functional notation of universal turing machine. To justify this we have to define a language whose strings are all legal "epresentation of turing machines. We adopt the following convention. A string "Presenting a turing machine state is of the form (q}0, 1}*; that is, the letter q followed by binary string. Similarly, a tape symbol is always represented as string in’(q) {0, 1)*. Let Tm = ing machine, and k and | be smallest integers Such that 2 > (ox a 87S Tr. Then each state in Q will be represented #4 followed by a binary string of length k; each symbol in ¥ will be likewise Presented as letter a followed by a binary string of ! bits. The head directions tet left (D and right (R) are included in input tape symbols to justify "+2 ™ in the definition of 1.a: 234 THEORY OF AUTOMATA AND COMPUTATION Example 10.25. Consider the turing machine m = (Q, 5, 8, 5) where Q= (Sqm B= (UH, b, a}, and 8 is given in following taby, le. States | Symbol 3 $ @ @#) s # (i, #) s b (S, R) q a (S, a) 4 # (S, R) 4 b aR) Since there are three states, three symbols in 5, we have k = 2 and | =3 These are the smallest integers such that 2* > 3 and 2! > 3 + 2. The states and symbols are represented as follows : State/Symbol | Representation Ss 00 gol qu 2000 001 4010 a011 a 100 Thus representation of baatta is “baatta” = a0012100a100a000a100. The representing “Tm” of the turing machine Tm is the following strings “Tm” = (g00, 2100, q01, 2000), (q00, 2000, 411, a000), (q00, 2001, 400, 011), (G01, 4100, 400, a011), (g01, a000, q00, a011), (q01, a001, q01, 011) In the last let us see pictorial representation of universal turing machine Poors 1m Input W \ ry Universal Turing Machine \|/ Result of calculation by Tm on input W Fig. 10.35. Result of calculation by Tm on input w. After discussing of above example we can have following obse Observation 1, A Turing machine M designed to solve a partic”: Problem P consists, apart from the description of the set of possible stales and the set of possible input etc. of mainly the description of the proce some coded form of a sequence of steps required to solve the problem i" srvation = articular —_bet tin of he ing chine Man hepa eae rants Tomguage) of the Universal toring machin eared eorcess alongwith the code of the input, is stored in the SST UTD perssost on the Fines of the control unit of nememory efithe JT ; bia a general purpose computer the ‘control unit of UTM, reads the codes for steps, one ae i a tims decodes Voxecute the code for each step, unti : ag on the tape of UTM. P. I the code for the final result is Observation 2. A Turing machine Tm desi ci i soblem P aM easily be specified by 'm designed to solve a particular (j) The initial state say qoy,, of the Turing machine M. (ji) The next-move function 8,, of Tm, which can be described by the rules of the form : if the current state of Tm is q; and contents of cell being scanned are a; then the next state of Tm is q, the symbol to be written in the current cell is a, and move m;, of the T: Head be To-left, To-right or None. orl etaa aaa aa Thus, each of these rules for a particular Tm can be specified by quintupoles of the form (q,, 4; ,, m1). And hence the next-move function Bim for machine Tm is completely specified by the set. Adis Me Fae Bae MY 2 ir I © Qi ip Mar © Pi My E {To-left, To-right, None}} Observation 3. Next question that arises in the context of the construction of universal Turing machine, is about the number of distinct states in UTM and number of distinct inputs/tape symbols required in the UTM, so that it can solve any solvable problem. ‘As UTM should be able to simulate each Turing Machine, therefore, it may appear that number of distinct states and number of distinct tape symbols in the UTM, should be at least as much as is possible in any Tm, because UTM may be required to accomplish the task of any Tm. However, by proper coding techniques we may use only two symbols to represent set of symbols. 10.12.1. Rice’s Theorem 1. Partial Functi In mathematics and computer science, a o partial function, from the domain X to the co- x domain Y is a binary relation, over X and ¥, which is functional, that is, associates with every element in set X with, at most, oné element in set Y. If a partial function associates with every element in its domain precisely one clement of its co-domain, then it is a “total function”. Note that with this terminology, not every partial function is a “true” function ._ This above diagram does not represent 4 fig, 10.36. Partial Function well-defined” function; because, the element 1 in X, is associated with nothing:236 THEORY OF AUTOMATA AND COMPUTATION, 2. Primitive Recursive Function Primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability, They are defined using recursion and composition as central operations, The primitive recursive functions are a strict subset of the cecursive functions Definition Primitive recursive functions take natural numbers or tuples of natural numbers as arguments and produce a natural number. A function which takes 1 arguments is called n-ary. The basic primitive recursive functions are given by these axioms: 1. The constant function 0 is primitive recursive. 2. The successor function S, which takes one argument and returns the succeeding number as given by the Peano postulates, is primitive recursive, 3. The projection functions P,", which take n arguments and return their ith argument, are primitive recursive. More complex primitive recursive functions can be obtained by applying the operators given by these axioms : 1. Composition : Given f, a k-ary primitive recursive function, and k Fary primitive recursive functions go... g; 1, the composition of f with go, ..., 8, _y, ie., the function K(X, = SGX» 8k -1% --» %)_,)), is primitive recursive. wMLy ah oe 2. Primitive recursion : Given f a k-ary primitive recursive function and 8 4 (k + 2)-ary primitive recursive function, the (k + 1)-ary function defined as the primitive recursion of f and g, ic. the function h where FO, Sa oy Ba) = ft os Xk 3) and HSH), yyy X43) = gl, Xp, Xp od My Xyey Xy_), is primitive recursive. A function is primitive recursive if itis one of the basic functions above, or can be obtained from one of the basic functions by applying the operations a finite number of times. 3. Recursive function In computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are “computable” in some intuitive sense. In fact, in computability theory it is shown that the Tecursive functions are precisely the functions that can be computed by Turing machines, Recursive functions are related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions, Not every recursive function is primitive recursive as well-the most famous example is the Ackermann function. Other equivalent function classes are the A-recursive functions and the functions that can be computed, by Markov algorithms. Definition Take as axioms the axioms of the primitive recursive functions, but extend the definitions so as to allow for partial functions. Add one further operator, the least search or unbounded search operator, defined as follows:» 2, then the function i i i i ny then th bux f is the partial function with arent 21 that returns the least x such that f(O, 2, Zp, oe 2y) fl, 2 ), worf Qs 2 Zar oe Z,) ae all defined and f(x, 24, 23, «1 2) = 0, if such if nose x exists, then pix f is not defined for the particular yen Iris easy to see that this least search axiom (along with the simple primitive recursion axioms) implies the bounded search axiom of primitive recursion. ‘The set of partial recursive functions is defined as the smallest set of partial functions of any arity from natural numbers to natural numbers which contains the zero, successor, and projection functions, and which is closed under tomposition, primitive recursion, and unbounded search. ‘The set of total recursive functions is the subset of partial recursive functions which are total. statement of Rice’s theorem Rice’s theorem is an important result in the theory of recursive functions. ‘A property of partial functions is trivial if it holds for all partial recursive functions or for none. Rice’s theorem states that, for any non-trivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is undividable, ‘As an example, consider the following variant of the halting problem: ‘Take the property a partial function F has if F is defined for argument 1. It is obviously non-trivial, since there are partial functions that are ‘defined for 1 snd others that are undefined at 1. The 1-halting problem is the problem of deciding of any algorithm whether it defines a function with this property, ie, whether the algorithm halts on input 1. By Rice's theorem, the 1-halting problem is undividable. 10.13. THE HALTING PROBLEM [RTU 2007] Tet assume that we have given the description of turing machine Tm and an input w, when started in the initial configuration qow, perform a computation that eventually halts? Using an abbreviated way of talking about the problem, we ask wheather Tm applied to w, of simply (Tm, w) halts or doce not halt, The domain of this problem is to be taken as the set of all turing machines and all w; that is, we are looking for a single turing machine that, given the description of an arbitrary Tm and w, will predict whether or not the computation of Tm applied to w will halt. We cannot find the answer by simulating the action of Tm on w, say by performing it on universal turing machine, because there is no limit on the length Of the computation. If Tm enters an infinite loop, then no matter how long we Wait we ce naver be sure that Tm is in fact in a loop. Tt may be simple case of Very long computation. What we need is an algorithm that can determine the correct answer for any Tm and w by performing some analysis on the machine's description and the input. But it is clear that no such algorithm exists. In short halting problem is : To determine for an arbitrary given Turing machine Whether Tm will eventually halt on input 1. a and input w,=: = ._ 238 ‘THEORY OF AUTOMATA AND COMPUTATION 10.14, UNDECIDABILITY/DECIDABILITY , We know that recursive languages are those languages which are accepted by atleast one turing machine and these sets of recursive languages are subclass of regular sets, called the recursive sets “A problem whose language i recursive is said to be decidable”. Otherwise problem is undecidable. That is, a problem is undecidable if there exist no algorithm that takes as input an ance of the problem and determine whether the answer to that instance is “yes” or “no”. 10.14.1. Facts about Turing-Decidable and Turing Acceptable Languages 1. If L is turing-decidable then L is turing-acceptable Proof. If m decides L, then the turing machine >I i) Fig. 10.37. accepts/semidecides L. That if Tm decides L, we enter into either state ‘Y’ or ‘n’. > If Tm halts in “Y’, this machine halts (because if w € L, Tm goes to state Y and halts). So clearly if L is decided by some turing machine Tm then L is also accepted by some turing machine. 2. If L is turing-decidable then so is L. Proof. Let Tm be a turing machine such as : tm Lon y Fig. 10.38, This machine goes to a no (n) state when Tm ended up ina yes (Y) state and vice-versa. Therefore, there is also a turing machine which decides L (complement of the language L). 10.14.2. Turing Acceptable We know that a turing machine Tm accepts w € 3* if Tm halts on input w, language L is turing-acceptable if there is some turing machine that accepts it. “Let assume, given a countably infi Tm,, Tm, T te number of turing machines Tm), ~ Tm; ... and language L is turing acceptable if at least one of the cepts (halts on) any w € L”. But the question is how do we know or discover which Tm, (if any) accepts L. If we start testing Tm,, Tm,. ete. If Tm, doesn’t accept L it will never halt. Yet, how do we know that if we run Tm, long enough it would not eventuallyr 1g MACHINES wail 7 $0 the issue comes down t << Tene machine will on ¢ would like to be able to accurately pee ict fecany) curing methine ed halt on input w. If it were possible fo pe ie chine ara rental any input string whether or not that uring le language would also ie y alt on that input then every turing weepl ’e turing-decidable. Some authors call Turin} eepiable Language as Recursively Enumerable Language also. ie 4.14.3. Turing-Acceptable Vs Turing-Decidable Consider the language Ly = ("Tm" “w" : Turing machine Tm accepts w] Then let us see some points : (1) Ly is turing-acceptable (by definition) : There is a machine, Tmo (a variant of U) Which accepts input = “Tm” “w’ such that Tm accepts input wv. (2) So if Tm accepts w € L then Tmg also accepts “Tm” "w" € Ly (3) Lp is like infinite dictionary : By = {Ti “ty, "Tay" "ay", Tm" “aso “TM” Haag, oe TM" "Way", “Tmg" “39”, a dictionary which contains answer to questions : Does arbitrary turing machine Tm accepts input w ? Because to answer the question we (a) look in the dictionary to see if Tm is paired with input wv. (b) If Tm does appear with w then Tm accepts w, else Tm doesn’t accept w. (4) So Ly is formulized version of the halting problem because for any arbitrary Tm and w, we could just examine Ly to see if "Tm" "w" € Lo But since Ly is infinite, if we don’t find “Tm” “ww”, we will never know if we have searched long enough. However, if we could answer the question in general is "Tm" "w" € Ly. But Ly is not turing-decidable = the halting problem is not solvable. 6) (6; (7 For specific Tm, w we could predict whether Tm will halt on input 79 that is : (a) could see if Tm has any halt state (b) for real simple Tm, w. But there is no completely general method that correctly decides all cases. Now on the basis of above discussion we can understand that in the case of a Language L which is Turing Acceptable Language but which is not Turing Decidable, there may be a Tm which halts on a large number of strings W, Where W ¢ L, but there must be at least one string WW ¢ L on which Tm does Not halt. Similarly, in the case of a language L which is not Turing Acceptable {and hence cannot be turing decidable), it may happen that there is a Turing machine Te hich say halt for a large number of inputs W which belong to L But there must be atleast one string W € / for which M does not halt.