当前课程知识点：计算思维导论 > 第四单元 > 4.1 从数学危机到图灵机 > Video
大家好
这一节我们介绍
从数学危机到图灵机
我们先看看图灵机是怎么来的
我们知道
数学界经历了两次数学危机
到十九世纪下半叶
德国数学家康托尔（Cantor）创立了集合论
以希尔伯特（Hilbert）为代表的数学家们
兴致勃勃地从自然数与集合论出发
希望以形式化方法
构建起整个数学大厦
也就是说
一切数学成果可建立在集合论基础上
就在数学家们努力奋斗
并取得累累硕果的时候
英国数学家
哲学家
伯特兰﹒罗素（Russell）
用一个“理发师悖论”指出
集合论也有漏洞和缺陷
给当时的数学界致命一击
那么
能不能找到一个完备的系统
从而构建起整个数学大厦呢
或者说这样的系统是否存在呢
1931年
德国数学家哥德尔（Godel）
经过证明给出了结论
任何一个数学系统
只要它是从有限的公理
和基本概念中推导出来的
并且从中能推证出自然数系统
就可以在其中找到一个命题
对于这个命题
我们既无法证明
也就是证真
也无法推翻
或者叫证伪
这就是著名的
哥德尔不完备性定理
它宣告了把数学彻底形式化
是不可能实现的
人们无法寻求一个完美的数学系统
因此 在一个数学系统中
总有一些命题既不能证真
也不能证伪
左边是可以证明的问题
右边是既不能证真
也不能证伪的问题
那么中间
它的界线到底在哪里
怎么去判断一个
未解的问题是否真的有解
这就是所谓的可计算问题
那么
什么是可计算的（Computable）呢
从数学的角度来说
设函数f
它的定义域为D
值域为R
如果存在一种算法
对D中任意选定的x
都能计算出函数f(x)的值
那么则称函数f是可计算的
从计算机的角度来说
在可以预先确定的时间和步骤之内
能够具体进行的计算
当然 这是后话
在电子计算机出现之前
数理逻辑学家们
就提出了这么一个研究思路
为计算建立一个数学模型
我们也称之为计算模型
然后证明
凡是这个计算模型能够完成的任务
就是可计算任务
反之 就是不可计算任务
图灵（Turing）就是在这种情况下
提出了一个计算模型
这就是图灵机（Turing machine）
并于1936年发表了著名的论文
论可计算数在判定问题中的应用
从图灵机模型可以看出它的构成
主要有
一
一条无限长的纸带
纸带被划分为一个个格子
每个格子里面可以存放一个数字或符号
二
一个读写头
它可以读写所在格子中的数字或字母
三
一个控制器
控制器有若干种不同的状态
按照事先确定的一套计算规则
根据当前的状态以及
读入的数字或符号
改写所在格子中的数字或符号
移动读写头并改变自身的状态
例如一个五元组
Q1 b 1 R Q2
它表示控制器当前状态是Q1
读入符号b后 输出1
控制器状态变成Q2
然后把读写头往右移一格
四
一个寄存器
它位于控制器内部
用于记录控制器的当前状态
现在让我们看看图灵机的计算过程
假设图灵机只接收两个符号
即空白符合
在这我们用符号b表示
和数字1
并设我们的计算仅涉及正整数
且整数的大小用1的个数来表示
例如
整数4用1111
也就是4个1来表示
7用1111111表示
也就是7个1
现在我们用一个简单的实例
来展示图灵机的计算过程
该过程和玩游戏差不多
假定我们要计算
四加三等于多少
刚开始时
图灵机的状态为Q0
读入的符号为b
因此根据第一条规则
它输出b
然后状态变成Q1
且往右移动读写头
现在大家看到图灵机的状态为Q1
读入的符号为1
因此根据第二条规则
它输出1 然后状态变成Q1
且继续往右移动读写头
好了
大家看到这一步显然与前面一样
我们不再细说
继续往右移动
同理 继续右移读写头
还是一样
再继续往右移动读写头
现在注意了
图灵机的状态为Q1
读入的符号为b
因此根据第三条规则
它输出1 然后状态变成Q2
且往右继续移动读写头
我们现在看到图灵机的状态为Q2
读入的符号为1
因此根据第四条规则
它输出1 然后状态变成Q2
且往右移动读写头
这一步与前面一样
也不再细说
继续往右移动
还是继续往右移动
现在我们看到图灵机的状态为Q2
读入的符号为b
因此根据第五条规则
它输出b 然后状态变成Q3
注意 现在要往左移动读写头
我们现在看到的图灵机的状态为Q3
读入的符号为1
因此根据第六条规则
它输出b 然后状态变成Q3
这里请注意
不移动读写头了
现在图灵机的状态为Q3
读入的符号为b
因此根据第七条规则
它输出b 然后状态变成Q’
且读写头不动
Q’为结束状态
计算结束了
我们得到了计算结果7
从上述过程不难看出
一
图灵机是一个纯理论模型
比如 纸带可以无限长
二
图灵机对计算过程的机械特征进行了精细地刻画
三
计算过程的核心机制
是图灵机运行的“计算规则集”
四
图灵机的计算过程
不再依赖于人的心智和灵感
因此
我们可以说图灵机所刻画的是
是机械的计算机思维
好 这一节就讲到这
谢谢大家
-1.1 计算思维及其教育
--Video
-2.1 计算是什么
--Video
-2.2 计算与自动计算
--Video
-2.3 计算机及其计算本质特征（I）
--Video
-2.4 计算机及计算的本质特征（II）
--Video
-3.1 数的表示与模拟计算
--Video
-3.2 数的表示与数字计算
--Video
-3.3 二进制加法运算的机器化
--Video
-3.4 “九九归一”的加法运算
--Video
-3.5 二进制之优越性及问题与代价
--Video
-4.1 从数学危机到图灵机
--Video
-4.2 图灵机的计算能力
--Video
-4.3 什么问题都能计算吗？
--Video
-4.4 冯•诺依曼机及其发展与演化
--Video
-4.5 从算盘到图灵机——机械计算的本质
--Video
-4.6 电子计算机——透过现象看本质
--Video
-5.1 思维可机械计算吗（I）
--Video
-5.2 思维可机械计算吗（II）
--Video
-6.1 量子理论
--Video
-6.2 量子计算机
--Video
-7.1 人类求解问题之过程
--Video
-7.2 基于计算（机）的问题求解过程
--Video
-7.3 面向过程的结构化设计方法学
--Video
-7.4 面向对象之方法学
--Video
-7.5 面向对象技术
--Video
-7.6 抽象
--Video
-7.7 计算学科中的抽象
--Video
-7.8 时间与空间及其相互转换
--Video
-7.9 技术层面的其他方法学
--Video
-7.10 认知层面的其他方法学
--Video
-8.1 算法与程序
--Video
-8.2 算法设计方法——枚举
--Video
-8.3 算法设计方法——递推
--Video
-8.4 算法设计方法——递归
--Video
-8.5 算法设计方法——分治
--Video
-8.6 算法设计方法——仿生
--Video
-9.1 机器间的通信方式
--Video
-9.2 数据转发方法
--Video
-9.3 网络分层体系结构
--Video
-9.4 有趣的对称加密技术
--Video
-9.5 难解的非对称加密技术
--Video
-9.6 数字签名及其应用
--Video
-9.7 从自然智能到人工智能
--Video
-9.8 符号主义的基本思想
--Video
-9.9 连接主义Ⅰ
--Video
-9.10 连接主义Ⅱ
--Video
-9.11 行为主义的基本思想
--Video
-9.12 机器翻译的愿景与困难
--Video
-9.13 峰回路转的自然语言处理
--Video
-9.14 信息传输中的问题与挑战
--Video
-9.15 重复传输与冗余编码
--Video
-9.16 校验与校验和
--Video
-9.18 自纠错技术及应用
--Video
-9.19 两种简单的数据压缩方法
--Video
-9.20 哈夫曼编码
--Video
-9.21 数据压缩极限与LZ压缩方法
--Video
-9.22 大海捞针的搜索引擎
--Video
-9.23 网页排序方法（PageRank）
--Video
-10.1 计算文化
--Video
-期末考试--作业
