资源描述：
《art4图灵机及可计算理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Part4图灵机及可计算理论主讲教师贺利坚Part4主要内容提示内 容教 材 出 处一、图灵机及形式定义9.1基本概念(9.1.1)二、图灵机的构造9.1基本概念(9.1.1-3)三、图灵机的变形9.2图灵机的变形四、通用图灵机9.3通用图灵机五、可计算性理论9.4可计算性理论的几个相关概念2*一、图灵机及形式定义1、图灵机2、图灵机的形式定义3、图灵机接受的语言3*图灵机FA和PDA的局限FA有有限的存储，只能处理RLPDA用栈提供无限的存储，但栈只能后进先出，PDA只能处理CFLFA和PDA不能用作通用的计算模型4*图灵机是通用的计算模型，是计算机的数学模型图灵在论
2、述“有些数学问题是不可解的”时，提出了图灵机图灵论题：凡是可计算的函数，都可以用图灵机计算丘奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现提出TM的目的在于:对有效的计算过程(即算法)进行形式化的描述,忽略模型的存储容量在内的一些枝节问题,只考虑算法的基本特征.图灵提出TM具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。图灵机5*图灵生平1912年出生，演算能力突出1931年，进剑桥大学学数学1936年，提出图灵机模型1938年，获普灵斯顿大学博士学位1950年，发表论文“计算机和智能”，提出图灵测试1951年，成为英皇家学会院士19
3、54年，不幸去世现代计算机设计思想的创始人，人工智能领域的开拓者计算机领域的最高奖以图灵命名图灵机6*AlanTuring(1912-1954)1912(23June):Birth,Paddington,London 1926-31:SherborneSchool 1930:DeathoffriendChristopherMorcom1931-34:UndergraduateatKing'sCollege,CambridgeUniversity 1932-35:Quantummechanics,probability,logic 1935:ElectedfellowofK
4、ing'sCollege,Cambridge 1936:TheTuringmachine,computability,universalmachine1936-38:PrincetonUniversity.Ph.D.Logic,algebra,numbertheory 1938-39:ReturntoCambridge.IntroducedtoGermanEnigmaciphermachine 1939-40:TheBombe,machineforEnigmadecryption 1939-42:BreakingofU-boatEnigma,savingbattleoft
5、heAtlantic 1943-45:ChiefAnglo-Americancryptoconsultant.Electronicwork. 1945:NationalPhysicalLaboratory,London 1946:Computerandsoftwaredesignleadingtheworld. 1947-48:Programming,neuralnets,andartificialintelligence 1948:ManchesterUniversity 1949:Firstseriousmathematicaluseofacomputer 1950:
6、TheTuringTestformachineintelligence 1951:ElectedFRS.Non-lineartheoryofbiologicalgrowth 1952:Arrestedasahomosexual,lossofsecurityclearance 1953-54:Unfinishedworkinbiologyandphysics 1954(7June):Death(suicide)bycyanidepoisoning,Wilmslow,Cheshire.7*图灵机的物理模型基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一
7、个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。图灵机8*图灵机的形式定义定义9-1图灵机(Turingmachine)/基本的图灵机TMM=(Q,∑,Γ,,q0,B,F)Q：状态的有穷集合，q∈Q为M的一个状态；∑：输入字母表，a∑为M的一个输入符号。除空白符号B外，只有∑中的符号才能在M启动时出现在输入带上；Γ：带符号表(tapesymbol)，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上；q0∈Q：M的开始状态，
