论人类下一代语言的可能—8.1图灵机 - 人类下一代语言的可能
source link: https://www.cnblogs.com/CHARACTER2/p/16888481.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
论人类下一代语言的可能—8.1图灵机
除了在纸笔媒介系统下以书面符号形式进行数学计算外,从一开始我们也设计和制造计算工具,利用这些工具来进行数学计算。 现代计算机是计算工具的最新产品。上世纪三十年代,英国数学家图灵(Alan Mathison Turing,1912.6-1954.6)提出了图灵机的概念,其基本原理如下。
(图8-1:图灵机)
图灵机的构成包括:
用于输入与输出,可以设想为一个无限长的纸带,纸带分为一个个单元格Rn,每个单元格上记录某个字符表中的一个字符R(a),或者为空。
读写头可以在纸带上左右移动,其作用是:
读取当前单元格里的字符;
擦除当前单元格里的字符;
将一个字符写入当前单元格。
任意时刻读写头只能在一个单元格上操作,此单元格称为扫描单元格。
图中的控制器可分解为下面的逻辑部件:
字母表包括了输入纸带单元格上可以有的字符,读写头可以写入单元格的字符,比如字符集是{“1”“0”“+”“=”“︺”}。
图灵机在任意时刻都处于一种状态下,所有的状态构成状态集{s0、s1、s2、s3、s4、s5},其中包括:
开始状态s0、每次运行的开始都处于此状态;
停机状态s5、当图灵机进入此状态时,机器就停止运行,此状态下纸带留下的字符为计算结果或者问题无解。
5控制规则
读写头读取当前单元格的字符,结合当前机器的状态,可决定:
一、图灵机的新状态;
二、图灵机的响应操作,包括:
擦除:擦除当前单元格的内容;
写入:在当前单元格写入字符集中的一个字符;
移动:向左移动或向右移动。
图灵机的操作可抽象为:((当前状态、当前读入)→(新状态、当前写入、移动方向))。一个图灵机可能的(当前状态、当前读入)组合称为其格局,它们对应的控制规则决定了图灵机的行为。我们构造个简单的例子,这个例子是二进制个位数的加法运算。设计七种状态:(整体可以有不同的设计)
s0:初始状态;
s1:被加数=1;
s2:被加数=0;
s3:被加数、加数=1;
s4:被加数、加数不一致;
s5:被加数、加数=0;
S6: 停机状态。
字符表为{“1”“0”“+”}。
“擦除”操作表示清空单元格内容。
可制定的规则如下:
纸带上的输入是字符串“1+0=”,将进行的过程如下:
【1】+0 |
S0→s1 |
||
1【+】0 |
|||
1+【0】 |
S1→s4 |
||
注:【】符号表示括号中的字母在当前单元格。
这是个过于简单的例子。一般书上所能见到的例子都过于简单,人们不禁会问:图灵机能有什么用?现代计算机所处理的问题越来越复杂,比如宇宙演化的模拟、天气预报、自动驾驶等等,这些处理中也是应用同样的机制,区别在于字符集、状态集、规则集的数量级。
图灵机的强大还在于可以构造通用图灵机:可以模拟其他图灵机的图灵机。一台解决特定问题的图灵机,其字符表中的字符、状态集的状态、规则集中的规则,它们的数量都是有限的,因此它所有“((当前状态、当前读入)→(新状态、当前写入、移动方向))”可以以某种方式编码,作为另一台图灵机纸带上的特定输入,同时它运行时的状态、位置也在模拟时维护在通用图灵机纸带的特定单元格,这样后一台图灵机通过读取上的控制可以模拟前一台图灵机的运行。有了通用的图灵机,我们就不必为每一类问题设计专门的图灵机,只需要为通用的图灵机设计不同的纸带与控制就可以。目前已知最小的通用图灵机是字符表的字符数量为2,状态集的状态数量为3的图灵机,这比上面举例还要简单,理论上今天所有计算机的能力都不超过这台最小的通用图灵机,差别只在于效率上。
图灵研究的直接背景是希尔伯特第十问题。1900年新世纪开始时,德国数学家希尔伯特在巴黎第二届国际数学家大会上作了《数学问题》的著名讲演,提出了数学理论中23个最困难的问题,后来这个世纪的数学进展与这23个问题的解决密切相关。其中的第10个问题也称为判定性问题。原题目是:给定一个系数均为有理整数,包含任意多个未知数的丢番图方程,能否设计一个过程,通过有限步骤的计算,判定出该方程在有理数上是否可解。问题的一般形式是:是否存在对任何可定义的数学问题可解的判定方法?图灵研究论文的题目是“论数字计算在决断难题中的应用”,他从数的可计算去研究可判定问题,数的可计算是个技术细节更单纯的问题,同时图灵证明了数的可计算问题与逻辑上可判定问题等价。
图灵对于计算问题的研究是从观察分析人用笔在纸上进行计算过程开始,他设想了一个装置来模拟人的计算过程。图灵机的读写头相当于人的眼睛与手,纸带的输入是待求解的问题,状态是对前面过程的一种记忆,根据输入以及当前的状态,匹配适用的规则产生新的状态并进行写入与移动操作,这与人用笔在纸上计算时的决策与操作过程类似。图灵机装置使所研究的问题具体化,一个数学问题的可计算等于此问题的图灵机可计算。一个数学问题图灵机可计算,此图灵机就描述了此问题的算法。图灵是回溯到如何施行计算操作以完成计算来研究可计算或可判定问题的,这其中包含的一个概念是算法,目前本书还没有正式讲到。以图灵机的方式给出计算与算法的概念,在理论意义上,图灵机可看作抽象的计算模型。从物理实现的方向考虑,图灵机就是一种理论计算机的模型。由于技术上的原因,再发一篇文章后,最后的八篇只在同名公号里发布,本平台存在未审核通过的文章(即有断号),也可到那里阅读。
回到原问题,希尔伯特的判定问题可归为一台通用图灵机不通过实际模拟另一台图灵机,能否预测另一台图灵机的行为,如预测这台图灵机是否会停机。图灵研究的结论是否定的,希尔伯特的判定问题无解。这是与哥德尔不完备定理同样影响深远的结论。图灵机的思想及得到的结论,自图灵以来一直刺激着更多的研究与讨论,其中三个持续的主题是:
人的大脑是不是一台图灵机?
宇宙是不是一台图灵机?
在不违背物理规律的情况下,能不能设计出超过通用图灵机的机器?
Recommend
-
69
雷锋网按:本文为雷锋字幕组编译的技术博客,原标题Neural Turing Machines: a fundamental approach to access memory in deep learning,作者为Jonathan Hui。 翻译 | 赵朋飞 校对 | 凡江 内存是大脑和计算机的...
-
63
来源:返朴 fanpu2019撰文 | 王培人们往往根据自己的理解对一个概念下断言,其实对方使用的概念并不是你所以为的含义。要想避免这种误会,就不该对自己没有认真研究过的问题
-
7
程序员 - @James369 - 如果说计算机是图灵机演变的,那么图灵机的设计理念是什么?从百科查到:所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在
-
7
区块链存储 ARWEAVE:图灵机的纸带,可信计算新范式 数字共识的本质是存储共识。...
-
5
AI数学基础之:确定图灵机和非确定图灵机 2021-04-08 图灵机是由艾伦·麦席森·图灵在1936年描述的一种抽象机器,它是人们使用纸笔进行数学运算的过程的抽象,它肯定了计...
-
10
Marvin Minsky 的通用图灵机发现 0day 漏洞 WinterIsComing (31822)发表于 2021年...
-
3
论人类下一代语言的可能—4.1算术 我们主要从对算术...
-
6
论人类下一代语言的可能—4.2算术后的发展 算术是数...
-
3
论人类下一代语言的可能—6.3.2等价-替换原理 继续回...
-
1
9.3.2另一种计算机器2 本书把所构想的语言机器作为...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK