最后更新: 2025-11-05 10:47 查看: 99 次纠错评论(0) 课件开VIP

图灵 Turing

## 图灵 Turing
艾伦·麦席森·图灵（1912年6月23日 – 1954年6月7日）是英国数学家、逻辑学家、密码分析学家和理论生物学家，他被广泛誉为**计算机科学与人工智能之父**。他的工作对现代数字计算机的发展、理论计算机科学的形成以及人工智能的探索产生了深远而根本的影响。

![图片](/uploads/2025-11/a5b32b.jpg){width=200px}
 
 ## 大学生涯
1931年，图灵考入剑桥大学国王学院攻读本科，并获得了数学一等荣誉。

1934年他以优异成绩毕业。

1935年，22岁的他凭借证明中心极限定理的论文被选为国王学院研究员。虽然说图灵不知道，该定理已在1922年由亚尔·瓦尔德马·林德伯格证明。尽管如此，委员会认为这项研究值得考虑提供研究金。

图灵在他的重要论文《论可计算数及其在判定问题上的应用》（英语：On Computable Numbers, with an Application to the Entscheidungsproblem）里 ，对哥德尔1931年在证明和计算的限制的结果作了重新论述，他用现在叫做图灵机的简单形式的抽象设备代替了哥德尔的以通用算术为基础的形式语言。虽然图灵机过于缓慢的速度使其没有实际用途，图灵还是证明了这样的机器有能力解决任何可想像的，并以数学式表达的数学难题。现今，图灵机还是计算理论研究的中心课题。他继续证明了判定问题是没有答案的。他的证明首先展示了图灵机的停机问题没有答案，这是说不可能用一个算法来决定一台指定的图灵机是否会停机。尽管他的证明比阿隆佐·邱奇在λ演算方面相等的证明晚发表了几个月，图灵的著作是更易于理解和直观。他的通用（图灵）机的概念也很新颖。这一通用机能够完成任何其他机器所能做的任务。这篇论文还介绍了可定义数的概念。

1936年9月到1938年7月间，图灵大部分时间都在普林斯顿大学的教堂下学习，第二年被评选为简·伊丽莎·宝洁奖学金客座教授（Jane Eliza Procter Visiting Fellow）。除了他的纯数学工作外，他亦研究密码学，并建造了机电二进制乘法器的四个阶段中的其中三个。[16]1938年6月，获普林斯顿数学系博士学位； 他的论文基于序数的逻辑系统 ,介绍了序数逻辑的概念和相对计算的概念，其中图灵机增加了所谓的预言机，允许学者进一步研究图灵机无法解决的问题。冯·诺依曼有意聘请图灵做他的博士后助理，但他谢绝后又回到了英国。

1939年图灵回到剑桥，聆听了维特根斯坦关于数学基本原理（Foundations of mathematics）的讲座。他们激烈地争论，图灵为形式主义辩护，而维特根斯坦则认为把数学抬得太高反而不能发现任何绝对真理。

## 图灵机
图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种将人的计算行为抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。

> 今天的我们对电脑“视而不见”，输入一个命令计算机就会给出结果，认为这些结果是“理所当然”，但是时间回退到1940年左右，给你一个机器，能否指向这个命令？怎么指向这个命令？等等都是悬而未决的问题，图灵是第一个采用数学逻辑推导出计算机可行性的第一人。

![图片](/uploads/2025-11/6d95e1.jpg)
 图灵机的艺术表示

### 图灵的基本思想
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；
把注意力从纸的一处移动到另一处；
而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某个位置的符号和（b）此人当前思维的状态。
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

1一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 □表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, ...，纸带的右端可以无限伸展。

2 一个读写头HEAD。它可以在纸带上左右移动，能读出当前所指的格子上的符号，并能改变它。
3 一套控制规则数量有限的TABLE（A finite table of instructions）。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
按照以下顺序告知图灵机命令：
 ① 写入（替换）或擦除当前符号；
 ② 移动 HEAD， 'L'向左， 'R'向右或者'N'不移动；
 ③ 保持当前状态或者转到另一状态。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。

![图片](/uploads/2025-11/b240ec.jpg)
 
**注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。**

## 密码分析
在第二次世界大战期间，图灵是布莱切利庄园破解德国密码的主要参与者

1939年图灵被英国皇家海军招聘，并在英国军情六处监督下从事对德国机密军事密码的破译工作。两年后他的小组成功破译了德国的密码系统**恩尼格玛**密码机，从而使得军情六处对德国的军事指挥和计划了如指掌。但是军情六处以机密为由隐瞒了图灵小组的存在和成就，将其所得情报据为己有。

通过使用统计技术来优化密码破译过程中不同可能性的试验，图灵为该课题做出了创新贡献。他写了两篇有关数学计算方法的论文，题为 The Applications of Probability to Cryptography[25]和Paper on Statistics of Repetitions, 对 GC&CS 及其继任者GCHQ具有十分重要的价值，以至于它们直到2012年4月才被发布给英国国家档案馆，也就是他诞辰一百周年前不久。

## 图灵测试

1945年到1948年，图灵在国家物理实验室负责自动计算引擎（ACE）的研究工作。1949年，他成为曼彻斯特大学计算机实验室的副主任，负责最早的真正的计算机---曼彻斯特一号的软件工作。在这段时间，他继续作一些比较抽象的研究，如“计算机械和智能”。图灵在对人工智能的研究中，提出了一个叫做图灵测试的实验，尝试定出一个决定机器是否有感觉的标准。

1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。

后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究组根据图灵的理论，在ENIAC上设计出世界上第一个电脑程序的国际象棋－洛斯阿拉莫斯国际象棋。

图灵测试（英语：Turing test）是英国计算机科学家艾伦·图灵于1950年提出的思想实验，图灵亦将其称为“模仿游戏”（imitation game），这个实验的流程是由一位询问者写下自己的问题，随后将问题发送给在另一个房间中的一个人与一台机器，由询问者根据他们所作的回答来判断哪一个是真人，哪一个是机器，所有测试者都会被单独分开，对话以纯文本形式透过屏幕传输，因此结果不取决于机器的语音能力，这个测试意在探求机器能否模仿出与人类相同或无法区分的智能

![图片](/uploads/2025-11/417d99.svg)
图灵测试一个标准的模式：C使用问题来判断A或B是人类还是机械

## 图案形成和数理生物学的研究
从1952年直到去世，图灵一直在生物数学方面做研究。他在1952年发表了一篇论文《形态发生的化学基础》（英语：The Chemical Basis of Morphogenesis）。[46]他主要的兴趣是斐波那契叶序列，存在于植物结构的斐波那契数。他应用了反应-扩散公式，现在已经成为图案形成范畴的核心。他后期的论文都没有发表，一直等到1992年《艾伦·图灵选集》出版，这些文章才见天日。 2012年，《自然》杂志称赞他是有史以来最具科学思想的人物之一。

## 图灵估计
Good-Turing平滑法可处理N元语法中数据矩阵的稀疏问题，主要思想将非零N元语法的概率均匀分给一些低概率语法，以修改最大似然估计与真实概率之间的偏离。是使用的比较多的一种平滑算法。

在自然语言处理的N元模型中，用最大似然估计（MLE）作为某个字符串出现的概率，这样会造成数据稀疏问题，并且使得MLE值偏离真实概率。这个问题与N元语法自身有关，他们不能估计长距离的上下文，总是倾向于过低地估计哪些在训练语料库中不是彼此向邻近出现的符号串的概率。

平滑就是给那些“零概率和低概率的N元语法”指派非零概率的方法。平滑分为打折和回退，打折是指将某个非零N元语法的计数降下来，把这部分概率量指派给那些训练语料库中出现次数为零或很低的事件。回退指用根据N-1元语法计数来建立N元语法模型。
Good-Turing平滑法由古德于1953年提出，而这种算法的思想则来自图灵

## 图灵完备性
在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它便符合图灵完备（Turing-complete或computationally universal）。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。

还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P，则两台计算机P和Q称为等效计算机。 邱奇－图灵论题认为任何可以通过算法计算其值的函数都可以由图灵机计算，因此，如果任何真实世界的计算机都可以模拟图灵机，则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机，且可以扩展现实世界计算机的计算方面。

如果某物是图灵完备的，则它可以用于模拟某些图灵完备的系统。例如，一个指令式编程具有条件表达式（例如，“ if”和“ goto”语句，或者“branch if zero”的指令；请参见单一指令计算机）并且具有更改任意指令的能力，那么它便具备图灵完备性。

需要注意的是，虽然任何物理系统都不可能进行无限的迭代展开，但如果忽略这项限制，绝大多数物理系统都符合图灵完备性。

## 图灵归约
图灵归约是可计算性理论中的一种归约，若问题A可图灵归约成问题B，是指若问题B的解答已经知道（Rogers 1967, Soare 1987），就可以解问题A，也可以解释为若一个算法可以用来处理问题B，就可以处理问题A。较正式的说法，可被图灵归约成问题B的问题是指若存在问题B的预言机，就可以求解的问题集合。图灵归约可以用在决定性问题及功能性问题。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：刘维尔 Liouville

下一篇：序：近世代数对数学的整体思考

本文对您是否有用？有用 (0) 无用 (0)