要解释图灵完备，不得不首先简单介绍一下图灵本人。图灵（1912-1954）全名艾伦·麦席森·图灵（Alan Mathison Turing），英国数学家，可以称得上是一个天才。图灵在二战期间参与破解德军密码系统，极大地影响了战争的走向，他在数学和计算机方面的成果奠定了现代计算机技术的基础。美国计算机协会在1966年以图灵的名字设立图灵奖，奖励在计算机科学上有突出贡献的人，被认为是计算机界的最高奖项。
图灵-网络图片
在数学领域，计算一直是一个重要的研究课题。在20世纪初，数学家们开始思考如何将计算的过程转化为一些有限的、机械重复的步骤。对于任何一个问题，如果可以找到这样的方法，那么就可以通过机器来机械的重复这些步骤得出问题的答案，这样的机器也就是我们熟悉的计算机。
图灵在1936年读硕士时，发表了一篇论文《计算机器和智能》，对一个问题的可计算性进行了精确的定义，并把计算归结为简单基本的操作，由此也引出了“图灵机”的模型。图灵机模型的设想便是通过机械操作来模拟并完成计算。
图灵机的设想是：有一个无限长的纸条，被分成一个一个的小格，小格中记录了不同的符号，有一个机器可以读写或擦除这个小格，并可以从一个小格移动到另一个小格进行操作，而所谓的计算无非就是读写或擦除小格子或移动到另一个小格子这两种操作的机械重复。图灵机中包含了一些列操作规则，根据读到的不同符号，图灵机会根据这些规则进入不同的操作状态，同时图灵机中也有一个位置可以记录目前机器所处的状态。
图灵机-网络图片
设想要计算‘1+2=’。那么图灵机便可以开始依次读取每一个小格子里的1、+、2、=，图灵机则可以理解读取到的1和2，也会按照包含的规则列表中找到+和=所代表的操作，然后移动到新的位置写出结果。当然这样理解图灵机模型十分粗糙，但作为外行可以这样简化理解。进一步，如果一个问题可以在有限的步骤内按照这个过程表达出来，或者说一个问题有具体的算法，那么这个问题便可以用图灵机来计算。也就是说，只要一个问题可以计算，就可以用图灵机来解决。
同时，图灵还认为可以实现机器按照某种方式自动进行学习，类似婴儿的学习成长过程。所以，图灵还提出了著名的图灵测试。也就是如果人类没办法分辨与他进行交互的是人还是机器，则这个机器便拥有了“智能”。
回到图灵完备，如果一个编程语言或一个系统有等同于图灵机的能力，即可以用于计算那些有具体算法的问题，则可以称这个编程语言或系统是图灵完备的。目前流行的的各种编程语言，如Python、C++等都是图灵完备的，这些编程语言都兼顾了效率和可读性，而其实一个编程语言可以设计地十分简略，如‘BrainFuck’语言，仅仅用了8个符号表示8种状态便实现了图灵完备性。
网友评论