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.

2 So,toshowa languageLis notrecursive usingRice's Theorem,I picktheappropriateC( ,aCsuchthatLC=L), prove that(1)C RE, (2)C6=RE, and(3)C6=;. 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!

3 Thenumberofpossibleinputsis 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. 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!

4 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. hM; xi=2HP)Mhaltsonxwithinksteps)M0rejectsal linputswwhoselengthisgreaterthanorequalt ok)M0rejectsanin nitenumberofevennumbers)M0=2L4.

5 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.

6 HM; xi=2HP)Mhaltsonxwithinksteps)M0rejectsal lstringswhoselengthisgreaterthanorequalt ok)L(M0)is nite)M0=2L6. 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.]]

7 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. 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.]

8 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. 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.

9 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.

10 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.