我要投搞

标签云

收藏小站

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

当前位置:多盈娱乐注册 > 多带图灵机 >

什么是图灵完备?

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

  断断续续研究这个问题许久了,希望这个回答能有帮助,也算是我私心为了以后有迹可循写下一篇学习笔记。答案中如果有任何错误还请指出。

  这是一篇旨在帮助理解图灵机及相关概念是什么,而非证明其正确性的回答,它包含以下内容:

  图灵机(Turing Machine)是图灵在1936年发表的 On Computable Numbers, with an Application to the Entscheidungsproblem(《论可计算数及其在判定性问题上的应用》)中提出的数学模型。既然是数学模型,它就并非一个实体概念,而是架空的一个想法。在文章中图灵描述了它是什么,并且证明了,只要图灵机可以被实现,就可以用来解决任何可计算问题。

  一条无限长的纸带(tape),纸带被分成一个个相邻的格子(square),每个格子都可以写上至多一个字符(symbol)。

  一个字符表(alphabet),即字符的集合,它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符(blank),意思是此格子没有任何字符。

  一个读写头(head),可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容,此外也可以每次向左/右移动一个格子。

  一个状态寄存器(state register),它追踪着每一步运算过程中,整个机器所处的状态(运行/终止)。当这个状态从运行变为终止,则运算结束,机器停机并交回控制权。如果你了解有限状态机,它便对应着有限状态机里的状态。

  一个有限的指令集(instructions table),它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南,里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时,擦除,改写为1,并向右移一格。此外,令下一状态为运行。”这样的命令。其实某种意义上,这个指令集就对应着程序员所写下的程序了。

  在计算开始前,纸带可以是完全空白,也可以在某些格子里预先就有写上部分字符作为输入。运算开始时,读写头从某一位置开始,严格按照此刻的配置(configuration),即:

  来一步步的对照着指令集去进行操作,直到状态变为停止,运算结束。而后纸带上留下的信息,即字符的序列(比如类似“...011001...”)便作为输出,由人来解码为自然语言。

  要重申一下,以上只是图灵机模型的内容,而非具体的实现。所谓的纸带和读写头都只是图灵提出的抽象概念。为便于理解打一个比方。算盘虽然不是图灵机(因为它没有无限长的纸带,即无限的存储空间),但它的行为与图灵机一致。每一串算珠都是纸带上的一格,一串算珠上展示的数字便记录着当前格中的字符(可以是空白,可以是 12345 )。人类的手即是读写头,可以更改每串算珠的状态。算盘的运行遵循人脑中的算法,当算法结束,算盘停机。

  在文章中,图灵所做的事是证明了,假设上述模型里所说的功能都能被以某种形式物理实现,那么任意可计算问题都可以被解决。这里所说的可计算问题,涉及到计算理论(Computation Theory)的概念。这个领域的概念很繁杂,先简单梳理一下。

  在计算机领域,或者说自动机领域,我们研究的一切问题都是计算问题(Computational Problem)。它泛指一切与计算相关的问题。

  计算问题有的可以解决,有的不可解决。这就引出了计算问题的可计算性(Computability)。它可以被理解为“是否存在一个算法,能解决在任何输入下的此计算问题”。如上面的问题 1,我们当然可以找到一个算法来解决判断任意正整数 n 是否为质数的问题(比如从2遍历到 n-1,看 n 是否可以整除它)。所以,问题 1 就是可计算的。

  也有一些不可计算的计算问题,比如著名的停机问题(Halting Problem)。它的表述是这样的:给定一段程序的描述和该程序的一个有效输入,运行此程序,那么程序最终是会终止,还是会死循环下去?

  这个问题很绕人,有点像那个著名的理发师悖论,但它确实是一个计算问题。更具体的,它是一个不可判定问题(Undecidable Problem)。即不存在一个通用算法,可以在任意输入下解决此问题。图灵在文章里很优雅的用反证法推翻了假设“假设有这么一个算法可以解决任何停机问题”,从而证明了这样的算法并不存在。具体证明过程网上的资料非常丰富,我就不再花篇幅了。

  回到这一节的主题。简而言之,对于一个问题,对于任意输入,只要人类可以保证算出结果(不管花多少时间),那么图灵机就可以保证算出结果(不管花多少时间)。

  图灵完备性(Turing Completeness)是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言,也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时,就称它具有图灵完备性。直白一点说,图灵完备性就是我给你一工具箱的东西,包括无限内存、if/else 控制流、while 循环……那么你现在图灵完备了吗?

  概念本身倒是非常直观,但整件事似乎还是让人云里雾里。我曾经一直不懂的就是为什么图灵给出的那个命题是正确的。换句话说,凭什么有了纸带以及其他的那一套东西,就可以自信解决任意可计算问题呢?尽管我不能通读他的那篇论文里的证明,但是通过一门叫做 Brainfuck 的编程语言,还是可以获得一些直觉。

  如今主流的编程语言(C++,Java,Python,以及等等等等)都是图灵完备的语言。关于语言优劣之争也只是在其封装、优化等方面,以及因为这些区别而产生的“不同语言适用于不同情况”的争执。如果我们回到最底层,就会发现它们可以实现的功能其实完全一样,并且本质上就是一个图灵机。

  在1993年,Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了——它一共只含有 8 个有效字符,每个有效字符就是一条指令。语言虽然极致轻量,它却是一门图灵完备的编程语言。如果能理解它的工作原理,那么对于理解图灵机是有很大帮助的。

  BF 的工作机制与图灵机高度一致。首先它存储数据的方式是一个不限长的一维整数数组,里面的数值全部初始化为 0。此外,有一数据指针,每一时刻都指向数组的某一任意元素。指针可以向左/右移动,也可以读取/修改当前值。

  有了这些工具,我们可以很快做出一个计算乘法的程序。因为 ASCII 表中 A 对应的值为 65,可以使用 5 * 13 算出 65 并输出得到字符 A。

  把指针初始处的格子命名为 cell 0,cell 0 右边的那个格子命名为 cell 1。那么第一句将其递增 5 次变为 5。然后,循环执行“右移指针,递增 13 次, 左移指针,递减 1 次”。当 cell 0 的值最终被递减为 0 的时候,循环结束。此时 cell 1 的值执行了 5 次“递增 13 次”的操作,即 65。指针右移至 cell 1,输出此格子,则在终端会看到 A。

  我写这个例子的目的是演示只用图灵机的模型,就可以确实计算出乘法的结果。那么自然更加复杂的计算也可以被拆解成图灵机操作(尽管可能非常琐碎)。此外,这个语言因为简洁,也是第一次练习写编译器的一个非常好的选择。

  图灵机模型符合直观但是不容易联系到具体的计算上,我从递归函数的角度来说一下。

  这三种函数通过前两种操作组合出来的所有函数被称为原始递归函数(primitive recursive function),原始递归函数+极小化组合出来的函数叫偏递归函数(partial recursive function,参考读《The Little Schemer》时,看到第9章有partial function和total function两个概念,不是特别懂,请赐教?)。图灵机和偏递归函数等价,一个语言如果是图灵完备的,那这个语言可以完全模拟这三种函数+三种操作。如果一门语言只能模拟原始递归函数,那你就无法写出无限循环。想想单片机、服务器、操作系统,如果没有无限循环跑起来该有多痛苦,这就是为什么通用编程语言都要图灵完全的原因。

  顺便一提,图灵机是我们已知能实现的最强的计算模型。最近媒体经常报道的量子计算机仍然是图灵机,只是特定算法快一些。

  顺便二提,根据Kleene正规型定理,任意偏递归函数都可以由原始递归函数经过一次极小化得来,所以写程序的时候如果发现两层以上的无限循环要格外小心,很可能逻辑是错的。

  图灵不完备的语言常见原因有循环或递归受限(无法写不终止的程序,如 while(true){}; ), 无法实现类似数组或列表这样的数据结构(不能模拟纸带). 这会使能写的程序有限

  图灵完备可能带来坏处, 如C++的模板语言, 模板语言是在类型检查时执行, 如果编译器不加以检查,我们完全可以写出使得C++编译器陷入死循环的程序.

  图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的.

  图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情,可以解决所有的可计算问题。

  一台计算机也是一个图灵机,一个图灵完备的语言意味着这个语言可以使用计算机完成任何计算机可以完成的任务,也就能够发挥计算机的所有能力。(这句话有点绕口)

  一般概念上图灵不完备指的是计算能力不如图灵机的。当然也存在计算能力可能更高的,比如说非确定图灵机。但是到底高多少,还是本质是一样的。应该没人知道,这也就是P和NP的问题。(这一段话我也不知道说的对不对,因为没印象了#_-)

  首先要搞明白这套理论其实需要自动机方面的知识。大致是人们很好奇需要什么样的机器才能表达出某种语言(字符序列的集合)。

  就表达能力来讲,大致可以分为有限状态自动机,下推自动机和图灵机那么几档。(当然还有别的很多)前者所能表达的语言是后者的真子集。

  有限状态自动机只能表达正则语言。下退自动机能够表达上下文无关语言。而图灵机的语言是递归可枚举语言。不过也有语言不是图灵机表达得了的,比如对角语言。

  更加有趣的是,这些图灵机可以一一对应到一个字符串,并被别的图灵机模拟。这个能模拟图灵机的图灵机叫通用图灵机。能够模拟图灵机,则称之为图灵完备。(当然图灵机可以模拟有限状态自动机和下推自动机)

  而现在我们的电脑便是这么一台通用图灵机。当然,这里又涉及到生活中的问题到语言的一个转换。

  至于P和NP,分别是确定型图灵机,和非确定型图灵机在多项式的推演步骤下,所能表达的语言集合。注意一点,这两类图灵机所能表达的语言集合是一样的。就是多项式推演步骤这个条件一加,就未解之谜了。

  可判定性问题,就是刚才说的,许多问题还真不是图灵机能解决的(图灵机不能表达的语言)。刚才说的对角语言就是很重要的一种情况。著名的问题有图灵机停机问题。

  所以这里指出,P与NP其实都是可判定问题,而且许多人一直误解的是,他们其实都是指多项式时间内可判定,只是后者需要动用非确定型图灵机。

  在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟单带图灵机,那么它是图灵完备的。

  简单来说,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。

  可图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾伦·图灵(Alan Turing)。

  虽然图灵机会受到存储能力的物理限制,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。

本文链接:http://cakesbyrita.net/duodaitulingji/752.html