天才的思维殿堂——图灵和图灵机

如果没有接触过相关领域或专业知识,相信很多人对图灵——这位出生于1912年的英国大数学家的了解更多的来源于著名的电影《模仿游戏》。最近几年人工智能话题很火热,从图灵"人工智能之父"的称号,我们似乎就嗅到了这位大神不一般的意味,不过今天要聊的不是图灵在人工智能方面的贡献,要知道图灵还有一个称号是"计算机科学之父",为什么呢,这就要从图灵提出的一个有趣的概念——"图灵机"说起了。

图灵成长、生活于二战时期,这时候第二次工业革命早就将欧洲带入了电气时代,同时,二战倒逼了很多的科技进步发展,当时的欧洲的机械化也很普及了,车间和路上都有机器在轰鸣,图灵身为一位数学家,也想让数学计算机械化一下,试想一下:有那么一台机器,把任意一道问题送进去,然后随着火光蒸汽冲天,机器叮叮当当一顿执行,最后在机器出口,出来的不是什么螺钉、布料,而是精确的数学题答案,这简直太朋克了。

说干就干,不过大神就是大神,他没有立刻抄起螺丝刀和扳手,而是坐在窗前,先来了个灵魂发问:要设计的这台机器能够计算哪些问题?或者说,哪些问题是能够被机器计算的?有的朋友现在可能觉得莫名其妙,这个问题很重要吗?试想一下,图灵说了,我的机器就是用来计算一切可以计算的问题的,那就必须得回答一下,哪些问题可以被计算,才好进一步设计机器啊。

图灵机模型

图灵设想的机器是把每一步的操作指令写在一条纸带上的,纸带上划分了一个一个小格子,每一格是带编号的,里面记录的就是一个操作指令,这些操作指令都是这台机器能够认识的、有限种的基本操作(如果指令机器不认识,那就停机操作)。机器每次读一个格子,根据格子里面的指令进行操作。纸带有多长?图灵说了,你甭管它有多长,反正前面规定了我只处理可计算问题,所以你步骤理论上得是有限的,那这纸带保证你够用就行,要多长有多长,有无限长。

那我们就来试试吧,我们先做一台图灵1.0,我们给这台图灵1.0安装上一把锤子,然后让它能够识别两个指令:

A指令:砸一下,跳转到下一格纸带

B指令: 输出,停机

我们开始用这台机器,在纸带里面写上三万六千格的A指令,最后写一个B指令。把纸带输入。眼看着机器开始咣咣咣运行,每读一个格子,锤子就落下,然后跳转到下一格。就这样经过了三万六千锤,恭喜你,图灵1.0成功为你输出了一口章丘铁锅。

等一下,感觉有什么不对的地方,图灵1.0砸了三万六千锤,岂不是就得写三万六千格纸带?坑爹呢这是,除了省了一点力气,还是要人一步一步执行的,感觉意义不大啊。

显然,这种问题大神第一时间就想到了。所以图灵说,重点还在于机器本身能够识别的基本操作上(不妨叫机器预置的指令集)上。刚才设计的机器预置的指令太少了,不满足我的要求,这种机器我不承认它是我的机器(所以这种模型称之为图灵不完备),我要求机器不仅能够向下一格移动,还能返回向上一格移动,而且还能够根据每一格执行前或者执行后的数据状态判断一下向前移动还是向后移动。那我们再简单改造一下指令集里面的内容:

A指令:锤一下,转向下一格命令;

B指令:检查一下有没有锤够三万六千次,没有就返回上一格,否则就进行下一格指令;

C指令:输出,停机

那么好了,仅仅是添加了一下逻辑判断,现在我们重新编辑我们的纸带,仅有ABC这三个指令,然后机器开始执行,让我们看看发生了什么,首先机器读取指令A,进行一次锤击操作,转向下一个格子,发现次数没有够,转回上一格,如此循环往复,发现了吗,我们仅需要合理安排这三个指令,就可以完成一个可计算问题,所以,图灵机还有一个重要属性就是能够完成指令的循环执行,按照通俗的说法,如果你能够使用某台机器模拟出上面的执行效果,就可以说是这个机器是图灵机,或者称之为图灵完备的。上面只是列举的一个非常简单的例子,实际上,即使是一个非常复杂的数学问题,只要它满足图灵的可计算定义,就可以按照图灵机的思想进行设计出一台对应的自动化运算的机器,看到这里,相信已经对图灵机有一个感性的认识了,在前面的描述中,其实有心的朋友意会识到很多不严谨的地方,这仅仅是为了便于理解而已,实际上,图灵身为一个数学家,对问题的定义和描述是十分严格精确的,不妨给大家体会一下维基上的专业描述

数学天才图灵为什么死(天才的思维殿堂)(1)

我们也能感受到,图灵机模型已经不仅仅是可以用来设计数学计算机器的,而是一种对此类问题的高度抽象的方法,大神果然是大神,处理和考虑问题高度就是不一样,能够提纲挈领。

处在信息时代的我们,已经有意无意地接触了很多信息计算机知识,理解图灵机已经容易很多,在图灵的时代,虽然已经有了一些类似问题的讨论背景,但是作为一个时代的开创者,图灵凭借自己的天才在思维殿堂中为我们搭建了这个现代计算机的理论模型(冯诺依曼则完成了物理模型,当然这又是另一个话题了),直至今天,我们使用的计算机、手机等等信息处理设备都没有跳出图灵机的范畴。

最后,图灵机的相关内容发表在图灵的《论可计算数及其在判定性问题上的应用》,而且图灵大神的一生也很传奇,有兴趣可以自己了解一下。

最后膜拜大神本尊

数学天才图灵为什么死(天才的思维殿堂)(2)

,