图灵机及可计算理论.ppt

Part 4 图灵机及可计算理论 主讲教师 贺利坚 Part 4 主要内容提示 一、图灵机及形式定义 1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言 图灵机 FA和PDA的局限 FA有有限的存储，只能处理RL PDA用栈提供无限的存储，但栈只能后进先出，PDA只能处理CFL FA和PDA不能用作通用的计算模型 图灵机是通用的计算模型，是计算机的数学模型 图灵在论述“有些数学问题是不可解的”时，提出了图灵机 图灵论题：凡是可计算的函数，都可以用图灵机计算 丘奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现 提出TM的目的在于: 对有效的计算过程(即算法)进行形式化的描述, 忽略模型的存储容量在内的一些枝节问题, 只考虑算法的基本特征. 图灵提出TM具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。 图灵生平 1912年出生，演算能力突出 1931年，进剑桥大学学数学 1936年，提出图灵机模型 1938年，获普灵斯顿大学博士学位 1950年，发表论文“计算机和智能”，提出图灵测试 1951年，成为英皇家学会院士 1954年，不幸去世 Alan Turing(1912-1954) 1912 (23 June): Birth, Paddington, London1926-31: Sherborne School1930: Death of friend Christopher Morcom1931-34: Undergraduate at Kings College, Cambridge University1932-35: Quantum mechanics, probability, logic1935: Elected fellow of Kings College, Cambridge1936: The Turing machine, computability, universal machine1936-38: Princeton University. Ph.D. Logic, algebra, number theory1938-39: Return to Cambridge. Introduced to German Enigma cipher machine1939-40: The Bombe, machine for Enigma decryption1939-42: Breaking of U-boat Enigma, saving battle of the Atlantic1943-45: Chief Anglo-American crypto consultant. Electronic work.1945: National Physical Laboratory, London1946: Computer and software design leading the world.1947-48: Programming, neural nets, and artificial intelligence1948: Manchester University1949: First serious mathematical use of a computer1950: The Turing Test for machine intelligence1951: Elected FRS. Non-linear theory of biological growth1952: Arrested as a homosexual, loss of security clearance1953-54: Unfinished work in biology and physics1954 (7 June): Death (suicide) by cyanide poisoning, Wilmslow, Cheshire. 图灵机的形式定义 定义9-1 图灵机(Turing machine)/基本的图灵机 TM M=(Q, ∑, Γ, ?, q0, B, F) Q：状态的有穷集合，?q∈Q为M的一个状态； ∑：输入字母表，?a?∑为M的一个输入符号。除空白符号B外，只有∑中的符号才能在M启动时出现在输入带上； Γ：带符号表(tape symbol)，?X??为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上； q0∈Q：M的开始状态，M从状态q0启动，读头正注视着输入带最左端的符号； B??：空白符(blank symbol)，含空白符的带方格是空的； F?Q：M的终止状态集，?q∈F为M的一个终止状态。