资源描述：
《计算理论导论(英文版)图灵机课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Chapter3 TheChurch-TuringThesis1ModelsofComputingDevicesFiniteautomataTapeheadmovesonlyinonedirectionTapeisread-onlyThelengthoftapeisconstantPushdownautomataTapeheadmovesonlyinonedirectionTapeisread-only,butstackiswritableTapelengthisconstant,butstackinunboundedStackisaccessibleonlyin
2、FILOway2ConclusionBothDFAandPDAarehandicappedmachineswithlimitedcomputationpower.Theyaretoorestrictedtoserveasmodelofgeneralpurposecomputers.ComputabilityComputableEquivalenceofDFAs;StringmembershipinaRLUncomputableEquivalenceofCFGs;EmptinessofthecomplementofaCFL3Consideringmorepowerf
3、ulmodelforcomputation:WritableandtwowaytapeRandomaccessmemory4TuringMachinesAfterAlanM.Turing(1912–1954)In1936,Turingintroducedhisabstractmodelforcomputationinhisarticle“OnComputableNumbers,”.Atthesametime,AlonzoChurchpublishedsimilarideasandresults.reachthesamegoalbydifferentroutesHo
4、wever,theTuringmodelhasbecomethestandardmodelintheoreticalcomputerscience.53.1.1InformalDescriptionTMAninfinitetape-,dividedintocells(orcalledsquares),whichcaneachholdexactlyonesymbol.Atapehead–read,write,movearoundInitially….nextpage6InputConvention7InputConvention8OutputConvention9T
5、uringMachine元组式定义ATuringmachineMisdefinedbya7-tuple(Q,S,G,d,q0,qaccept,qreject),with1.Qfinitesetofstates状态集合，相当于程序标号2.Sfiniteinputalphabet(without“_”)输入字母表3.Gfinitetapealphabetwith{_}ÈSÍG带字母表4.q0startstateÎQ开始状态5.qacceptacceptstateÎQ接受状态6.qrejectrejectstateÎQ拒绝状态7.dthetransitionfuncti
6、on转移函数相当于移动+goto10ConfigurationofaTM格局=状态＋已经处理部分＋今后任务，目前形式与任务TheconfigurationofaTuringmachineconsistsofthecurrentstateqÎQthecurrenttapecontentsÎG*thecurrentheadlocationÎ{0,1,2,…}ThiscanbeexpressedasanelementofG*×Q×G*:11ConfigurationofaTM格局=状态＋已经处理部分＋今后任务，目前形式与任务TheconfigurationofaTuri
7、ngmachineconsistsofthecurrentstateqÎQthecurrenttapecontentsÎG*thecurrentheadlocationÎ{0,1,2,…}ThiscanbeexpressedasanelementofG*×Q×G*:12AnElementaryTMStep13Terminology格局startingconfigurationoninputw:“q0w”初始格局acceptingconfiguration:“uqacceptv”接受格局返回truerejectingconfiguration:“uqrejectv”
8、拒绝格局返
