资源描述：
《8 A noncomputably enumerably language.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、8ANoncomputablyEnumerableLanguage8.1IntroductionInSect.7.7,Igaveapassingcommentthatthesetofcompositenumbersiscom-putablyenumerable.Thereisaminorhuddleinusingtheterminologytoarbitrarysets,forexample,asetofnumbers,ratherthantolanguages.Thatisnotabighud-dle,forwejustrepresen
2、tacountablesetbyalanguageandtrytosolvetheproblemaboutthelanguage.Agreedthatwecanusetheadjective“computablyenumerable”forsets,howdoweproceedtoshowthatthesetofcompositenumbersiscomputablyenumerable?Itssolution,assuggestedthere,requiresaTuringmachinecapableofmultiplyingtwonu
3、mberspandq.Nowthisissomethingunnaturaltothewaywewereusingallourautomata.Why?Wehaveusedallvarietiesofautomataaslanguageacceptors,which,givenastring,wouldsignaltouswhetheritacceptsthestringornot.Here,whenwesaythatwewantmultiplicationofpandq,ourrequirementisabitmoredemanding
4、.WewantaTuringmachinenotonlytooperateandhaltonaninput,butalsoitshouldgiveusanoutputuponhalting.Toaddtotheproblem,whenamachinehaltsaftergivinganoutput,anothermachinemayalsoworkonthesametape,takingthecontentofthetapeasitsin-puttape.Thatis,thefirstmachinemustleavethetapeinsuc
5、hawaythatitcanbeusedasaninitialtapeforanothermachine.Asourinputsarewrittenasbu,wheretheread/writeheadisplacedinitiallyonthebprecedingtheinput,wemaylikeouroutputtobeinthesameform.Thismeansthatthefirstmachinemustscanthesymbolbprecedingtheoutputwhilehaltingsothatthesecondm
6、achinewillstartworking.Thisrequirementamountstoimaginingthemachineasthecontrolunitonly,whereasthetapeandtheread/writeheadcanbedetachedfromitandattachedtoanothermachinethatmightworkafterthefirsthadcompleteditsjob.Itgoesalongwellwithourmachinecombinationsalso.Wewillputitasac
7、onventionwhilecom-putinganyfunction.A.Singh,ElementsofComputationTheory,TextsinComputerScience,245cSpringer-VerlagLondonLimited20092468ANoncomputablyEnumerableLanguage8.2TuringMachinesasComputersComputingafunctionf(·)meansthatgivenaninputxtothemachine,itmustoutputthevalu
8、ef(x)uponhalting.Aswehaveadoptedourdatastructureasstrings,wewillusethemforcomputingfunctionsmapp
