a Tia we Machine enertly the fie contro conti the fine avons wih th ate rmstions the fie come Turing machine repress teat tsa. Bur hee he orgs of ir go The dat long with he stale So here we use the finite eno 0 hold finite amount of dts ana stare a 7 » sone [a | # | € * Fig 7.2 Turing Machine with storage in finite control ‘This type of Turing machine makes the state to remember and to have a memory forthe symbol inthe input. From the above Turing machine, the state js , and this state q contains A, B, Cas the in storage with q + This type of Turing machine can be designed to store inthe state with any data from the inp Each state contains the “B" blank symbol as its storage intially + This type of Turing machine is used to store any symbol in the input and to check whether stored symbol appears inthe input. 7.6.1 Problems for storage in Finite Control: a e 1) Design a Turing machine to accept the string 919400) orm 10 Solution: Step I: Idea of Creation Here we have to design a Turing machine such that it should accept the strings such as, OULLL, 1000. «te. So the string should have the first symbol as ‘0’ or ‘1° and it should not appear else wher the input. Steps: |. Atstate (inital tate) (, B), if it finds ‘0° or 1, it stores in its state without replacing and right and enters the state q, % At state {q,], iit finds "I, then it skips all 1's and moves right and remains inthe same st Atstate[q, 1, it skip all '0's and moves right remaining inthe same state Atstate[q, 0, if it fnds B, then it reaches the accepting state (q,B] Atstate [4,1 if finds B, then it reaches the accepting state [9,, B] ‘UNIT 4 TURING MACHINESeae consisting of 0's and 1°S and £0 reptacy e strings consisting Place a5, 2. Design » Tring machine to rend th 1 sh 8 pits memory, ft finds 5 is repeated (ntl the Bln D Serato cof Creation i nachine ist initial stat ns proce Step 1 ‘The idea to create this Turing Oty st Similarly if it finds ‘1°, it replaces | bY 1g’ as 1 and go to the stat hen replace ‘0° as I “tao 7 1 reached. ; Tat initial state (a, 1), if it finds *0" finds ‘1, replace 1 by ‘O° inds ‘0, then replace 0 10 ds 0 and (9s moves right. ‘Step 2: The transition Table is shown below, State 11,9,R) ({9,+ B1,B,Ry + fag +B) | (ta, 01 td (18> (fay 90) o1eR) Cay 21 40-R) (9y > BI BR) fa. faye) [Cfay 01 oR) (fay 21 ,0R) (Lay, B1B.R) #14), B) ‘The Turing Machine definition is, M=({idy Bl, 14, 91, [q,, 11,19, BI (0, 1}, (0, 1, B}, 3, Iq, Bl, B, fla, BIS) {4 B) > Initial State, [g,, B|> Final state Where 6 is given as lone ! 8 (Ca, B}, 9) =({4,, 0}, 1, R) 4 (fq, Bl, 1) (14,1, 0, R) 5 ((4,, 0.0) ={q, 0} 1, R) 8 ((4,,91, 1) =(iq,, 1], 0, R) 5 (lq, 0}. B)=(q,,B], B, R) 5 (19), Uh, (Eq, 1, 0, R) 5 ((4,, U0) =((q,, 0}, 1, R) 6 ((4,, 1, B) =((q,, B), B, R)re trnnstion Dingray i, ¥ 17o— k Intis Turing machine, where the nite contol gona the state and its storage and the input tape contains multiple tracks. fEschirack in the input tape contains one symbol ‘Tie tape alphabet of the Turing machine consists of tuples with one component in each track and ‘temumber of components in the tuples depends on the numberof tracks of the input tape. Forexample in the above example the cell scanned by the tape head contains the symbol [X.Y.Z] ‘Tiemuliple tracks of Turing machine is used to find whether the number is odd or even. ‘The Mauliple tracks can also be used to check whether the number is prime, / Saat 7 7.3 Turing Machine with Finite storage contrat and multiple tracks ces,tgning Turing machine with multiple tracks: Ie unacks to cheek whether the £i¥e" Input number 7.7.1 Example for desi 1) Desig Turing Machine w machine fd hte bet marr ro a re tint be ner se Tee ie nay n cod ik ope oe Oe py se rng maine we onary orm Now il we get ‘O" of any remainder. “me mince the rime MUMDCTtoewg Tank also. All the symbols i 1d track value is ineremented by | on ig ded a ee mt non zero vale, then the sega scion procedure continued a os rack x equal then the number is me ruber. Lat gag 217 the value of input valve 7 and itis stored as, Now process is as follows, Subtracting 2 from 7, we get ‘The Remainder is 3, so increment the value of second track by |Be aie nost Oe JS5e (pas Ai ofet-—lelelel= orale 7fel— Jelels|[= Remainder is 2, so increment the value of second track by |sein equal, so the umber 5s 8 Prime number Nn ow the vale of ist and second trac BEATE on dviing2 fom 6, we get ten by subtracting 4 by 2, we get? and agin by subtracting 2 0 Since the remainder i 0, the number 6 is not a prime number (eee ena ‘The Moltape Turing machine has a finite contol state and some finite number of tapes, Ea: multiple (or) multtape Turing mac Filan Tug machine shown below, all ye 488 UNIT TURING MACHINES ee oa hine is divided into cells and each cell ean hold any srBere on at ABS snc than he rs tape ne comps Boa | Set ns Move. dhe Multitape turing mach ime does he fllowing. pe finite control enters afew state bic tape ne tape symbols writen on Biers tape ond tates amore whch canbe eich He tre heads move independently or stationary a = atm emer ‘Siferent directions and Some eres ‘machine can be extended by using ch 1cking off symbols. This method i sed by the Turing ma set tanguages tat contains the repeated sings ad to empae the wo su 4 2 and to compare the length ofthe to subst > (wew,/ w={2,D}*) P= tw w= t0. 1°) the fort w=(0. 13°) Problems for checking off symbols: to recognize the language L= {wew /w = (0, 1}") 7 torecognize he language wew is that we ae going to Se NSE Tar represent the sa 25 [4B] where he ist conenes’ eis the stored symbol. To construct he Turing anil we read the symbol“, and we check 19 Symbol chen we move eh afterrot ee HR) OILY OLA ek RD ALAM OEM Gg ea fen foe nme ae.thmi aXtLmeLD ae - - - — wang, ma ~ = param aso mut GABA gag sab) GL om — RALMGY desmRrOL dee BLI TLD a orm (OLR) UAB = LBL aL BLL — waren — - ABLE ORBLE gpm, ‘The Turing Machine forthe language, L.= {wew /w = {0, 1}*) is given below, M~(Q.5,0,6.q,B,F) Where, Qe 4, 45 4, 4, Ie Me 4, 4 A} X (0, 1, B}) E=(0,1,¢) => ({B, 0) 18 1, Bel) T= (B,*}X (0,1, ¢, B} 4,» B] > Initial State 14, BI-> Final state 1B, B] > Blank symbol ’ Here in this, the input symbol B is represented as [B, B] + '0°is represented as [B, 0} * — ‘I'is represented as (B,1] ‘And ‘c'is represented as [B, c], Here we use the symbol "to matk that the symbolsmavimg— fave (Yr aces Orr raven fave.o) Tere are some problems, in which some same tasks need to be performed repeatedly and it canbe done by subroutines, The subroutines are also called asa function. The subroutine fn the Turing machine isa set of ‘sates that specifically performs some tasks. '" The set of states inthe subroutine has one start state and another state namely the return state, ‘The retum state ofthe subroutine does not have moves and it pass the control to the other set of states of the Turing machine that calls the subroutine. * The subroutine is called whenever there isa transition to its initial state. «The calls are made tothe start states of different copies of the subroutine and each copy retums fo a different state «The subroutines ofthe Turing machine perform some task simultaneously. 2 a ‘UNIT TURING MACHINES 4417.10.1 Problems on Subroutine: m=2 nad a ojaleolole|+i3\— « by Monon eo!| con fo) | B)\5——-- *3=6 At inital state, when ‘0 found inthe input, replace it to “Band move right for searching ‘After finding “1, cal the subroutine to copy the ‘n’ number of 0's for ‘m’ number of rims ‘After performing mn" numberof copy with ‘n° number of 0's, we replace O10" 10 3g {ape contains 0" te 1 ‘Step 2: Transition table for Subroutine Concat program: (ay XR) (gh) = - (408) (ay 1R) = (4g OLY (40,1) (ay 1, L) (yy XR) Epa asteyecaer anit)EEN eet) ‘A Non Deterministic Turing Machines is one in which the transition function 8 is given 38, 8G, XD = 4p ¥pD,) Gye Vp BD nn (y Yq DD} From the above transition, We ean know tha the ansiton for any state withthe tape symbol »C, we ca have many transition. The Non Deterministic Turing Machines an choose any one of the transition move at the state q with the tape symbol "X 4 ‘*The Non deterministic Turing machine *M* accepts an input string ‘wif there is any sequence of choice of moves that lead sto an instantaneous description with an accepting state. ‘The Non deterministic Turing machine accept the languages that are accepted bythe deterministic “Turing machine "Similarly the nondeterministic Turing machine doesnot accept the languages that are not accepted by the deterministic Turing machine. ‘Two Mark Questions - PART A 1. Whatis meant by Turing machi ‘lan Turing introduced a new mathematical machine called Turing Machine during the year 1936. Machine isa tol for studying the computability of mathematical functions. Turing hypothesis bel ‘hata function is computable ifand only ifit can be computed by a Turing machine. 2. Define Turing machine, ‘The Turing Machine can be formally defined as follows, M=@Q,5,18,4, BF) ere, Q Finite set of states & Finite se of input alphabets, ‘44 UNIT4 TURING MACHINESIe cles about Tang Machines ta sve Ye aliowing problems about Turing Machine ar under a ee ae a LP netsh langage accepted by Turing Machine soy Peter the language accepted by a Turn Machng ne Whether he language accepted by Turing Machin ia reel Whether the language accepted bya Turing Machine ts tone fr jf Problems about Turing Machine, we are going oso the fellowing concep, ible Proves TRiSeckalePross epmerting the Binary sing of Ting Machine Wess rte Tring acing ne ‘decidable Problems abou Turing Machine Tloteable Probie of Tring Machine {letsable Decision problems of Tring Machine },1 Decidable Problems fs Decidable if and ony ithere is a Tring machine M sch that Maccpts every singe “Land reject the string that is not the language. The Decidable problem has the algorithm tha ppt and it decides whether the input is accepted or not and it produces the resulta either "Yes" The Decidable language is one when there sa slition. for Decidable Problem: vrtne strings over the alphabet (a,b) that has equal numberof a's and b's ‘The strings over te alphabet {0,1} that has alternative O's and I's 2 Undecidable Language: and we cannot predict whether the input is accepted reeidable problem exist if and oaly if there exiss no algrtim to solve he problem in nie 3.) Soe cannot expect the solution to the problem and cannot predict whether the Turing mast Pe are comma prec for which input, the Turing machin fais to halt in the undecisble : efor undeidae chine M and ay given sting w, Does Mba fore input tn 7 | 2. Membership problem is undecidable. 'M, does M halt on every input string "¥"? For any given Turing Machine | pa ital arta TURNG MACHINES 455 rr‘acon oF comurarion es 8.3.3 Enumerating the Binary Strings: _ In this binary sing enumeration, we songn the integers to al the Way srfONs, #9 thet cacy responds fo one imteger and ech integer correspond ene PH [Exemple: Let‘w'is 4 binary string then treat “Iw” na leary Kaieger “FT bps th ‘Simla. € > Fist ring (0-> Second string 1.9 Thind string (00 > Fourth string 01-9 Fifth string 10> Sixth string and so on ‘So we can refer tothe # string as w, 8.3.4 Codes for Turing machines: [Now we are going o generate a binary coe fo the Turing machines tat each Turing machine Alpe (01 maybe assumed a binary sting. To represent Tring Machine fers 1.95.8, ung, ems fist asin tee tnt sme et Rule following assumption. SS SS ee ont acceping ste, Sines te Turing iachine bas whenever i ener an AECeHng a, will be symbol 0" zabway ree be°B AndJ rwcon oF commurarion jr ora900i010100 [Gode = oT9v OT 0000100 11 OF sie ‘010040010000010 1 1 9010100101 | 4.3.5 Undecidable Problems about Turing Machine: vccidable probes abou ihe Turing mache THe EOE of unde et Turing mAChNes that cen eye ee es eee sat tn an inamcota pin iin hin cman emf es ee = ea ear eae Fig 8.1. "7 {poyes" answer into an instanceof P, fe tumed into an instance of P, with “No” answer and is show Reduction turns positive instances into Figure 8.1 iegative instance to Negative Positive and Ne eamally a eduction rm P,P isa Turing Machine hat ake an instance of Py writen ons rorrn eree oP, dks ape. So the reduction takes an stance of P, a input nd pray insane of P, athe ouput ‘Theorem 82; If there is aredvetion from PP, then 1. IfP is undeidabe, then Sos 2. IfPrisnon-RE, then So is F, 1). “If, is undecidable, then So is P,”. undecidable. I tis possible to decide P, as undecidable, then we can com ~ Here we use an algorithm which converts the instance of P, to instanceof Figure 82 Solving P, using the solution of P, 460 UNIT4 TURING MACHINES‘String w yr, x [> No/ Reject x Algorithm a [> ¥es / Accept —_| ve the problem P. instance™X" of Then Wy ecae wey 1 Yes ~> Xo Figure 8.3 w isan instance of P, and Similarly ifX is notin ,then “wis na inp #SoifX is inP,, then w isin P,andifXis nein P Seif, isundecidable, then Fis also udocidey G2), isnon RE, then SOis , bpeP, is Non RE, but P is RE. Since P. is RE, then w fing machine that says “yes” then wis not in, oo ae ans v0 ‘isan instance o Figure 8.4 Turing Machine Which may not halt fig 8.4 describes a Turing Machine which may not halt andthe language is Pf Wis in P, then this Turing machine will accept w. ‘isnot in P,, then X isnot in P, ‘the Turing machine may or may not halt but will not surely accept w. ‘we assumed that noIM for P; exists, we have shown by contradiction that no TM for P,ex- 2, non-RE, 20, no0 RE, /—_ ee able Problems of Turing Machine: ‘a Turing Machine T, is BE L(T) ‘thatthe Turing Machine T reach the accepting state, Accepts ~ Bis unsolvable .as Accepts ~ B as a decision problem which is specified a, it begins witha blank Tape.problem Accepts to AeceptB a8 = THEORY OF COMPUTATION Proof To prove this theorem , we try t reduce the the input string, We must id fT oa yes mtance of Rice hy | accepts x” and" accepts ‘rand TH ot we ereate a tape with x and, Acces < Accepts 8 fostat with apex) whee T Michie Tso that T9896 rtm th above inference, W & NoSane en theconrcion of Ti bine TT can sat with a tn ing Mash and Meo acces and farce ing Mahe "oy Ts SMe wring se ands denoted ty, TI = wre hat of Fon input and His Cory TRE comps nae at oT 2 Mie sting chine hat as wh ina Reena neo‘? ifand ont CT accept te ms en TI doped on Tring Mocks The Unstable robin Bis Unahabl 8.3.7 Unsolvable Decision Problems of Turing Machine: ‘Machine are as follows, ‘The Unsolvable Decision problems of Tring 1) Accepts Something- Given a TMT, s L(T)isnom empty? 2) Accepts Everything - Given a turning machine TMT with an input alphabet J, and is L(T) = 5* 3) Subset = Given two TM TH and T2,is L(TH) S L172)? ‘Theorem 8A: The Decision problem Accepts something is unsolvable such L(T) is non empty? it, Given a TH roof: We have to prove that Accepts something is unsolvable. This ean be done showing that canbe reduced to Accepts something a, Accepts < Accepts Something Here both the problem are decision problems andthe instance is a Turning Machine (TM) *= We construct Turning Machine T for Accepts B and Turing Machine T! for Accepts something that Turing Machine T accepts B if and only if Turning Machine T1 accepts at least one stn: '*Since TI is reduced from. T erases its input first and then executes the functionality of Td Turing Machine Tis # TI =BraseTape > T = T= 1M for Accepts B *" TL=TM for Accepts Something {Ese Tp sess pt sting and aves the tape ead on square 0. "*€ Tappears with B input tape and it accepts B, the TI will also accept the i Since Turing Machine T1 de : Sear an ee ey iw tar Tr ce Ba ‘Theorem 8.5 : The decision INT ih apa preelaig eermeraee unsolvable (ie) Given a turning md ‘roof: To prove that. ir Accepts Be Accepts Eaecatge ene i unsolvable we try to reduc it from Accepts - Bs "* Create the foll Howing Turing Machine as, T= Turing Machine for Accepts B and Ti =Ts"8 chine for Accepts Everything eeRS <———__ osama Asour ra scan Turing Machine T accepts B ifand only tthe Tring Mi my string inthe ing nd only ifthe Turing Machi V ‘ 8 Machine'T1 accepts any string in the input ‘Are bow that ACcepsB is insolable, the Turing mach 1° T1 with the decision problem Accept a E yt Acc 18 machine 1 with the decision problem Accepts yore 86: ThE decision problem Subset is My SUtay? fot Here let us create a Turing machine a a pair (TI, 12) so thatthe Turing Machine T acceps every _goner te input alphabet Sif and only Lr) S112, nsolvable Given two TM TI and T2, {pare that LIT) S L(T2 is unsolvable, we try to reduce subset from Accept eveything a, -AcceptsEverything < Subset + Now let us create the Turing Machine T= Turing Machine for Accepts Everything and (T1, 72) = Turing Machine for subset % nes ete Turing Machine Tacceps the string w ifand only if L(T1) © L(T2) (ie) every string preset i ‘als present in T2 here TI is the trivial Turing Machine with input alphabet that acepts any input and therefore y=? and T2=T ‘the Turing Machine (1,2) i reduced from Accepts Everything. As we know that Acceps Every- ‘ris unsolvable, the subset TM (1, T2) is also unsolvable. ATEN u rete (Chomskian hierarchy of languages have the following four types of languages ‘Type 0 — Recursive or Unrestricted Language ‘Type I -¥ Context Sensitive Language ‘Type 2 Context free Language Type 3 Regular Language. Content Sensitive, Languagereper: AP stv : Sian al fi either em 1 ch hai is sats by no langue tl or property of the RRE languages is undecidable and Unsolvable mon vil propery of er ck eo en Atma at ty Taupe ney guy tat sin the empty language isnt in Since P ate pom te 5 ving tp snd iP Leiba aig Mac apie Bre Gein! eed yin rade ce coe ecidable and Lnsolvable. The EE Ropuc rate anc te . tM ace ‘One tape is used to simulate M on W. ulate M, onthe input x to M the following, Ee Mon input w.The sting Wnt input rather M' writes M and W onto one of is tapes and simulates the univest Tring Mohn *U" on that par FM does not accept w, then MP ‘does nt perform anything. M” never on ts on input x Ths, MP will accept M isin Lp. seta ant thts in Lp ifand ony if ine peor P| a Usable accepts its own input x $0 L exactly the4 RECURSIVE FUNCTIONS stars] “ven rors] +9 10 “0 cs MPCP reduces to PCP is a solution tothe given MPCP instance with lists A and B. Then, we know 5 oe Suppose ii, WM, Ma‘TWeoRY oF COMPUTATION ” 4 mac instance. THU, there sare, jon tothe alo be decidable. "4 Thuan te PEP instr imple 8 MU pc woul tm CofMPCP m PCR, which confirms that iFPCP jit IM, w) we construct 0.1.44 Completion of the proof of PCP wd hs apron apa cid ere we are goin pa i cnt (A,B olin (Aryan sch aig mate MT gn gf Mom on teiance (A.B) simolates in its pata te Trazumecus Description) IDs of MH Fc, Hs # Where ve > tial 1D of Mwith input: 24, fall ring from the A list, unless M ene, na string from B list will always be one ID ahead of the st ig from _ ee UPC lcmare, ye niece tas ut Tog mati ney" Prine = Bank ay, Ss et fom is initial head postion. ne ‘string of the form c29B, where cn + Inthat case, an ID of the Turing machine wil always be string aq a ‘strings of the of nonblank tape symbols, and q is a state. daa eee ene oye th lank mmeitel 0 the GH FO theron Vega bladko the eho ese ‘Thus, the symbols cr and B. will correspond ex: plus any cells tothe righ thatthe head has previously visited. = Lat M=(0, 5.18.4, ByF) bea Turing machine and let w in 5 be an input string. We const: stance of MPCP as follows (i.e) the frst listo be one ID behind the second list, unless M acc actly to the contents ofthe cell that hed ie Bales, 1) The First pairis, * fagwt ‘This pair starts any solution according to the rules of MPCP, begin the simulat : eee nen es begin the simulation of M on in: 2) Tape symbols and the separator # can be appended to both lists as, Uist | tisee oan (ex 1 lt shove pairallows symbols not involv wae? }) To simulate a move of | Iving the state to be copied. in. X,Y and Zi ‘M, we have certain, gait pars. For each q in Q-F where q is an non accepting st nape alphabets, we have the following lst as,THEORY OF COMPUTATION ar 1 Now i edy to execute, to compute 2) a Heats ally rue au at at to accep for some iwi at 1) fs undetnd ten he esta OFT 0 int I falls 85°F th Q isa So we cold that T oceps the input 1° BI an only fe, ke) defined sods compa toa funtion Measure aneuane PEE | 9.4.1 Recursive Language A language Lis said tn be Recursive Language if 1) If is nL, then M accepts tng state but it halts for some Turing Machine M such that, 2) Ifthe string w is notin L then M doesnot enter accepting . So Lis called cial language ft is Recursive Langsoge Te language Lic ended a guage ifs not a Recursive Language &Yanguage is Recursive Language fs a Tang Me SaaS oct at th Totag Mi see sings tat arin he an raat eae strings that are no'in the language". So if the tring ‘w” i in L, then M acoepss and therefor te Trig, ‘Machine halts. — 1 Input string W Fe nett ‘Machine ME Reeuxe Figure 9.5 Recursive Language ‘*1Fw isnot in the language L, then M hals without entering the accepting state; ‘*So any problem or language L is decidable, i tsa recursive language. ‘And any language is undeciabe, iis not recursive language. 9.4.2 Recursively Enumerable (RE) Language: ‘The language defined by the phrase structure grammar is known as Recursively Enumerable la ‘Alanguage is Regursively Eauierbl if thee exists a Turing Machine that i in he lnguage and does not accept the sti inthe ‘machine to eter into an init Top. it may cause the see ye be fae ae [> Reject /Iatinite loop “0 UNITS UNSOLVABLE PROBLEMS AND CONPUTABLE FUNCTIONSx ay ami ‘RECURSIVE FUNCTIONS Recursive Lay Recursive Enumerabie Figure 9.7 Relationship of Recursive and Recursive Enumerable Language 4.3 Relationship between Recursive, RE and non RE languages: Turing machine that snot uaranted to halt may no give us enough information to conclude that the isnot in the language. So now we ate going to divide the problems o anguages fellows "Decidable or Recursive language: Those languages that are solved by an algrithn, ‘*Undecidable language: Those language that hes no algorithm and it has wo types and they are, 1) Thelangunges that te RecasivelyEnumerable bt ot Recursive Tha he Trng acco ‘tw is inthe language else it goes into an infinite lop) 2) The languages that are N sursively Enumerable those that do not have Turing machine at all. The Relationship between these classes of languages are shovin below, | La Net Recersve slready know that any language is recursively enumerbl if the Turing machine accepts the stings that inthe language and rejects and go into an infinite lop forthe stings that are not inthe language. So we bingo find the languages that are no recursively enumersble. Generally any language “Lis Recut y Enumerable (RE) if and ony if there exist a language L' such that L=L(M) fr some Turing Ma 1) Misa Turing machine with input alphabets (0,1) P “tsa string of and 1's and isthe input string input string ‘w""THEORY OF COMPUTATION a so undecidable. There is ire above poblem i uncial then he Twin chi 1 ring machine represen a te Micon al the stings #0088 a wo Turing mach 9 Soc acy ip sting WA he ignitor anung ven So eit Cenrly proving that there no Tung MACHA tt wee eave han proving thm the ange a vdecnble. NOW NE that el RecusivelyEnumerble 9.4.5 Diagonalization languag Definition: The Diagonatization Language Ls th an isnot in L(M) where Ms the Turing machine. The et of stn pe are some integers which do not correspond to any Turing machine at all ee oh Bm stot vga ‘code. We shall take the Turing machine M, to be the Turing Machine with one tl Tt No transit Thats, for these values ofthe ttn machine M, immediately halls on any input * Thus the Turing machine L (M) is if, fis to bea valid code of Turing machine M, *Somnow we can conclude thatthe diagonalization language consists ofall tings” Such ‘Turing machine M whose code is ‘w" that does not accept when w is given as input. a [Now consider the following example for the diagonalization language “Ld”. The diagonalizatig guage table in the figure 9.9 shows that for all values ‘i’ and ‘j, whether TM M, accepts the ‘String iy ea | *16(i,3)=1, them M, accepts the string and tells “yes”. *1F()=0, them M. doesnot accepts the string and tells “No” The # row is called the “agonalizaton characters Vector” forthe Language L (M). The sg row inde the sings hat ae member fs angunge The dagnal values els Wht i am Reta, the string w, or not, To construct the diagonalization language, we complement, The diagonal sting is 0111 Camoleene agonal ang Lats 1000 oom the above complemented diagonal 100, the lang = an ite ve olen gral 100 ng Ld old atin WIE an ie etainen, Se ac al ms4 wre? AecUnBIVE FUNCTIONS 2 - 2 \ gb Diagonalization: perros: of complementing the diagonal io construct the characteris vector of language tat canner i 0 i called diagonalization. Thus th complement of the dingonal er ng the membership in some language Ld. So the complement ofthe Ieee cannot be the characteristic vector of any Turing machine « 447 Diagonalization Language ‘Ld’ 9.12: Lis not a Reca pe sccepts La. Prove: Thee is no is not Recursively Enumerable: sively Enumerable Language, That is there is no Turing Macl 3 Machine that accepts the diagonalization Language “Ld. fe Suppose Ld is accepted by some Turi ing machine M defined by L (M). Since Ld is a language over {0, 1} M would be in the list of Tur ase W, cam neither be in Ld nor fail to be in Ld, we conclude that there is a contradiction of our assump- that M exists. Thus, the diagonalizati ion Language “La” isnot a recursively Enumerable Language 8 Undecidable problem that is Recursively Enumerable (RE): + lgorthm and not only recogniaes the language but also els whether the string isnot inthe language. uch a Turing machine hal whether the input is accepted or not, it reaches the final state or accepting stat. 9) The second cases of languages consist of hose RE languages that arent accepted by any Turing chine he put sigs the gue teaches alt, tite ip srt eae ‘guage, then the Turing machine go int infinite loop. 9 Properties of Recursive and Recursively Enumerable languages: we are going to see the complement ofthe recursive and Recursively Enumerable language. ‘f+L’is a recursive language, then Lis also a Recursive Language (on Ls recursive language, so L” (On) complement of recursive language is also recursive language, Prove: If Lis recursive, then Lis also recursive language, ee The complement of the languageTHEORY OF COMPUTATION 1 that always hat (Mt for some Turing machine sys ae Lime na uch that (= 1M ang Let -L isthe tnguage (Le) L i r wring machine ‘Let us construct the vomplement ofthe TW shown below. Turing Machine Mt string W aR al re Mf? Reject jon of M- accepting the Compl Accept ment of M Figure 910 Construct jus behave ike M. The Turing machine Mis constructed as f110¥E 1 ye Accepting states of Mare made as non accepting states oF, 2) MP has ane accepting state and thee are no transitions fom 7 5 rorcch pa o ne seeping cof M, and tape syabol of M such that M bas nana then adda transition othe aceping sat‘ of M {since Mis puranteed total then Mls uarnteedto bat The Tring machine Mex sy thos tings tha ae not accepted the Turing Machine M, Thus M accepts L) CAEL So the complement of the recursive language ‘Lis also recursive. th no transitions | ‘Thcorem 9.14: Ifa language Land L’ are Recursively Enumerable (RE), then Lis Recursive (On Ue both ata ‘and its complement L’ are Recursively Enumé en Li Ee 1 its complement L’ are Recursively Enumerable (RE), then Lis recusiyg ‘To Prove: If Land L is RE, then Lis Recursive Proof: Let L= L(M,) and L’ = L (M, for some Turing machine M1 and M2. Both MI and M2 ated in parallel by a Turing machine ‘M". And itis shown below, ~~ ae Accept String Wye above setZ isthe union of th I two countably infinit ‘wo sets (0,1, sean 7 OUT nites (0.12 Vand (12ers) Biornd aaa " - clude the PrOOE the union oF Wo coun "ably infinite sets is also countably infinite 8 cl ye Countable, then S,— is uncountable. arty the set of languages that are not recursively , that are secursvely enumerates “USER enumerable is much bigger than the st of soany sof IANEUAEES Over the alphabe othave the tring machine to accept it sesetof languages over {0,1} that are not RE languages wil also be uncountable, Meee : sivesal Language “Lu” is the set of binary strings tht encode a par (M, w) where M isthe Turing ‘imi inary pstalpait and wi aren) Serdang in) Te al Luis the set of strings representing a T Turing machine ‘Mandan input accepted By that low we are going to show that there is a universal Turing machine UV such that Lu=L (U). tees Ting Machine ‘Ui Used ss mulap rng mane tnd shown n 4913 | Bei rsisend of M srg wth cpt ng eeepc tole he simulated tape of M asthe code of M. The tape symbol X of M will be Bp edi lpetycl vi py sg sTrethind tape of U hold the state of M with tate g, represented by 0 “i *s (0.1) that are not recursively enumerable languages will (OaTHEORY OF COMPUTATION —_—_ ~~ 9.5.1 Operation of Universal Turing Machine: jas follow heat ‘The operation of the universal Turing machine i ali code fr 0 1) Examine the input o make sue thatthe code For M teh oa AR xing in ended Tht for ec 2) Inte second tape cata te PN od tape The a \ place 100 inthe second tape and foreach of ¥ Ps tape. All the cells beyond those useq yu Mt tape is represented by 1000 and will not appeat OF . willold the blank of *U “i 3) Place 0", the start state of M on the hd peo $21 Tring Machine) ston ae toh Br ape fr aration, 0°1 01 081.01 Or ay simulate a move of M, searches ont fist tape for a mieieir: . i ‘tht one yan ie tae bol of tha Bei a the Peston {ape 2 samedi Ucthsthenexttrariton that M mist make andthe "U'make the KOWE, i. Change the content of tape 310 To do this, U first changes ans ang then copies 0 from tape It tape 3. ‘ of M. ii, Replace O'on tape 2 by 0, that is change the tape symbol m=I(left) or m=2 (right), Thus 'U' simulates the move of Mt the le shox ae 5) 1FM has no transition that matches the simulated state and tape symbol, then no transition ig found. Thus M halt in the simulated configuration and ‘U’ also performs the same, 6) 1FM enters its accepting stat, then *U" accepts. SoU" simulates M on the sting“. U accept coded pair (M, w) iTand ony if M acceptsW'- machine, head af he U's Turing Machin (pg 9.5.2 Undecidability of the Universal Language: Here we are going to sce the Lu tat is RE but not Recursive, The Ld language is not RE. The Reason the reduction of Lu to another problem P can be used fo show that there is no algorithm to solve Pra ‘of whether ornot Pis RE. However, reduction to Ld to Ps only possible ifP is not RE, so Ld cannot be to show undecidability for those problems that are RE but not Recursive. So Lu is RE and La isnot RE ‘Theorem 9.20: Lu is Recursively Enumerable (RE), but not Recursive. Proof Assume that Lu is Recursive, Therefore the complement of Lu is Lu’ is also Recursive. If we havea ‘machine M to accept Lu’ then we can construct a Turing machine to accept Ld, Since we ales: know {isnot RE, we have a contradiction of our assumption that Lu is Recursive. Torben striagw = = i ‘wittw. ‘Hypotntia ai: i Algor St tore Firs ACEH Reet | v Lv Accept Reject Figure 9.15 Reduction of La to Lu*Gown WL (M) = La’, then we ean modity 1, plows, 1) Given string °* om its input, M ch Yo copy ‘wand then convert the tw 2) M’ simulates M on the new input, I {ips Me Since M accepts La, it will accep if and only i Ld ion, then M determines whether M, a. Mi does not accept w, such that , fn Aes Masse ifand only iwi in Li, Thus we ean conlue hat Li not Recursive ‘Two Mark Questions - PART A. J, What is meant by Solvable Problem? los be resonable encoding ofa decison problem Poverthe alphabet « ecidable only it ¥(P) = eh) 1g ‘ayes-instance of P} and Y(P) © 2 Define Le and Lne, then the problem Pi solvable I? isa recursive language Non Empty Language “Lae”: if (Mi) ¢ 4, then w isin Lne. Thus Lne isthe language of all codes for Lane machines that accept atleast one input sting, Lae RE, but not Recursive. Le is non RE Lne=(M/L(M) #4) What is meant by NSA and SA? Self Accepting Language (NSA): = E(0,1)¢/W = ECT) Some Turing Machine , and the Input String w € L(T) Accepting Language (SA) The Set Accepting Language (SA) i defined a, ‘The Non Self Accepting Language (NSA) is defined as, SA=(wE(0,1}*/ w= ECT) Py such hat iit satisted by no language at Trivial Property: A prope i sid tobe non Tvl fit isnot py ats meant by Computable functions? {unetons that are computed bythe ting machine ar ealled computable fantions. The Uncom- faction of solvable problem are the character fnstions of an recuse npences is meant by constant function? Functions: For each K >0 and each a> the constant function C*:N* —> N is defied byTHEORY OF COMPUTATION. ae For this above non-deteministi procedure, we can simulate & track of stack as "Activation records” For executing “return ‘eject state, The above procedure also executed in polynomia time time, then ts given. T(r) Se(logny’ + ETP) [By inductive proof, we have to show tha, | Tia) Se (log ny" From the hypothesis, we have to show that, elogny! + 3 e(logP )"*' < e(log ny" lies cilogn +Zetlog.y" Teneurns Gees 10.5.1 The classes P and NP: The Two moran pins aoa he problems 1 the pbles stable plum ine on typi compere exaty he same hepa Iems able inpobmomia tine on Trig machine 2. Exprene ta shown ha te dviding ne between problems that can be solve npoboia time and hos tt eq eonenal ine or more uit nda “The problems solvable in polynomial ime by deteminstic and non deterministic Turing Machine respec- tively andthe technique of polynomial time reduction are involved inthe classes of P and NP problems. [NP completenes is «notation tobe given othe NP problems which has a property that they are withina polynomial in ime. oe ofa = Definition: The problems solvable in Polynomial time by Deterministic Turing Max chin is called Class P Problem | ‘CLASS NP Problem - Definition: The problems solvable in Polynomial ime by Non -Deteministic Tae ing Machine i called Class P Problem Ve x ‘CLASS NP Complete problems - Definition: A language ‘L’ is NP complet fit satisfies the following statements. isin NP 2. For every language L’ in NP there is polynomial time reduction ofthe language L 10 l.rer 10 i sauna ino cLAserrn cour tery “Ue NPcomplte LE NPand NP NPeomplepetens 2 B Soreling leon peter exer len Seat regen ptm ‘Zanuiy ee pemeleeesoe nw eey gughM dc Lipsy ne 5.2 Problems solvable in Polynomial Time: ig Machine M is said tobe of Time Com, 1, M halts after making at most T (n), A language Lis in class “P™ if there is some Turing Machine M of time complexity T(n) 5.3 Class P Problem - Kruskal’s Algorithm: Fen Sr cachnode the connected component in whch node appears sing what ever edges ofthe [ree have been selected so fa. Maintain th # connected component ofeach node. Initially every node is laconnected component by itself, {ertthe edges of the graph in ascending order, {let the lowest weight edge that has not been visited, "Select that edge. ‘Merge the two connected components ‘he tep3 is repeated untit all edges ae visited. [be Total Time taken is, © (e (e+ m))) Where e edges m> nodes. (ier the following graph and find the Minimum weight spanning tree MSWT [UNIT UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS S13 oy‘Tony OF ComPUTATION —— Solution: ‘i The edges with the weight in ascending onde G.a)-10 us flows (21s aan 10.5.4 Implementation of Kruskal’s algorithm using Turing machine: ‘When translating the loge of rusk’ algorithm tothe Turing machine, we encounter te oll Jems, ‘The output of MWST isa list of edges. But TM wil give only 2 answers (yes “or” No) ati ‘ep’ or *Rejec’. So the problem ean be refined as “Given the graph G and weight sos ‘spanning tee of weight w (or less? 514 OMT UNOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONSVa pratt alert is ven py ting CIDE, 180 Sing ye ge 2S OT BTIPH ag ihe Fas WH lectin ey 8 Mabe we nd es. tin te Fie aifference between the ging it" the “edi he Size as 94 MEASURING AND CLASSIFYING CompLExITY arte wing ne meaaune eo ihm ofthe yan oad Da dno poor. logarithm ofthe integers size ang, PMA Node rerio for any ode. gs Example Problem for NSW usin gshfllowne an fd NST ig 18 Turing Machine: uring Machine ion: ‘pits given as code for the graphs and wei chess and comma, sepsare, ight limits, The code has five symbols as 0,1, lef, right |: Assign integers 1 through m tothe nodes 2, Begin the code with the value m in binary andthe weight limit win binary that is separated by comma, 4, Ifthe is an edge between nodes i and j with weight ~w’, then place (i,j w) in the code, The integer i,j w ate coded in binary. The order of i and j within an edge andthe order of the edes within the code are immaterial. The codes are, 100, 101000, (1,10, 1111 (1, 11,1010) (10,11, 1109 (10, 100, 10100) (1,100, 10010) 5.6 Construction of Turing machine for kruskal’s algorithm: ‘uning time of kruska’s algorithm implemented in a Turing machine sO (@), Here we use mulitape ‘ngmachine. * We use multitape Turing machine in which one tape canbe used to store the nodes and heir curent ent numbers. The length ofthe tape i O(n), sharp can be used sean heeds on he nat tape an ante ape can be seo ok the curently least edge weight found among those edges that have no been visite. ‘Dw = UNGOLVABLE PROBLEMS AND COMPUTABLE FONGTION® SIS| THEORY OF compuranion: wie weigh Aptiocaig. rei cies that were selected the The second track ofthe input tape is used to mark those ede dee of reoanig oh Sable aes ad + Aer eecting on dg, plas two nodes ma ae Ser mpg, tal tceemenen et estrone Te aig yy «Renee lint een eA ei nave pevty come component component umber changed 1 Thi ‘and each node found to be in component have its compe san takes On) time, 10.5.7 CLASS NP Problem - Non Deterministic Polynomial Time: ‘The clases of problems inthe stay of itactabilty ints ase a ‘comin Tring machine that uns in polynomial ime. We ay angus 1 te Dexmnisic Polo) thee mondtermiitic TM M and 2 Cee ae such that = L.(M) and when M is given an input of length n, there are no sequ “ner tha complesiy (a) moves of [rene] NP contains many problems not in ‘The Reason is that a NTM running in polynomial time has the ability to guess an exponen, ter of posible solutions toa problem and check each one in polynomial time in paral * Whether P=NP, such that whether infact everything tha canbe done in polynomial ime by «an infact be done by a DTM in polynomial time witha higher degree polynomial 10.5.8 CLASS NP problem - Traveling SalesMan Problem: Traveling sales man problem is the same as that of MSWT problem. The input to the TSP isthe someag MSWT, a graph with integer weights on the edges and a weight limit w. The question is whether he has Hamilton ciruit of total weight st most the limit w? ‘The Hamilton circuit isa set of edges that connect the nodes into a sin Pearing exactly once, 1 The numberof edges ona Hamiton circuit must equal the numberof nodes inthe grap ‘inthis TSP, salesperson has to vist each venexenaelly once and retum to eae ‘minimum distance. bs Conse the flloving raph gle eycle with cach nage, PingMEASURING AND CLASSIF piehe= 15420618 + 10-63, p> 63. then the answer is “Ves #63, then the answer is "No an M-node gy ‘i ter, it “ raph, the number of distint cycles grows as O (m). For a non deterministic compu ie So cing ewes £ Permutation ofthe nodes und compute the ttl weight for the ele of des in tha frome tne ste NTM, ts pombe guess permutation nO rape and esa ta weg pe sme time. Thus TSP comes under the cass NF EAR OGTS Rae }6.1 Definition - Polynomial Time Reduction: Reductions from P, to P stance. The P, instance et be solved in polynomial time in P, to P, Arya ime if tkes time that is some polynomial inthe length of the {ength tha is polynomial in the length of P, instance. A problem P ‘can be proved by the reduction of a problem P, which is known not oan 2tOve, if, is in Pthen P is also in P. When P instance length is M, output is 2" which is FP, #8 also in P. When P, instance length is hick ie repectical polynomial time algorithm for Ps Hehe jon algorithm run in © (n) time, then O* an Igo If the decision algor @) ° which is exponential in M. Inst: stance Ta No. Fig 10.1 Polynomial Time Reductions Reductions: ty know that, “L1 is reducible to L2” ifthere is a computable function so that checking whether equivalent to check whether f(x) € L, is no harder than L, can be tested in two ways by computing t* and testing membership in L, e statement “no harder than” can be distinguished by possible and impossible. s esting the membership of a string in L, is possible, then testing a string after computing “fis also sible, > reducing function ‘f” should be computable in a reasonable amount of time which sing 4