图灵机：在没有计算机的时候，我们怎么谈论计算？
发布时间：2022-07-30 12:55:31 所属栏目：大数据 来源：互联网
导读：1950年10月，一篇题为机器能思考吗的论文横空出世。这篇论文中提出了一个令人细思极恐的测试，即在测试者与被测试者（一个真人和一台机器）隔开的情况下，通过通讯装置向被测试者随意提问，并让测试者猜测与自己对话的对方到底是真人还是机器。 在多次测试后
|
1950年10月，一篇题为“机器能思考吗”的论文横空出世。这篇论文中提出了一个令人细思极恐的测试，即在测试者与被测试者（一个真人和一台机器）隔开的情况下，通过通讯装置向被测试者随意提问，并让测试者猜测与自己对话的对方到底是真人还是机器。 在多次测试后，如果机器能平均让每个参与者做出超过30%的误判，那么这台机器就通过了测试，并被认为具有人类智能。 人们第一次意识到机器人可能具备人类智能，便是从此开始。这个测试便是令千万科幻爱好者津津乐道的图灵测试。这篇文章也为作者Alan Turing（艾伦·图灵）赢得了「人工智能之父」的桂冠。 而人工智能之路，或者说计算机发展史的源头，是一篇图灵在24岁时发表的论文。在这篇论文中，他给「可计算性」下了一个严格的数学定义，并提出著名的「图灵机（Turing Machine）」的设想。图灵机不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。 因为图灵发明了图灵机，于是时不时便有人跳出来宣称图灵其实「发明了计算机」。然而，图灵机与实际计算机器的设计并不相同。图灵机甚至不是机器的抽象模型。事实证明（有图灵言论为证），图灵机是一个人在桌上的纸张上书写的模型。那么，图灵为什么要发明图灵机，而图灵机又将引领我们去向何方？ 1 图灵的论文 “论可计算数” 解答这些疑问的最好办法是把课本放到一边，打开论文。如今，借阅一本1936年的期刊不需要填写借阅卡，也不需要等上一个小时让图书管理员从藏书室取来，我们只需要手捧一杯麦芽威士忌，在家里轻松访问谷歌即可。我们要寻找的那篇图灵论文如下： 论文地址：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf 论文中有一些错误，但瑕不掩瑜。正如Joel David Hamkins所说，图灵将可计算实数（computable real numbers）定义为具有可计算的十进制展开数，这实际上是行不通的，不过修正并不困难。 图灵在标题中就说明了这篇论文的写作意图：“论可计算数及其在「判定问题」中的应用 ”。其中“Entscheidungsproblem（判定问题）”询问是否存在一种有效技术来决定给定的一阶逻辑公式有效，即在所有解释中为真。 图灵将他的想法展开如下: 我们可以把一个正在计算实数的人比作一台只能满足有限数量条件q1，q2，... qR...的机器。这台机器中有一条长长的“纸带”穿过，纸带被分成很多个部分，这种一块一块的部分我们将其称为方块（square），每个方块都能承载一个“符号”...一些写下的符号会形成被计算的实数的十进制的数字序列，而其他的符号则只是“帮助记忆”的粗略笔记。这些粗略的笔记是可以擦掉的。我的论点是，这种在纸带上滑来滑去，滑到某个符号并对这个符号进行相应处理的运算方式，其中包括了所有用于数字计算的运算。 …… “可计算数”简单说来就是，其十进制的表达用有限的手段可计算的实数。按照我的定义，如果一个数的十进制的表达能被机器写下来，那么这个数就是可计算的。 图灵后续进行了定义和证明，这是一篇典型的数学论文，而不是典型的工程论文，在这种文章里读者想看到讨论如何实现文中所描述的某种机制。从图灵的标题和文章中我们可以看出，图灵主要关心的是一个实数到无限位小数的计算。 这篇论文还有许多其他重要贡献： 通用图灵机，以及以数字形式为机器编码的想法 如此编码的机器的停机问题，以及对角化的不可判定性 写罢这篇论文，图灵打开了理论计算科学领域的大门。 2 通用图灵机 我们不能确定是什么让图灵产生了通用图灵机（UTM）的想法，但一旦他想到了，他可能会认为通用图灵机的存在是显而易见的。因为图灵机的目的就是模拟一个在办公桌上工作的职员，而图灵机的操作和文员行为一样——根据机器状态和磁带符号，根据给定的转换规则列表执行这个或那个操作——显然需要一个图灵机来执行这样的例行任务。图灵的论文对于构造的细节有些粗略，但似乎没有人介意。 而如今，我们有了已经被设计得淋漓尽致的通用图灵机。几十年前，在剑桥大学，Ken Moody 博士编写了一个通用明斯基注册机： 链接：http://www.igblan.free-online.co.uk/igblan/ca/minsky.html 这样的机器有有限的寄存器，每个寄存器可以存储任意大的非负整数。它有一个有限程序，由三种不同类型的标记指令组成： 递增寄存器R并跳到标签L，或R+→L 测试/递减寄存器R并跳转到标签L0/L1，或L0↞R−→L1 中断。 这样的机器比图灵机更容易编程，尽管它们仍然不像真正的计算机。 Moody在N和N×N之间使用了标准的双射，将整数列表打包成单个整数。他编写了一个小型寄存器机器的小库，用于执行堆栈上推和从堆栈弹出等操作，并创建了一个让人想起真实处理器的获取-执行周期的设计。整个过程可见以下几张幻灯片。下图是机器本身： 下图则是机器的整体结构。(这两张图的作者都是剑桥大学理论计算科学教授Andrew Pitts。) 出人意料的是，这个机器的结构真简单！ 3 停机问题 停顿问题显然是不可决定的。否则，许多数学上的猜想都会难以解决，比如费马大定理：只要写一个程序，搜索x, y, z, n>2，使图片，并问它是否终止。然而，停机的不可判定性必须被严格地表达和证明。 与大众看法相反，图灵的论文并没有讨论停机问题，而是讨论了一个与停机问题相关的特性，他称之为“循环性”（circularity）。如果图灵机「只写下有限数量的第一种符号」（即0和1），它就是循环性的。我想，循环性之所以重要，是因为图灵特别喜欢把实数近似为无限的二进制字符串。物理学家Christopher Strachey在1965年给《计算机杂志（Computer Journal）》的一封信中声称，图灵告诉他一个关于停机问题不可判定性的证明。 （编辑：我爱制作网_潮州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330565号