我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合特码 > 多带图灵机 >

带你深入理解图灵机——什么是图灵机、完备

归档日期:06-22       文本归类:多带图灵机      文章编辑:爱尚语录

  介绍了天才图灵所处的时代背景,简述了那个时代的数学逻辑和可计算理论的发展状况,由此,我们可以站在更大的时间和空间维度以更高的视角看待问题。

  从上一篇文章我们知道图灵机首次提出在图灵的一篇论文《论数字计算在决断难题中的应用》中提出,原论文题目为《On Computable Numbers, with an Application to the Entscheidungsproblem》,英文好的同学可以从这个链接中查看原版的论文内容。

  这张图片什么意思?这么一个简单的机器/装置怎么会所有电子计算机的理论模型?

  相信大家看到这张图后都有这样的疑问,下面笔者带来由浅入深去理解图灵机的组成。

  图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,它运算过程看作下列两种简单的动作:

  一个无限长的存储带,带子有一个个连续的存储格子组成,每个格子可以存储一个数字或符号

  一个读写头,读写头可以在存储带上左右移动,并可以读、修改存储格上的数字或符号

  内部状态存储器,该存储器可以记录图灵机的当前状态,并且有一种特殊状态为停机状态

  控制程序指令,指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作(左移还是右移),并改变状态存储器的值,令机器进入一个新的状态或保持状态不变。

  当然这些只是理想的图灵机,因为现实中不存在无限长的存储带,更加图灵的理论这样的一台装置就能模拟人类所能进行的任何计算过程。是不是很神奇?我相信你肯定不相信,不过图灵是经过严格的数学证明,下面我们来看看图灵机的计算过程。

  估计你还是不明白,别急。看过《三体》的同学都知道三体人把地球人看做“虫子”,三体人的维度比地球三维世界高,就好像我们人类把看虫子一样。

  下面,我们把虫子放到一个二维的世界中,以虫子为例,给大家来说明最简单的图灵机模型(注:该例子非原创)。

  虫子所处的二维世界是一个无限长的纸带,这个纸带上被分成了若干小的方格,而每个方格都仅仅只有黑和白两种颜色。纸带的片段为:

  假设虫子的感官只有眼睛,并且它的视力短的可怜,只能看到当前所处格子的颜色

  虫子的操作系统、程序为:我们假设黑色是食物区,虫子吃到食物后前移一格,白色是空白区,没有食物后退一格,

  黑色前移一格白色后移一格在这个情况中格子的颜色是虫子的输入信息,集合为IN={黑色,白色},输出集合为 OUT= {前移一格,后移一格}

  现实中虫子肯定不可能傻到无线循环,虫子会有饥饿、吃饱的感受,食物吃了后也会消失。因此我们在情况下中改进下模型。

  虫子在黑色的格子时,如果是饥饿状态,吃掉食物把格子变成白色;如果是吃饱状态,后移一格

  虫子在白色的格子时,如果是饥饿状态,停下来等食物长出来涂黑;如果是吃饱状态,前移一格

  输入当前状态输出下一个状态黑色吃饱后移一格饥饿黑色饥饿吃完食物格子变白(不移动)吃饱白色吃饱前移一格饥饿白色饥饿等待食物长出来涂黑(不移动)吃饱

  在这种情况中,输入集合为IN={黑色,白色},输出集合为 OUT= {前移一格,后移一格,吃掉食物涂白,等待食物长出来涂黑},内部状态S={吃饱,饥饿}

  情况二,小虫的行为比情况以复杂了一些,但小虫最后仍然会落入无限循环当中。

  到此,如果你已经彻底搞懂了二维虫子是怎么移动的,那么你已经明白了图灵机的工作原理了!因为从本质上讲,最后的小虫模型就是一个图灵机!

  刚才用二维虫子说明了图灵机的工作原理,相信你的第一个反映就是,这样的模型太简单了!

  他根本说明不了现实世界中的任何问题!下面,我就要试图说服你,图灵机这个模型是伟大的!

  其实可以把二维虫子的模型进行更多扩展,以和现实世界基本或完全一致。因为二维虫子模型是以一切都简化的前提开始的,所以它的确是太太简单了。

  然而,我们可以把二维虫子的输入集合、输出行动集合、内部状态集合进行扩大,这个模型就一下子实用多了。

  二维虫子也可以拥有其他的感觉器官,比如嗅觉、听觉等等,而这些改变都仅仅是扩大了输入集合的维数和范围,并没有其他更本质的改变。

  二维虫子可能的输出集合也是异常的丰富,它不仅仅能移动自己,还可以尽情的改造它所在的自然界。

  进一步的,二维虫子的内部状态可能非常的多,而且控制它行为的程序可能异常复杂

  那么二维虫子会有什么本事呢?这就很难说了,因为随着小虫内部的状态数的增加,随着它所处环境的复杂度的增加,我们正在逐渐失去对二维虫子行为的预测能力。

  可图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。

  上面的解释比较抽象,通过上面的例子理解了什么是图灵机,图灵完备其实就很很简单理解了。

  简单来说,能够抽象成图灵机的系统或编程语言就是图灵完备的;一切可计算的问题图灵机都能计算,因此满足这样要求的逻辑系统、装置或者编程语言就叫图灵完备的。

  Bitcoin的脚本由于没有条件分支,循环等控制指令,回到上面的虫子的例子,虫子就不能根据当前状态,判断选择移动还是吃食物等一系列的动作,因此不满足图灵机的模型,不是图灵完备的。

  其实我们每一个会决策、会思考的人就可以被抽象的看成一个图灵机,也就是笑来老师一直说:每个人都有自己的操作系统,因为有元认知能力,还可以自己升级操作系统。

  输入状态集合就是你所处的环境中能够看到、听到、闻到、感觉到的所有一起,可能的输出集合就是你的每一言每一行,以及你能够表达出来的所有表情动作。内部状态集合则要复杂得多。因为我们可以把任意一个神经细胞的状态组合看作是一个内部状态,那么所有可能的神经细胞的状态组合将是天文数字!这就是人类的记忆。只要图灵机具有了内部状态,它就相应的具有了记忆。

  图灵机的程序指令是固定的。但是人类有学习能力,也就是说人的大脑会进化,操作系统会升级,所以大脑的实际程序规则是不固定,似乎图灵机模型包含不了。

  这个问题,其实图灵也已经考虑过了,其实就是我们现在一个大热门:AI,人工智能,计算机是否真的能实现人工智能?下一篇我们将和大家探讨这个话题。

本文链接:http://ticketsareus.net/duodaitulingji/703.html