获取内容资料
大数据AI

从计算理论到大数据图灵机

这里想用图灵自己曾说过的一句话来总结他为计算机科学和人工智智能所做出的贡献:有时候,正是那些意想不到之人,成就了无人能成之事。的确,他所成就的也的确是无人能成之事。1936 年,图灵发表了一篇题为“论数字计算在决断难题中的应用”的文章。文章中,图灵给“可计算性”下了一个严格的数学定义,并提出了“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的 计算 装置,用来计算所有能想象得到的可计算函数。自此,“图灵机”这一概念被永久地载入计算机发展史中。1950 年,图灵提出的一个关于判断机器是否能够思考的思想实验,这也是后来影响了计算机发展进程的“图灵测试(Turing test)”。测试的目的是为了检验某机器是否能表现出与人等价或无法区分的智能,这也是人工智能最早的思想雏形。1966 年,为表彰他在计算机领域的杰出贡献,特以他的名字设立了该领域内的最高奖项计算机界的诺贝尔奖图灵奖。

从计算理论到大数据图灵机

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

如果了解过可“计算性理论”(Computability Theory)这个学术分支历史的读者会知道,在图灵机被提出之前其实就已经有了能模拟人类所能进行的全部计算过程的模型被设计出来。例如图灵在硕士阶段的导师,普林斯顿大学的阿隆佐·邱奇(Alonzo Church,1903-1995)教授于1928年就提出的“Lambda演算”就是其中之一。但图灵机相比起其他计算模型的优势在于它极为直观易于理解,而且很容易通过机械或者电子技术来实现。因此,图灵机的价值被人们所发现后,迅速成为了计算机解决“如何计算”问题的基础,在计算理论上也成为了可计算性的对标物。当一个新的计算模型出现,人们会判定它是否能解决所有在算法上可计算的问题,如果是的话,它就被称为是图灵等价或者图灵完备的。今天,我们称某种程序设计语言是图灵完备的,意思也是所有可计算的算法都能够用这种语言来实现(如今天常见的C、C++、Java、JavaScript等都是图灵完备的,而HTML/CSS这些语言则不是图灵完备的)。由于笔者是个程序员,所以这里就再多写一句题外话,由于图灵机的结构简单性,不考虑编码效率和可读性的话,只需寥寥几个操作指令就能照着图灵机的定义实现出一款图灵完备的语言,制造出脑洞大开的效果,大家有兴趣的话可以搜索一下“BrainFuck”和“Whitespace”这两门语言看看。

图灵机不是具体的机器,而是一种思想模型,可以制造一种十分简单但运算能力极强的计算装置,以计算所有能想象得到的可计算函数。图灵机与冯·诺依曼机齐名,被载入计算机的发展史中。

“图灵机”这种虚拟的计算机器实际上是一种理想中的计算模型,它的基本思想是用机械操作来模拟人们用纸笔进行数学运算的过程。通俗地讲,图灵把“计算”这一件日常的行为抽象概括出来,看作是下列两种简单动作的不断重复:

我们现在了解了图灵机的定义和运行机制,能够用图灵机计算的数叫作可计算数。目前,得到了两个表格表示的不同图灵机,分别用来计算可计算数1/3和2/3。写过程序的人可以把这两个表当作两个程序,以方便理解后面的内容。

接着作者运用一个举一反三的简单例子,试图从图灵机的初态与终态变易的角度,解读图灵机的“确定性计算”与人工智能的“不确定性计算”的异同,以分析上述论证混淆了图灵计算与人工智能,并指出这样的认知混淆与“顾名思义”有关,属于认知上的“稻草人”谬误。

这个图灵机只做一件事情,就是表示一个可计算数1/3。为了达到举一反三的目的,我们可以把表1-1中的b和k的顺序更换一下,从而创造另外一个计算2/3的图灵机。表格如表1-2所示。

本书运用辩证发展科研创新法,通过对话、分析、游戏原创性地阐述和研究计算理论和大数据图灵机。全书共7章,主要内容包括:计算模型、可计算性、计算复杂性、图灵机的大数据应用和大数据图灵机等。本书内容深入浅出、通俗易懂,是一本对话式的著作,并将游戏穿插其中,妙趣横生,适合高等院校“计算理论”课程教学使用,也可作为研究院所的科研参考用书。

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注