登陆

架构思维训练之自己推导图灵机

admin 2019-09-26 363人围观 ,发现0个评论

前言

上节课我们谈到了架构思维就是创造思维,需要一直刻意训练才能掌握。鉴于计算机组成原理的奠基性位置,是学编程、架构的必备知识。因此从推导组成原理开始,在学习知识的同时训练架构思维。

万事开头难,推仲浩林导要有起点。现代计算机及编程语言源自同一个理论模型—图灵机,以图灵机为推导起点再适合不过。

为什么从图灵机开始推导?

古希腊大哲学家柏拉图,曾经惊世骇俗的提出了人生三问:“我是谁?从哪来?到哪去?”。这三个问题千百年来,引起人们无数的思考和探索,至今仍无定论。

三个看似极简单却极难回答的问题,似乎隐藏着一条可以探寻的线索。如果我们将时间轴打开,重新排列这三个问题,俨然就成了:“我从哪里来?我是谁?我要到哪里去?”。似曾相识,像极了本山大叔春晚的经典小品《昨天今天明天》。

“探讨严肃的哲学问题,不许开玩笑!”,好了,不走神,请接着回来。

按照这个顺序,似乎只要能够沿着起源,理清发展脉络,就能看清当下的自己,仿佛还能通达未来。这也难怪,以色列新锐历史学家尤瓦尔赫拉利,在写完《人类简史》后,接着就推出了《未来简史》和《今日简史》。这似乎昭示着,能够看清过去,就拥有了理解当下和把握未来的能力。

按照这种以史为鉴,面向未来的思路,我们要探究计算机的组成原理,就要从计算机的起源开始。那将是一个漫长的历程:“Long long ago,人类的祖先……”。“请打住!大家时间宝贵,捡重点!”,好了,不啰嗦。计算机的发展,可以追溯到北宋时期中国人发明的算盘,近代大数学家莱布尼茨发明的手摇式计算器,19世纪英国发明家巴贝奇发明的差分机。

说到差分机忍不住要提一下,这台以蒸汽机为动力由大量齿轮构成的“计算机”,虽然最终没有成功,但却诞生了史上第一位程序员,可以说是编程这个行当的开山祖师。不要听错了喽,这位祖师可是一位女生,而且一位非常漂亮的女生,她叫阿达洛芙莱斯,感兴趣的小伙伴网上搜一下她的画像便知。

阿达是一位数学家,是英国大诗人拜伦的女儿。看似男生众多的行当,创始人竟是一位优雅的大美女,说明女生还是很适合这个行业的哦。“哎!怎么说起妹子就高兴起来了呢?咱们还要继续呢!”。对,不打岔!前面讲的这一切的努力,最终促成了现代计算机的起源——图灵机。

图灵机并不是一台真正的计算机,它只是一个计算模型,是一台抽象的机器。“是啊,好抽象啊!”。不要急,本文将先讲解一下图灵机是怎么来的,然后就通过一个生活中的事例,把它推导出来。“没有听错吧?用生活中事例推导!”。对,伟大的发现都源自生活,苹果砸在牛顿头上就砸出来个万有引力,当然此事被证明是杜撰的,但却说明生活中充满了灵感。生活中的一件事就让图灵发现了图灵机。

有了图灵机的相关知识,我们就站在了推导计算核心(即CPU+内存)的起点上。之后我们就可以按照图灵机提出的理论模型,开启计算核心的“创造”之旅。

计算科学之父简介

要讲图灵机,首先简单介绍一下图灵机的作者,被称为“计算科学之父”、“人工智能之父”的艾伦图灵。

先看一下这张照片:


计算科学之父:艾伦图灵


这就是图灵,一位颜值超高的科学家。前面我们还提到过集美貌才华于一身的程序员祖师娘阿达,可见计算机也是一个高颜值的行业。“谁说IT工程师邋遢不修边幅,我表示反对!”嗯,反对有效。

好了,接着说图灵。图灵是英国著名的数学家、逻辑学家,二战期间曾协助英国军方破译德军密码。出于破译工作的需要,他参与了世界上最早的电子计算机的研制工作,并由此获得了英国政府颁布的最高荣誉奖章,为盟军取得二战的胜利作出了突出贡献。

关于图灵的生平,我们简单介绍到这里。但有一点我们需要注意,图灵作为数学家参与密码破译工作,一定会遇到大量的数学计算。二战所处的时代是机械化的时代,战争的紧迫,密码破译仅靠人力计算肯定是不够的。这就促使以图灵为代表的科学家,思考能否通过机器实现数学问题的计算,这就引出了图灵机的提出。

为什么提出图灵机

如我们之前所分析,由于战争的现实需求,迫使人们产生一个愿望:能否使用机器进行计算。

要实现这个愿望,不能靠祈求阿拉丁神灯之类的方法。科学时代要使用科学的方法,在实现这样的机器之前,首先要能够在理论上证明使用机器进行计算是否可行。只有理论上通过之后,才能对实践进行精确的指导。当然这里的论证主要是指数学论证,而这正是科学家的工作,是由牛顿论证运动三大定律为肇始的科学工作方式(由牛顿巨著《自然哲学的数学原理》所确定的方式)。因此,提出可行的机器计算模型,就成为图灵这样的先驱的工作重点。

为此图灵进行了如下思考:首先,需要确定可计算问题的范围,排除掉那些不能被计算的问题。据一位苏联数学家的证明,不能计算的问题比能计算出答案的问题还要多;其次,再排除掉那些不能在有限时间内计算出结果的问题,这就意味着问题的计算步骤必须是有限的;最后,对可在有限时间内的计算的问题,提出一个假想的机器模型,让它不断运行,最后机器停下来的时候,数学答案就计算出来了。

面对这些问题,图灵出色的完成他的论证,提出了图灵机模型。严格来讲图灵机是一种数学模型、计算理论模型。图灵机一旦被实现,就可以用来解决任何可计算问题,所有的现代计算机,包括量子计算机都没有超出图灵机的理论范畴。

目前作为读者的你,对图灵机了解应该达到了一种“脑瓜子嗡嗡地”程度了吧。如果是,不要着急,咱们前面说过从生活中的例子就能推导出图灵机。当然我们能推导出的只是一个好理解的概念模型并不是图灵机的精确定义,至于数学论证,“臣妾做不到啊!”,恳请大家高抬贵手放过在下吧!

另外,再补充一下。上面提到的“判断一个问题能否在有限时间内计算出结果”,引出了数学界有名的“停机问题”。简单来说:上述判断是由人来判定?还是由运行算法的机器来判定?当然,我们希望由机器来做,但是机器能判断出来吗?事实是机器无法判断,这个结论是被论证过的。停机问题,只能由人来保证:不能让架构思维训练之自己推导图灵机一个不能停止的算法在机器上运行,否则机器将陷入无法停机的状态。

有过编程经验的小伙伴,一定都知道不要编写 “死循环”的程序。对这个问题简单理解就是,如果程序不能停止,势必让计算机陷入“哥忙着呢,不要烦哥”的状态而无法自拔。如果程序能停止,那还要计算机判断干啥? 所以,停机问题是编程人员不可推卸的分内活,死循环这锅,计算机可不背。


推导图灵机模型

各位小伙伴只要有小学数学基础,咱们就可以一起愉快的玩耍推导图灵机了,当然小学数学是体育老师教的除外。相信大家的数学基础都是好的,直接出一道难题吧,10以内的四则混合运算!请看题:

10-3*2+(6-2)/2=?

大家应该很快算出答案:6。没错!结果就是6。算对了小伙伴值得表扬,说明我们确实只是普通人。难怪算了这么多年的小数数学甚至高等数学,都没有提出图灵机。如果你看到此题并不忙于计算而是陷入沉思:此题看似简单,实则暗含深意,虽道不出其中三昧,却隐约感觉暗藏玄机。那就要恭喜你了,说明你离大师的境界近了一步,虽然还相差十万八千里,毕竟是近了些。好了,不卖关子了,咱们就看一下用图灵的思维这道题该怎么做。

假设做题的场景:题目写在纸上,我们用笔答题。

不着急做,先从提问题开始,下面的每一部分都由问题引出,标题可以不用管,沿着问题看下去自然就懂了。

(一)算法和指令

第一个问题:题目的内容是啥?

嗯,是四则混合运算,由多个加减乘除组成,需要进行多步计算。如果把混合运算看做一个计算任务,每一步计算(如加法)就是一个子任务。

好,先看子任务。每个子任务有操作数、操作符及运算结果,就像加法:加数和被加数架构思维训练之自己推导图灵机是操作数,加号是操作符,和是结果。由此可知,每个子任务由功能(即操作符)、输入(即操作数)和输出(即结果)三部分组成。

再看混合计算任务,计算需要遵循规则:先算括号内,再算乘除,再算加减。这说明子任务之间是有顺序的,且可以存在数据依赖即子任务的输出结果可作为下个子任务的一个操作数。子任务按照顺序全部执行完成后计算任务结束。

经由上述分析可以讲解算法和指令的概念了,其中算法对应于计算任务,指令对应于子任务,具体内容如下:

算法包含有限个计算步骤,计算步骤之间存在一定的运行顺序和可能的数据依赖,计算步骤全部执行完成后算法结束。每个计算步骤称为一个指令,指令由指令功能、输入、输出构成。每个指令必须在有限时间内完成以确保算法结束。

接下来,我们将对上面题目稍作变化,注意啊,这里要用到小学数学的高阶课程了。我们把题目代数化,用变量代替数值,形式如下:

	a-b*c+(d-e)/f=?

将算法用变量描述之后,就得到了一个纯粹表达算法逻辑的代数形式。注意该形式中只有变量可没有具体数据,只有将变量代入数值后才能计算。通过引入变量将算法逻辑和数据进行了分离,这就可以构建通用的算法逻辑,灵活解决问题。

比如,长方形面积的计算逻辑为“长*宽”,表达为“a*b”,a、b可以代入任何值,这就可以把天下所有长方形的面积计算出来。于此同时,算法也具备了输入和输出,变量就是算法的输入,结果就是算法的输出。

以上是对算法和指令的简单介绍,这里再引申一点内容:前面提到的算法逻辑是用代数形式表达的,如果用程序语言表达呢?嗯,这就是编程了。再一个,将算法逻辑和数据分离,意义重大,咱们后面还会再讲。另外,前面我们用计算任务和子任务表示算法和指令,看似平淡无奇,实有深意且很重要。这里算是卖个关子,后面大家逐渐体会。

好了,下面我们将追随大师的思维继续思考。

(二)存储带

第二个问题:题目代表计算任务,算法内容就是任务的信息,可以分成两部分:算法逻辑和数据。好了问题来了,信息的载体是什么?或者说任务信息被存储在什么介质上呢?

按照咱们答题场景的约定,当然是写在纸上了。写哪儿呢?当然是在纸上的某个位置写了,这就意味着得在纸上确定书写位置。纸上的位置怎么确定呢?是啊,一张白纸啥也没有,肯定不能精确定位。

看到这儿,您可能嘀咕了:这不有病吗,一张白纸估摸着写上不就完了吗?还精确定位?这又不是GPS。您可别忘了,在科学家眼里一张纸可是大有学问了,那得是由无数的原子按照某种结构排列而成的…….,所以啊科学就得较真,可不能含糊,为了科学精神咱先忍一忍。

言归正传,纸上要想定位?这可难不倒我。咱毕竟是有小学数学基础的人,小演草咱可用过。没错,小演草上分出好多行,指定某一行就可以定位书写了。写的时候得一个字符一个字符的写,于是可以按字符大小把这一行分成多个格子。“哎吆,这会儿满意了吧,终于可以精确定位了”。没错,指定好起始行、起始格,就可以书写了。一行写满了,再换行写。

可是图灵要解决的计算问题,绝不是几张纸就能写完的,否则何必需要机器来计算呢?所以啊,得需要一个大容量的存储介质。展开我们的想象力,既然计算的书写量这么大,再写几页也写不完,那咱干脆就不换行了,一直写下去,直到永远……。

这样一来就出现了由无数个连续的格子组成的一行,每个格子可以填写一个字符。而且格子还可以无限次擦写,不用担心被橡皮擦破,多神奇啊!嗯,这就是做梦的力量。有了这么神奇的一行存储介质,无论多少计算问题都可以存储下了,这下破译德军的密码可就指日可待了。

图灵把上面这样一个由无数连续格子组成的存储介质称为存储带。算法可以存储了接下来就要解决算法执行的问题。

(三)读写头

第三个问题:回到我们的做题场景,现在我们把题目写在了存储带上,也就是把算法信息保存在存储带上,接下来就要进行计算了。计算装置当然就是我们的大脑,算法在存储带上,问题是如何把存储带上的算法信息传送给大脑呢?

	题目:10-3*2+(6-2)/2=?

那还不简单,用眼睛啊!题目反射的光线进入眼睛成像,大脑可以辨识图像的含义,这样就接收到算法信息了,然后就能计算了。

第四个问题:大脑是如何计算的呢?

首先我们的眼光定位到题目的起始位置,题目默认的读取顺序是从左向右,读入第一个字符“6”。大脑识别出数字后,根据已经掌握的四则混合运算法则,就知道这是一个操作数,还要往右读。眼光右移一格看到“-”。“这眼睛怎么一格一格的移动呢,我可是一下子就看到整个表达式了”,嗯,这正是咱和科学家的区别,科学就是要精确嘛。

看到减号大脑就知道可能要做减法,但乘除优于加减,还要接着往右读。读到“3”、“*”之后仍不能确定,因为括号优于乘除,再接着往右读直到读入“+”,这下可以确定了,有减有乘当然先算乘。

接着,把目光移动到乘法的第一个操作数“3”,顺序读入“3*2”计算出结果6。这时左减右加(即“10-6+…”),加减平级左为先,算减法,眼光移动到最左边读入“10”并计算10-6结果为4,再接着往下算不再赘述,直到算出最终结果。

第五个问题:计算出结果后,存储带上可能还有很多算法要算,可能还有别的事要做。总之为了防止遗忘,需要把结果长久保存。那如何保存呢?

正所谓“好记性不如烂笔头”,把眼光定位到等号右边的格子,用我们的手握着笔把结果写入存储带中就可以了。好了,到此为止,本计算任务结束。

第六个问题:上面三个问题分析了大脑的解题过程,紧接着我们不禁要问了:这个解题过程是怎么达成的?或者说存在哪些关键要素使解题过程得以实现?

这就需要我们对解题过程进行再思考,从中提炼出关键要素。

首先,算法信息通过眼睛从存储带传送给大脑,眼睛作为信息接收装置,负责定位和读入。另外,计算出结果后在眼睛的定位下,用笔将结果写入存储带的目标位置。这里的关键要素是信息的输入和输出,其中信息输入涉及读取定位(即眼睛在存储带上确定读入位置)、内容读取和读入信息传输(即内容通过光线反射进入眼睛成像),信息输出涉及写入定位(即眼睛在存储带上确定写入位置)、写入信息传输和内容写入(即大脑指挥手握笔写入存储带指定位置)。

其次,大脑之所以能够识别并执行输入的算法信息,是因为我们曾经习得了四则混合运算法则,在大脑中固化了这套运算逻辑。之后再有此类算法信息输入,大脑就可以运行这套逻辑来计算。固化的运算逻辑是计算过程的核心,控制着输入、输出的移动(即读写定位)以及算法指令的解释和执行。这里的关键要素是固化的运算逻辑。

再有,有了输入、输入和运算规则,固化的运算逻辑就能运行了吗?回忆问题4的计算场景,当计算了“3*2”之后,大脑并没有接着“+”向右算,而是回过来判断“10-6+…”,这说明大脑知道之前碰到过“-”,对经历的计算步骤有记忆。而且“3*2”的结果6也必须记在脑子里,否则没法往下算。由此可见固化的运算逻辑,还需要根据大脑记忆的计算步骤和中间结果,才能准确判断出下一步的行为,从而控制输入、输出和计算。

而记忆是对过去场景中某个瞬间状态的存储,一如相机拍照,照片就保持了按下快门那一刻镜头中景象的瞬时状态。因此,这里的关键要素就是计算过程中的状态存储(如对中间结果和已经历步骤的存储)。

至此,我们大脑中固化的运算逻辑终于可以欢快的执行算法了。也由此我们得出了大脑计算的关键要素:输入、输出、固化的运算逻辑、计算过程的状态存储。当然这些关键要素背后有一个共同的主体,那就是我们聪明的脑袋。

图灵正是受此启发,假想了一个机器脑袋,它拥有上面全部要素包括:能够读写存储带的输入/输出,通过在存储带上移动进行读写定位;固化的运算逻辑实现为机器内置的固定程序;代表状态存储的记忆实现为存储设备即内部状态存储器。图灵把这样一个机器脑袋称为读写头,读写头和存储带就构成了图灵机模型。

(四)图灵机模型

下面我们将简单描述图灵机模型的运行机制:

开始,读写头在存储带上定位到算法的起始位置进入初始状态。接着,读入算法指令,内置固定程序解析指令含义,并结合内部状态控制计算、移动读写头输入输出,于此同时内部状态存储器保存当前状态。不断重复上述过程,直到全部指令执行完,算法结束,读写头进入停机状态。

这段描述如果让大家感到晦涩,有胸闷之感。不妨把之前题目“10-3*2+(6-2)/2=?”用上述机制在脑中模拟运行,症状便可缓解一二。如不奏效,也无妨,下节“图灵完备”咱们还会通过一个示例进行讲解,相信届时自无大碍,还请诸位宽心。

图灵认为有了机器脑袋这宝贝,天下所有可计算的问题,都能解决绝无例外。从此读写头便可在存储带上肆意驰骋,破尽天下可算之题,破解德军密码那绝对是分分钟的事。想至此,图灵心生欢喜,不禁放声大笑。“嘿!嘿!嘿!上铺的兄弟,你这是肿么了?这大半夜的又是梦话,又是大笑,多渗人啊!”。图灵闻此方才惊醒,原来只是一梦。虽说是梦,但那读写头和存储带的形象却在心中了了分明。(注:以上情境纯属虚构)于是图灵画下此图:


图灵机的假想模型


只有一个概念模型还是远远不够的,必须得精确证明这个图灵机模型能够计算所有有限步骤内可计算的数学问题。数学是书写科学的语言,作为科学家的图灵必须要给出图灵机模型的数学证明。图灵的伟大之处也在于此,他提出了图灵机模型并给出了严格的数学证明,从理论上论证了用机器替代人脑计算的可行性,为计算机的实现奠定了理论基础。到此,咱们对图灵机的推导算是告一段落。

(五)推导复盘

下面我们将从三个角度复盘图灵机的推导过程:

第一,我们是从用机器模拟人类计算过程的角度推导出图灵机。为什么能这样做呢?从信息的角度看,人自身就是一个信息处理的生物机体。我们的眼睛、耳朵、鼻子以及布满全身的各类感受器,就是信息的接收装置。通过神经系统把收集到的信息传送给大脑(神经中枢),大脑对信息进行加工处理后产生反应信息,再通过神经系统传达给各类效应器(如:肌肉、腺体等)产生具体反应。

而我们用机器计算本质上就是让机器处理信息,当然可以借鉴人对信息的处理方式来实现了。这个思路对软件开发领域的影响很大,比如面向对象、并行计算等。 本教程的后续章节,也将沿用这个思路进行推导。

第二,推导中先设置了一个具体的解题场景,再由此推导出图灵机模型,而图灵机是可以解决任何可计算问题的。这说明我们从一个从具体解决场景推导出了一个普遍解决方案。这个过程是如何实现的呢?

下面我将用读写头的推导过程为例进行说明。首先,我们通过3个问题分析了大脑的解题过程,这是面向具体场景的并且分析了过程中的各个环节,因此这是对具体场景的分解及分析。接着,在前面分析的内容之上,我们提出了一些概念比如:输入、输出、固化的运算逻辑、状态存储等,这些概念正是对具体内容的提炼。最后,我们理清这些概念的关系并封装到读写头中,再确定读写头与存储带的协作方式从而得出图灵机,这是一个概念的整合过程。正是利用了“分解—提炼—整合”的思维方式,实现了从具体场景到普遍方案的推导,这就是抽象思维过程。

抽象思维在软件开发中是提炼通用组件、构建架构的关键能力,如果你具备这种能力,那么恭喜你。如果你不善此道,也没关系,抽象思维是可以被训练的,而且必须要在生活及工作中刻意训练才能运用自如。这里咱不空谈方法,本教程后面会有大量抽象思维的推导过程,各位读者只需看完后(如本节图灵机的推导)掩卷而思,重新推导复盘,久习之必有所得

第三,图灵从人用纸笔计算中抽象出图灵机的假想模型,接着用数学进行了论证。这里暗含着一种工作思路:提出假设;验证假设。首先需要根据某种逻辑提出一个假设;然后,要对假设进行验证,验证的方式包括理论验证(数理证明)、实验验证、事实验证等,验证结果是对假架构思维训练之自己推导图灵机设的证明或证伪。这一思路,正是本教程所提倡的演进式架构中的重要方法,大家可在后面课程中去体会。

最后,再重申一下。我们推导出的图灵机模型不是它的精确定义,只是一个好理解的概念模型。如果大家对图灵机的精确定义感兴趣,可以去看图灵的论文《论数字计算在决断难题中的应用》。不过,我要提醒一下,看这个小学数学基础可不行,“外婆交(教)大”的也难,大家需量力而行,且行且珍惜。

请关注微信公众号
微信二维码
不容错过
Powered By Z-BlogPHP