编程语言的本质：1.编程语言的计算能力

编程语言的本质到底是什么？”——昨天晚上给自己提了这么个问题

如果要我来解释，自然语言的本质到底要从哪几方面入手，我可能能说出这么一些来：拼写学Orthography、音系学Phonology、语音学Phonetics、词法学Morphology、句法Syntax、语义学Semantics、语用学Pragmatics[1]。也许，学英语，学法语，学拉丁文，掌握这么些本质的东西，融会贯通一下，学习起来应该就很快了。（我现在越来越觉得，你跟所谓的牛人之间的差距，可能只是方法论的区别而已。）

但是接触了这么久编程语言，编过PHP，编过C++，编过Java，编过Python，编过Prolog，编过OC，当我问自己这么个问题的时候，脑子竟然一片空白。以前总是沉迷在各种语言的“玩法”上不能自拔，觉得很爽，很拽，别人都不会，很有成就感。但其实那些都是很表皮的东西，翻翻文档就能完成的东西。最近看了些博客，看了些书，深知对语言的追求应该是到那种拿到一门新的语言，半天就能将特性琢磨透的程度。那么怎么琢磨透呢？我觉得，只有了解本质的东西，才能让你有这种认知的速度，基础才是最重要的。

本来这篇文章应该是徐宥前辈的“编程珠玑八卦版”[2]的读后感，但行文之前，隐隐感觉有种拾人牙慧的罪恶感，于是狠狠打开wiki，做起资料收集来。一查起来发现，徐宥前辈的文章就是一扇门，可能写得好的博客都是一扇门吧。这个问题，深挖可以牵扯到计算理论、计算模型等等理论计算机科学的东西，浅挖就是各种编程泛型、数据结构、核心特性等等，而徐宥前辈的文章似乎也自成一个体系，所以我决定将这个问题分开三个方面去阐述：

1. 第一篇以编程语言的计算能力为角度
2. 第二篇以编程语言的本质区别为角度
3. 第三篇以编程语言的历史发展为角度

之后可能会在这个基础上加上其它的一些角度，说不准。

========================================
编程语言的计算能力

给我一门编程语言，我是不是可以解决这个世界上所有问题呢？——这又是一个以前经常在脑海中回荡，但是一直不知道怎么找答案的问题

这个问题真的是很有趣的，也很哲学，提出的原因可能是我这种经常使用Python的，觉得很多都是”import antigravity”[3]的问题而已，也可能只是某个时候，刚码完代码，心情很爽，所以心血来潮有了这么个邪念。

在阅读徐宥前辈的《高级语言怎么来的》系列过程当中，前辈多次提到“FORTRAN语言是图灵完备的，尽管它不支持递归”这么一个观点。到底什么是图灵完备呢？图灵我见过，《模仿游戏》里面的卷福不是么？（其实我是奔着凯拉·奈特莉去的，值得一看。。）我们谈论的，其实是计算机科学领域的图灵。图灵生平做过什么牛事就不说了。我来说说他的“那台”图灵机，这台机器跟我提出的这个问题大有渊源。注意这台图灵机并不是那台Enigma。

A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules.[4]

有人根据这种描述，将字面上理解的图灵机表示了出来

但是请记住，这只是为了给读者一个直观的认识，因为图灵机实际上仍是一个抽象模型。

1. 那条纸带，我们叫它纸带（tape），图灵机将这条纸带假设为左右无限延展
2. 纸带操作头，叫head
3. 图灵机本身存储的状态的地方，叫state register，存的值叫做state
4. 那个表，叫做finite table of instructions

注意这里，整个图灵机的组成里面，除了tape，其他都是有限的，只有tape是无限的，这也说明了它的假想性质。图灵提出的仅仅是假想，但是我们现代的计算机，的确是以图灵机模型为基础的：

我们平时所说的和所使用的计算机，基于图灵提出的确定型图灵机模型。它是最好理解的：给出固定的程式，模型按照程式和输入完全确定性地运行。[5]

我们前面说的纸带图灵机，就是指确定型图灵机。我们要清楚，图灵机并不一定就是计算机，它是虚构的机器，确切来说是一个计算系统，我们的编程语言，cpu的命令集，都可以算是一个图灵机，明白这点很重要。

除此之外，常见的计算机模型还有非确定型图灵机模型：

它（非确定型图灵机）在进行计算的时候，会自动选择最优路径进行计算。通俗地说，它有预测能力。比如说，为了说明某个数是合数，非确定型图灵机会猜测一个数，恰好是其因子，从而证明了它不是质数

与确定型图灵机不同，图灵机只存在于人的想象中，现实上是不可行的（能够预测的计算机。。）但是人们仍然通过研究诸如“如果这个问题在非确定型图灵机上面用这个算法解决会有什么样的效率呢”之类的问题来进行研究

其中他们研究的一个问题就是P vs NP问题，这个问题也是千禧问题中的一个

P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。[6]

如果P=NP，那么很多在非确定型图灵机模型下能够多项式算法进行求解的问题，就能在确定型图灵机模型下使用多项式算法求得（虽然这个算法可能很难找到）；设想中的就能在现实中实现。

另外一个比较出名的就是量子计算机模型，它能够实现所谓无限并行度，这里不作细讲。有兴趣可以去学习量子理论和量子计算（理论计算机科学的一部分）

另外一位大牛，美国数学家Alonzo Church发表过一个观点：Church–Turing thesis（邱奇-图灵假说），认为所有的计算模型计算能力都无法超过确定型图灵机：

Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be “computed” can be computed by some Turing machine.[7]

这个虽然是一个假说，但是现在的计算理论都是基于这个理论搭建起来的，并且被证明非常成功。由这个假说我们知道，图灵机这个模型能够达到所有其他计算模型的计算能力。这种计算能力达到什么程度呢？是不是说，世界上所有的问题在图灵机都有办法解决呢？或者说，世界上的所有问题在图灵机都有算法吗？

答案是否定的。其中一个著名的不能解决的问题就是停机问题：

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.[8]

而图灵给出了证明，这个问题是无法解决的：

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.

现实中，我们去衡量自己的一个计算系统是不是可以归类为图灵机（前面已经说明图灵机并不一定是一台机器），要看它是不是“图灵完备”的。

什么是图灵完备呢？

In computability theory, a system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.[9]

如果你的这个系统，能够用来模拟出单纸带的图灵机，那么它就是图灵完备的，也就是说，它就和图灵机有一样的计算能力。前面说了，这个系统可以指很多东西，可以指一个软件，可以是一个编程语言，等等。

举几个例子，什么是图灵完备的编程语言？C是不是？你能用C语言模拟出单纸带的图灵机吗？明显可以（具体的实现可以在网上找）。

那么Python呢？Java呢？都可以。其实，有人早就做出一个总结，告诉你，以下这些语言就是图灵完备的：

All general-purpose languages in wide use：
1. Procedural programming languages such as C, Pascal.
2. Object-oriented languages such as CIL, Java, Smalltalk.
3. Multi-paradigm languages such as Ada, C++, Common Lisp, Object Pascal.

Most languages using less common paradigms
1. Functional languages such as Lisp and Haskell.
2. Logic programming languages such as Prolog.
3. Declarative languages such as XSLT.
4. Esoteric programming languages, such as Brainfuck

除此之外的语言呢？其实，绝大部分的编程语言都是图灵完备的，他们都拥有相同的计算能力。但是，有一些我们比较常见的却不是：

1. regular languages
2. XML, HTML, JSON, YAML（明显不具备计算能力，它们只是markup language
3. 等等

那么，有没有什么科学点的方法来验证某种编程语言是不是图灵完备的呢？简单的方法的话，可以参考一种叫做brainfuck的语言，这是一种最简单的图灵完全的语言，而且被证明了，如果一门编程语言能够完全brainfuck的所有功能，那么他一定是图灵完全的。（知乎@余天升）

到现在，我们可以知道，其实我们用的绝大多数语言，都是图灵完备的。这似乎就解答了我开始提出的问题：

问：“给我一门编程语言，是不是可以解决世界上所有问题呢？”转换为“图灵机对于这个世界上的问题是不是都有算法？”（本来提出这个问题，我也没想用标记语言去解决所有问题）
答：“不是”

但是通过上篇的分析，我们至少能够知道，绝大多数的语言，计算能力都是相同的。

但是细心想想这句话，其实和我们的“直觉”会有冲突。我们的直觉告诉我们，我们用Python去写一个网页后端，和用Prolog去写一个网页后端，肯定是不同的。这就不是计算能力（可行性）的问题了。而是关系到了计算的效率、代码的可理解性、可维护性等等的一些问题。图灵完备只是通用编程的最低要求，只是证明了“在内存无限、时间无限的情况下，最终会计算出来“这样的一种可行性。

那么，就很自然地引出一个问题，在计算能力相等的情况下，什么才是编程语言之间的区别呢？这是下一篇所要解决的问题了！

参考：
1. Cognitive_science,Knowledge and processing of language
2. 编程珠玑番外篇-D. 高级语言怎么来的-1,徐宥
3. PYTHON,xkcd
4. Turing_machine,wikipedia
5. 理论计算机初步：算法和计算模型,zhiqiang张志强
6. 理论计算机初步：P vs NP - 问题概述,zhiqiang张志强
7. 邱奇-图灵假说,wikipedia
8. 停机问题,wikipedia
9. 图灵完备,wikipedia

注：
1. 玩minecraft的同学可以看看这个视频， https://www.youtube/watch?v=1X21HQphy6I。 在minecraft里面用红石（redstone）和活塞（piston）构造的系统也是图灵完备的哦（这也就解释了为什么那么多人在minecraft里面编程了吧）
2. 维基百科上面有一篇文章是介绍图灵完备的，但是链接失效了，求备份！
3. 对于疏漏难免，如果有任何改进的建议，十分欢迎提出！