2
一、图灵机及形式定义
1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言
3

图灵机
FA和PDA的局限 FA有有限的存储，只能处理RL PDA用栈提供无限的存储，但栈只能后进先出，PDA 只能处理CFL
FA和PDA不能用作通用的计算模型
4
图灵机
图灵机是通用的计算模型，是计算机的数学模型 图灵在论述“有些数学问题是不可解的”时，提出了图灵 机 图灵论题：凡是可计算的函数，都可以用图灵机计算 丘奇论题：任何计算，如果存在一个有效过程，它就能被 图灵机实现
Part 4 图灵机及可计算理论
主讲教师 贺利坚
Part 4 主要内容提示
内容 一、图灵机及形式定义 二、图灵机的构造 三、图灵机的变形 四、通用图灵机 五、可计算性理论
教材出处
9.1 基本概念(9.1.1)
9.1 基本概念(9.1.1-3) 9.2 图灵机的变形 9.3 通用图灵机 9.4 可计算性理论的几个相关概 念
现代计算机设计思想的创始人，人工智能领域的开拓者 计算机领域的最高奖以图灵命名
6
Alan Turing(1912-1954)
1912 (23 June): Birth, Paddington, London 1926-31: Sherborne School 1930: Death of friend Christopher Morcom 1931-34: Undergraduate at King's College, Cambridge University 1932-35: Quantum mechanics, probability, logic 1935: Elected fellow of King's College, Cambridge 1936: The Turing machine, computability, universal machine 1936-38: Princeton University. Ph.D. Logic, algebra, number theory 1938-39: Return to Cambridge. Introduced to German Enigma cipher machine 1939-40: The Bombe, machine for Enigma decryption 1939-42: Breaking of U-boat Enigma, saving battle of the Atlantic 1943-45: Chief Anglo-American crypto consultant. Electronic work. 1945: National Physical Laboratory, London 1946: Computer and software design leading the world. 1947-48: Programming, neural nets, and artificial intelligence 1948: Manchester University 1949: First serious mathematical use of a computer 1950: The Turing Test for machine intelligence 1951: Elected FRS. Non-linear theory of biological growth 1952: Arrested as a homosexual, loss of security clearance 1953-54: Unfinished work in biology and physics 1954 (7 June): Death (suicide) by cyanide poisoning, Wilmslow, Cheshire.
q0∈Q：M的开始状态，M从状态q0启动，读头正注视着输入 带最左端的符号；
B：空白符(blank symbol)，含空白符的带方格是空的；
FQ：M的终止状态集，q∈F为M的一个终止状态。 TM M 一旦进入终止状态，它就停止运行。
9
图灵机的形式定义
TM M=(Q, ∑, Γ, , q0, B, F) 称为移动函数
7
图灵机
图灵机的物理模型 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 一个移动将完成以下三个动作： 改变有穷控制器的状态； 在当前所读符号所在的带方格中印刷一个符号； 将读头向右或者向左移一格。
8
图灵机的形式定义
定义9-1 图灵机(Turing machine)/基本的图灵机
TM M=(Q, ∑, Γ, , q0, B, F)
Q：状态的有穷集合，q∈Q为M的一个状态；
∑：输入字母表，a∑为M的一个输入符号。除空白符号B
外，只有∑中的符号才能在M启动时出现在输入带上；
Γ：带符号表(tape symbol)，X为M的一个带符号，表示
在M的运行过程中，X可以在某一时刻出现在输入带上；
提出TM的目的在于: 对有效的计算过程(即算法)进行形式化的 描述, 忽略模型的存储容量在内的一些枝节问题, 只考虑算法的 基本特征.
图灵提出TM具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。
5
图灵机
图灵生平 1912年出生，演算能力突出 1931年，进剑桥大学学数学 1936年，提出图灵机模型 1938年，获普灵斯顿大学博士学位 1950年，发表论文“计算机和智能”，提出图灵测 试 1951年，成为英皇家学会院士 1954年，不幸去世
：Q×Γ Q×Γ ×{R, L}，为M的移动函数(transaction
function)。
(q, X)=(p, Y, R)表示M在状态q读入符号X，将状态改为p，
并在这个X所在的带方格中印刷符号Y，然后将读头向右 移一格；
(q, X)=(p, Y, L)表示M在状态q读入符号X，将状态改为p，