资源描述：
《图灵机基本理论介绍(turing machines)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、TuringMachinesA“Turingmachine”isatheoreticalmodelofacomputerintroducedbyAlanTuringin1936.Itconsistsofalittle“machine”havingafiniteamountofmemorysittingonaninfinitetapewhichitcanreadandwritefrom:bA⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1100110⊔11001aThetapeisthemachine’s“externalmemory”.Italsohasaninterna
2、lmemory,knownasastate,whichisrepresentedbytheletter‘A’inthedrawing.Howeverthemachine’sinternalmemoryisfinite,sothataTuringmachinehasonlyfinitelymanydifferentstates.Ateachmomentofthecomputation,themachineisinexactlyonestate.Ateachstep,dependingonthesymbolatitscurrentlocationandonitsstate,themach
3、inedecideswhethertoprintanewsymbolatthislocation,whichnewstatetoenter,andwhethertogoleftorrightbyonecellonthetape.HereisanexampleofaTuringmachinewiththreenon-haltingstatesA,B,Candthatworkswithtwotapesymbols,‘⊔’and‘1’(bytheway,‘⊔’iscalledthe“blanksymbol”):ABC⊔(1,B,R)(⊔,C,R)(1,C,L)1(1,H,R)(1,B
4、,R)(1,A,L)IncolumnAandrow⊔wesee‘(1,B,R)’;thismeanswhenthemachineisinstateAandreadsa‘⊔’,themachineprintsa‘1’,changestostateB,andthenmovesright(Risforright,Lisforleft).Themachine’sstartstateisA(Aisunderlinedtoshowthatitisthestartstate)andthemachinehasaspecialhaltingstate,calledH;whenthemachine
5、reachesthehaltingstate,thecomputationstops.Herearethestepswhichthismachinemakeswhenitisstartedonatapewithallblanksymbols:bABCC⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1⊔1CABB⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1111BBCC⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔1111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔11111A
6、H⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔111111⊔⊔⊔⊔⊔⊔⊔⊔⊔⊔111111a1(Tomakethecomputationeasiertoread,wehaveputalittletriangletomarkthemachine’sstartingpositiononthetape.)Thismachinedoesthirteenstepsbeforehalting.Themachine’scomputationhasno“meaning”,inthiscase,butotherTuringmachinescomputeusefulthings.NotallTuringmachinesh
7、alt.ForexampletheTuringmachineABC⊔(⊔,B,R)(⊔,A,L)(⊔,H,L)simplyswitchesbackandforthbetweenstatesAandBforever,withouteverenteringstateCorthehaltingstateH.Asanevensimplerexample,themachineA⊔(⊔,A,R)simplygoesforevertotheright.Boththesemachinesworkonlywi
