人工智能通识-科普-图灵机1

人工智能通识-科普-图灵机1,第1张

图灵机Turing machine是英国科学家阿兰·图灵Alan Turing在1937年构想的一个计算机原型,图灵机被计算机届公认为现代计算机理论的开端,可以说,没有这个图灵机,就没有现代计算机的诞生,因此,阿兰图灵也被称之为计算机科学之父。

以上是教科书式的内容,但到底图灵机是怎么个东西,原理是怎么样的,为什么这么有意义,却很少有人真的说清。

图灵首先是个数学家,他有一个超前的想法,那就是建造一台机器,用来模拟人们用纸和笔进行运算的过程,他仔细思考之后认为,人的计算过程就是两种动作的组合:

每次除了写擦和换位置,另一个关键因素就是人的思考和决定,而这个思考又是依赖两个因素进行:

开始的配图看起来有些神秘,看上去也很复杂,但那只是艺术家的幻想罢了,真实的图灵机并不复杂。

为了模拟人做运算的过程,图灵构想的机器包含以下几个部分:

下面是一个用于翻转0和1的图灵机程序。

只要我们把指针放在纸条最右侧的非空位置上,过一会儿运行完毕之后,整个纸条上的连续的0和1就会被翻转过来,最终指针也会停留在最左侧位置上。

END

所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。

在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

在某些模型中,读写头沿着固定的纸带移动。要进行的指令(q1)展示在读写头内。在这种模型中“空白”的纸带是全部为 0 的。有阴影的方格,包括读写头扫描到的空白,标记了 1,1,B 的那些方格,和读写头符号,构成了系统状态。(由 Minsky (1967) p.121 绘制)。

扩展资料:

通用机型

对于任意一个图灵机,因为它的描述是有限的,因此我们总可以用某种方式将其编码为字符串。我们用 <M>表示图灵机 M 的编码。

我们可以构造出一个特殊的图灵机,它接受任意一个图灵机 M 的编码<M>,然后模拟 M 的运作,这样的图灵机称为通用图灵机(Universal Turing Machine)。

现代电子计算机其实就是这样一种通用图灵机的模拟,它能接受一段描述其他图灵机的程序,并运行程序实现该程序所描述的算法。但要注意,它只是模拟,因为现实中的计算机的存储都是有限的,所以无法跨越有限状态机的界限。

经典图灵机及其许多变形识别语言的能力都是相同的,正因为如此,图灵机可以作为计算的一般模型。另外,通用图灵机 (可编程图灵机) 是存在的,通用图灵机可以模拟任意一个图灵机,这也是将图灵机作为现代计算机的形式模型的根本原因。

参考资料来源:百度百科—图灵机


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/11167028.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-14
下一篇 2023-05-14

发表评论

登录后才能评论

评论列表(0条)

保存