COMP481 Review Problems Turing Machines and (Un ...

1 COMP481 ReviewProblemsTuringMachinesand(Un) ,I regularlymake useoftwo Problems ,namely TheHaltingProblem,denotedbyHP, andde nedasHP=fhM; wijMis a TMandit haltsonstringwg. ThecomplementoftheHaltingProblem,denoted byHP, andde nedasHP=fhM; wijMis a TMandit use decidable and recursive interchangeably, anduse semi-decidable and recursivelyenu-merable interchangeably. I useR forrecursive, : m denotesmappingreducibility. Forexample,L1 mL2means L1mappingreducestoL2 . show a languageLis notinR (notinRE),it suf cestoshow thatL0 mLforsomeL0thatis notinR (notinRE).Fromthetheoremwe've learned,it followsthatLis notinR (notinRE). mLis equivalenttoshowingL0 's Theorem(theversionI use): LetCbea proper, ,thelanguageLC=fhMi:L(M)2 Cgis notrecursive. So,toshowa languageLis notrecursive usingRice's Theorem,I picktheappropriateC( ,aCsuchthatLC=L), prove that(1)C RE, (2)C6=RE, and(3)C6=.

2 Finally, I concludethatLCis ,statewhethereachlanguageis(I)recursive, (II)recursivelyenumerablebutnotrecursive , or(III) youranswer. L1=fhMijMis a TMandthereexistsaninputonwhichMhaltsinle ssthanjhMijstepsg. thatdecidesthelanguagesworksasfollowsoni nputhMi. It rst ndsthelengthofhMi, ,it runsMonallinputsoflengthat mostjhMij, forat mostjhMijsteps,andacceptsifMacceptsatlea stoneofthestringswithinthespeci ,thenthereis nopointonlookingat any stringsthatarelonger1thanthatnumber, sinceif a TMis allowedtorunforatmostcsteps,it is notpossibleforthatTMto process any inputsymbolbeyondthecthsymbol!Thenumbero fpossibleinputsis nite,andthenumberofstepsMrunsoneachinput is nite,thereforeMis guaranteedtohaltanddecidethelanguage. L2=fhMijMis a TMandjL(M)j 3g. prove thisbya reductionfromHP. (hM; xi) = : iterasesitsinput,copiesMandxtoitstape,an drunsMonx; it now prove thevalidityofreduction: hM; xi2HP)Mdoesnothaltonx)M0doesnotacceptany input)jL(M0)j 3)M02L2.

3 HM; xi=2HP)Mhaltsonx)M0acceptsallinputs)jL(M 0)j>3)M0=2L2. GOODEXERCISE:Whathappensif thepropertywasjL(M)j= 2? Prove youranswer. L3=fhMijMis a TMandjL(M)j 3g. thatsemidecidesthelanguage,runsMonallinp utsinaninterleavedmode,andhaltswhenever3 inputshave generatestheinputstringsforMonebyoneasth ey areneeded(Itis notallowedthatM rstgeneratesallstrings,andthenstartsrunn ingMonthem,sincegeneratingtheinputstakes in nitetime!). prove thisbya reductionfromHP. (hM; xi) = :It erasesw, putsMandxonitstape, now prove thevalidityofthereduction: hM; xi2HP)Mhaltsonx)M0acceptsallinputs)jL(M0 )j 3)M02L3. hM; xi=2HP)Mdoesnothaltonx)M0doesnotacceptan y input)jL(M0)j<3)M0=2L3. L4=fhMijMis a TMthatacceptsallevennumbersg. prove thisbya reductionfromHP. (hM; xi) = : itrunsMonxforjwjsteps;it rejectsifMhaltsonxwithinjwjsteps, now prove thevalidityofthereduction: hM; xi 2HP)Mdoesnothaltonx)M0acceptsallinputs,a ndinparticular, allevennumbers)M02L4.

4 HM; xi=2HP)Mhaltsonxwithinksteps)M0rejectsal linputswwhoselengthisgreaterthanorequalt ok)M0rejectsanin nitenumberofevennumbers)M0=2L4. GOODEXERCISE:Whathappensif thepropertywas Mdoesnotacceptallevennum-bers ?Whathappensif thepropertywas Mrejectsallevennumbers ?Prove youran-swers. L5=fhMijMis a TMandL(M)is niteg. prove thisbya reductionfromHP. (hM; xi) = : now prove thevalidityofthereduction: hM; xi2HP)Mdoesnothaltonx)M0doesnotacceptany strings)L(M0)is nite) hM; xi=2HP)Mhaltsonx)M0acceptsallstrings)L(M 0)isin nite)M0=2L5. L6=fhMijMis a TMandL(M)is in niteg. prove thisbya reductionfromHP. (hM; xi) = : itrunsMonxforjwjsteps;it rejectsifMhaltsonxwithinjwjsteps, now prove thevalidityofthereduction: hM; xi 2HP)Mdoesnothaltonx)M0acceptsallstrings) L(M0)is in nite)M02L6. hM; xi=2HP)Mhaltsonxwithinksteps)M0rejectsal lstringswhoselengthisgreaterthanorequalt ok)L(M0)is nite)M0=2L6.

5 L7=fhMijMis a TMandL(M)is countableg. thelanguageofallTM's, sincetherearenouncountablelanguages(over nitealphabetsand nite-lengthstrings). L8=fhMijMis a TMandL(M)is uncountableg. ;therearenouncountablelanguages(over nitealphabetsand nite-lengthstrings). L9=fhM1; M2ijM1andM2aretwo TMs,and"2L(M1)[L(M2)g. thatsemidecidesthelanguagerunthetwo machineson"(itinterleavestherunbetweenth emachines),andacceptsif at leastoneofthemaccepts. prove thisbya reductionfromHP. (hM; xi) =hM0; : now prove thevalidityofthereduction: hM; xi2HP)Mhaltsonx)M0acceptsallstrings,andi nparticularit accepts")"2L(M0)[L(M0))hM0; M0i2L9. hM; xi=2HP)Mdoesnothaltonx)M0doesnotacceptan y strings,andinparticulardoesnotaccept")" =2L(M0)[L(M0))hM0; M0i=2L9. L10=fhM1; M2ijM1andM2aretwo TMs,and"2L(M1)\L(M2)g. thatsemidecidesthelanguagerunthetwo machineson"(itinterleavestherunbetweenth emachines),andacceptsif bothofthemaccept.]]]

6 Prove thisbya reductionfromHP. (hM; xi) =hM0; : now prove thevalidityofthereduction: hM; xi2HP)Mhaltsonx)M0acceptsallstrings,andi nparticularit accepts")"2L(M0)\L(M0))hM0; M0i2L10. hM; xi=2HP)Mdoesnothaltonx)M0doesnotacceptan y strings,andinparticulardoesnotaccept")" =2L(M0)\L(M0))hM0; M0i=2L10. L11=fhM1; M2ijM1andM2aretwo TMs,and"2L(M1)nL(M2)g. prove thisbya reductionfromHP. (hM; xi) =hM1; a TMthathaltsandacceptsonany input( ,L(M1) = ).M2oninputw: it now prove thevalidityofthereduction:3 hM; xi 2HP)Mdoesnothaltonx)M2doesnotacceptany input)L(M1)nL(M2) = )"2L(M1)nL(M2))hM1; M2i2L11. hM; xi=2HP)Mhaltsonx)M2acceptsallinputs)L(M1 )nL(M2) =;)" =2L(M1)nL(M2))hM1; M2i=2L11. L12=fhMijMis a TM,M0is a TMthathaltsonallinputs,andM02L(M)g. thatsemidecidesthelanguagerunsMonM0andha ltsifMacceptsM0.

7 Prove thisbyRice's RE: ;: , : ,; ,LC=fhMi:L(M)2Cg=2R. But,LC=fhMi:M02L(M)g; therefore,L12is notrecursive. L13=fhMijMis a TM,M0is a TMthathaltsonallinputs,andM2L(M0)g. thatdecidesL13runsM0onMandacceptsifM0acc eptsMandrejectsifM0rejectsM. ThedifferencebetweenthisandL12is thathereM0, themachinethatrunsontheinput,is guaranteedtoalwayshalt;however, inL12,M, themachinesthatrunsontheinput,mightnotha lt! L14=fhM; xijMis a TM,xis a string,andthereexistsa TM,M0, suchthatx =2L(M)\L(M0)g. TM,M, thereis alwaysa TM,M0, suchthatx =2L(M)\L(M0)g. Inparticular, ,thisis basicallythelanguageofallTM's. L15=fhMijMis a TM,andthereexistsaninputonwhichMhaltswit hin1000stepsg. verysimilartoL1. L16=fhMijMis a TM,andthereexistsaninputwhoselengthis lessthan100,onwhichMhaltsg. thatsemidecidesthelanguagerunsMonallstri ngsoflengthatmost100inaninterleavedmode, andhaltsifMacceptsat leastone.

8 Prove thisbya reductionfromHP. (hM; xi) = : it thevalidityofthisreduction!It's similartotheotherreductionsfromHPthatweu sedbefore. L17=fhMijMis a TM,andMis theonlyTMthatacceptsL(M)g. theemptyset,sinceeverylanguagehasanin nitenumberofTMsthatacceptit. L18=fhk; x; M1; M2; : : : ; Mkijkis a naturalnumber,xis a string,Miis a TMforall1 i k, andat leastk=2TM's ofM1; : : : ; Mkhaltonxg. thatsemidecidesthelanguagerunsthekmachin es(itinterleavestherunsofthemachines)onx , andacceptsif at leastk=2ofthemaccept. prove thisbya reductionfromHP. (hM; xi) =h2; x; M0; M0i).M0runsMonx, andacceptsifMhaltsonx. We now prove thevalidityofthereduction: hM; xi2HP)Mhaltsonx)M0acceptsx)h2; x; M0; hM; xi=2HP)Mdoesnothaltonx)M0doesnotacceptx) h2; x; M0; M0i=2L18. L19=fhMijMis a TM,andjMj<1000g. ,wearetalkingaboutallthedescriptionsofTu ringmachinesusinga xedalphabet(of nitesize,ofcourse), ,TM's ,L19is nite,andhencerecursive.

9 L20=fhMij9x;jxj 51, andx2L(M)g. ,M , thatsemidecidesthelanguagerunsMonallinpu ts(inaninterleavedmode)x, suchthatjxj 51, andhaltsifMacceptsat leastonesuchstring. NOT 's ;jxj 51, andx2Lg. It's easytoprove that(1)C RE, (2)C6=;, and(3)C6=RE. Hence,LC=fhMijL(M)2Cg=fhMij9x;jxj 51, andx2L(M)g62R. L21=fhMijMis a TM,andMhaltsonallpalindromesg. NOT seentheapplicationofRice's theoremtothislanguage,whichprovesthelang uagesis ,thislanguagesis alsonotinRE,andweprove :Rice's theoremdoesnotprove a languageis notinRE!We reduceHPtoL21. Thereductionfunction is asfollows: (hM; wi) =hM oninputxworksasfollows:M runsMonwforjxjsteps:ifMhaltsonwwithinjxj steps,reject, thevalidityofthereduction. L22=fhMijMis a TM,andL(M)\fa2njn 0gis emptyg. NOT 's thatdonotacceptany bya reductionfromHP. (hM; wi) =M .M oninputx: erasex, andrunMonw.

10 IfMhaltsonwthenM thevalidityofthereduction. L23=fhM; kijMis a TM,andjfw2L(M) :w2a b gj kg. ;prove it yourself. ;prove it yourself. L24=fhMijMis a TMthathaltsonallinputsandL(M) =L0forsomeundecidablelanguageL0g. ,thenL(M)is decidable,andhenceit can't bethatL(M)equalssomeundecidablelanguageL 0. Therefore,L24=;whichis recursive. L25=fhMijMis a TM,andMaccepts(atleast)two stringsofdifferentlengthsg. thatsemidecidedthelanguagerunsMonallinpu tsinaninterleavedmode,haltsandacceptsonc eMacceptstwo stringsofdifferentlengths. NOT ,oruseRice's GOODEXERCISE:Whathappensifwereplace atleast by exactly .Prove youranswer. L26=fhMijMis a TMsuchthatbothL(M)andL(M)arein NOT (hM; wi) =hM oninputxworksasfollows:ifxis ofoddlength, ofevenlength,runMonw. IfMhalts, 's prove ; wi 2HP)Mdoesnothaltonw)M acceptsallodd-lengthstringsandrejectsall even-lengthstrings)L(M)containsallodd-le ngthstrings, ,is in nite,andL(M)containsalleven-lengthstring s, ,is in nite)hM )Mhaltsonw)M acceptsallstrings)L(M) =; ,L(M)is nite,andhencehM i=2L26.