编程语言进化史《禅与计算机程序设计艺术》 / 陈光剑

编程语言概述

计算机编程语言是程序设计的最重要的工具，它是指计算机能够接受和处理的、具有一定语法规则的语言。

编程语言处在不断的发展和变化中，从最初的机器语言发展到如今的2500种以上的高级语言，每种语言都有其特定的用途和不同的发展轨迹。编程语言并不像人类自然语言发展变化一样的缓慢而又持久，其发展是相当快速的，这主要是计算机硬件、互联网和IT业的发展促进了编程语言的发展。

PYPL PopularitY of Programming Language 排行榜：

The PYPL PopularitY of Programming Language Index is created by analyzing how often language tutorials are searched on Google. https://pypl.github.io/PYPL.html

TIOBE编程语言排行榜：

https://www.tiobe.com/tiobe-index/

编程语言图谱：

编程语言的三个发展阶段

从计算机诞生至今，计算机编程语言的发展总体分三个阶段:

第一代机器语言 (相当于人类的原始阶段)

第二代汇编语言 (相当于人类的手工业阶段)

第三代高级语言 (相当于人类的工业阶段)

第一代机器语言 (machine language)

简介

机器语言是微处理器理解和使用的，用于控制它的操作二进制代码。

8086到Pentium的机器语言指令长度可以从1字节到13字节。

尽管机器语言好像是很复杂的，然而它是有规律的。

存在着多至100000种机器语言的指令。这意味着不能把这些种类全部列出来。

下面是一些常用的表达式:

000000000000 代表地址为 0 的存储器

000000000001 代表地址为 1 的存储器

000000010000 代表地址为 16 的存储器

0000,0000,000000010000 代表 LOAD A, 16

0000,0001,000000000001 代表 LOAD B, 1

0000 代表加载（LOAD）

0001 代表存储（STORE）

优缺点

优点:直接执行，速度快，资源占用少

缺点:可读性、可移植性差，编程繁杂

小结

机器语言由数字组成所有指令。当让你使用数字编程,写几百个数字、甚至几千个数字,每天面对的是纯数字,我大胆预测:”程序员群体100%会有精神问题”。

第二代汇编语言（面向机器的程序设计语言）

简介

这是一种面向机器的低级语言，通常是为特定的计算机或系列计算机专门设计的（机器强相关性）。

因为是机器指令的符号化表示，故不同的机器就有不同的汇编语言。使用汇编语言能面向机器并较好地发挥机器的特性，得到质量较高的程序。

汇编语言保持了机器语言的优点，具有直接和简捷的特点，可有效地访问、控制计算机的各种硬件设备，如磁盘、存储器、CPU、I/O端口等，且占用内存少，执行速度快，是高速度和高效率的程序设计语言。

编写和调试的复杂性：由于是直接控制硬件，且简单的任务也需要很多汇编语言语句，因此在进行程序设计时必须面面俱到，需要考虑到一切可能的问题，合理调配和使用各种软、硬件资源。这样，就不可避免地加重了程序员的负担。与此相同，在程序调试时，一旦程序的运行出了问题，就很难发现。

优缺点

优点

因为用汇编语言设计的程序最终被转换成机器指令，故能够保持机器语言的一致性，直接、简捷，并能像机器指令一样访问、控制计算机的各种硬件设备，如磁盘、存储器、CPU、I/O端口等。使用汇编语言，可以访问所有能够被访问的软、硬件资源。
目标代码简短，占用内存少，执行速度快，是高效的程序设计语言，经常与高级语言配合使用，以改善程序的执行速度和效率，弥补高级语言在硬件控制方面的不足，应用十分广泛。

缺点

汇编语言是面向机器的，处于整个计算机语言层次结构的底层，故被视为一种低级语言，通常是为特定的计算机或系列计算机专门设计的。不同的处理器有不同的汇编语言语法和编译器，编译的程序无法在不同的处理器上执行，缺乏可移植性；
难于从汇编语言代码上理解程序设计意图，可维护性差，即使是完成简单的工作也需要大量的汇编语言代码，很容易产生bug，难于调试；
使用汇编语言必须对某种处理器非常了解，而且只能针对特定的体系结构和处理器进行优化，开发效率很低，周期长且单调。

常用的命令

这部分指令用于执行算术和逻辑运算，包括加法指令ADD/ADC、减法指令SUB/SBB、加一指令INC、减一指令DEC、比较操作指令CMP、乘法指令MUL/IMUL、除法指令DIV/IDIV、符号扩展指令CBW/CWDE/CDQE、十进制调整指令DAA/DAS/AAA/AAS、逻辑运算指令NOT/AND/OR/XOR/TEST等。

小结

汇编语言虽然能编写高效率的程序,但是学习和使用都不是易事,并且很难调试。另一个复杂的问题，汇编语言以及早期的计算机语言( Basic、Fortran等 ) 没有考虑结构化设计原则,而是使用goto语句来作为程序流程控制的主要方法。这样做的后果是:一大堆混乱的调转语句使得程序几乎不可能被读懂。对于那个时代的程序员，能读懂上个月自己写的代码都成为一种挑战。

汇编语言仍然应用于工业电子编程领域、软件的加密解密、计算机病毒分析等。

第三代高级语言（High-level programming language ）

高级语言介绍

计算机语言具有高级语言和低级语言之分。而高级语言又主要是相对于汇编语言而言的，它是较接近自然语言和数学公式的编程，基本脱离了机器的硬件系统，用人们更易理解的方式编写程序。编写的程序称之为源程序。

高级语言并不是特指的某一种具体的语言，而是包括很多编程语言，如流行的java，c，c++，C#，pascal，python，lisp，prolog，FoxPro，易语言，中文版的C语言习语言等等，这些语言的语法、命令格式都不相同。

类C语言起源、历史

C语言、C语言的起源以及类似C语言的编程语言的历史简直不要太漫长，我简单总结列表如下：

CPL（Combined Programming Language） - 1963

CPL是1963年剑桥大学发明的

BCPL（Base Combined Programming Language） - 1967

剑桥的Matin Richards 对CPL做了简化，推出了BCPL

B（B Programming Language） - 1969

贝尔实验室的Ken Thompson（肯·汤普森）对BCPL又做了改进，设计出了简单的且接近硬件的B语言，并用B语言写了第一个UNIX OS

C（C Programming Language） - 1972

贝尔实验室的另外一个人Dennis MacAlistair Ritchie（D.M.Ritchie - DM里奇）在B的基础上设计出了C语言。C 保持了B的优点（精炼、接近硬件），又克服了他的缺点（过于简单，数据无类型）

C++（C plus plus Programming Language） - 1983

还是贝尔实验室的人，Bjarne Stroustrup（本贾尼·斯特劳斯特卢普）在C语言的基础上推出了C++，它扩充和完善了C语言，特别是在面向对象编程方面。一定程度上克服了C语言编写大型程序时的不足。

Java（Java Programming Language） - 1995

Sun公司的Patrick Naughton的工作小组研发了Java语言，主要成员是James Gosling（詹姆斯·高斯林）

C#（C Sharp Programming Language） - 2000

Microsoft公司的Anders Hejlsberg（安德斯·海尔斯伯格）发明了C#，他也是Delphi语言之父。

高级语言带来好处

高级语言接近算法语言，易学、易掌握，一般工程技术人员只要几周时间的培训就可以胜任程序员的工作；
高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；
高级语言远离机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好，重用率高；
由于把繁杂琐碎的事务交给了编译程序去做，所以自动化程度高，开发周期短，且程序员得到解脱，可以集中时间和精力去从事对于他们来说更为重要的创造性劳动，以提高程序的质量。

总结

高级语言的出现,尤其是面向对象语言的出现,相当于人类的工业社会,高级语言极其易用，编程门槛和难度大大降低，大量的人员进入软件开发行业，为软件爆发性的增长提供了充足的人力资源。目前以及可预见的将来,计算机语言仍然处于“第三代高级语言”阶段。

编程语言编年史

编程语言的历史早于真正意义的计算机的出现。19世纪就有可编程的织布机和钢琴弹奏装置出现，它们都是领域特定语言(DSL)的样例。

1951 – Regional Assembly Language

1952 – Autocode

1954 – IPL (LISP语言的祖先)

1955 – FLOW-MATIC (COBOL语言的祖先)

1957 – FORTRAN (第一个编译型语言)1957 – COMTRAN (COBOL语言的祖先)

1958 – LISP

1958 – ALGOL 58

1959 – FACT (COBOL语言的祖先)

1959 – COBOL1959 – RPG1962 – APL

1962 – Simula

1962 – SNOBOL

1963 – CPL (C语言的祖先)

1964 – BASIC1964 – PL/I

1966 – JOSS

1967 – BCPL (C语言的祖先)

1968 – Logo

1969 – B (C语言的祖先)

1970 – Pascal

1970 – Forth

1972 – C1972 – Smalltalk

1972 – Prolog

1973 – ML

1975 – Scheme

1978 – SQL

1980 – C++ (既有类的C语言，更名于1983年7月)

1983 – Ada

1984 – Common Lisp

1984 – MATLAB

1985 – Eiffel

1986 – Objective-C

1986 – Erlang

1987 – Perl1988 – Tcl

1988 – Mathematica

1989 – FL

1990 – Haskell

1991 – Python

1991 – Visual Basic

1993 – Ruby

1993 – Lua

1994 – CLOS (ANSI Common Lisp的一部分)

1995 – Java

1995 – Delphi (Object Pascal)

1995 – Java

1995 – PHP

1996 – WebDNA

1997 – Rebol

1999 – D

2000 – Action

2001 – C#

2001 – Visual Basic .NET

2002 – F#

2003 – Groovy

2003 – Scala

2007 – Clojure

2009 – Go

2011 – Dart

程序设计语言类型

命令式语言。这种语言的语义基础是模拟“数据存储/数据操作”的图灵机可计算模型，十分符合现代计算机体系结构的自然实现方式。其中产生操作的主要途径是依赖语句或命令产生的副作用。现代流行的大多数语言都是这一类型，比如 Fortran、Pascal、Cobol、C、C++、Basic、Ada、Java、C# 等，各种脚本语言也被看作是此种类型。
函数式语言。这种语言的语义基础是基于数学函数概念的值映射的λ算子可计算模型。这种语言非常适合于进行人工智能等工作的计算。典型的函数式语言如 Lisp、Haskell、ML、Scheme 、F#等。
逻辑式语言。这种语言的语义基础是基于一组已知规则的形式逻辑系统。这种语言主要用在专家系统的实现中。最著名的逻辑式语言是 Prolog。
面向对象语言。现代语言中的大多数都提供面向对象的支持，但有些语言是直接建立在面向对象基本模型上的，语言的语法形式的语义就是基本对象操作。主要的纯面向对象语言是 Smalltalk。

虽然各种语言属于不同的类型，但它们各自都不同程度地对其他类型的运算模式有所支持。

图灵机

1936年，英国数学家阿兰・麦席森・图灵(1912―-1954年)提出了一种抽象的计算模型——图灵机( Turing machine)。图灵机，又称图灵计算机，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。

图灵在1936年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"（《论可计算数及其在判定性问题上的应用》）中提出了图灵机（Turing Machine）的数学模型。文章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。

一台图灵机是一个七元组，{Q，Σ，Γ，δ，q0，qaccept，qreject}，其中 Q，Σ，Γ 都是有限集合，且满足：

1、Q 是状态集合；

2、Σ 是输入字母表，其中不包含特殊的空白符；

3、Γ 是带字母表，其中 Q∈Γ且Σ∈Γ ；

4、 δ：Q×Γ→Q×Γ×{L，R}是转移函数，其中L，R 表示读写头是向左移还是向右移；

5、q0∈Q是起始状态；

6、 qaccept是接受状态。

7、qreject是拒绝状态，且qreject≠qaccept。

图灵机 M = (Q，Σ，Γ，δ，q0，qaccept，qreject) 将以如下方式运作：

开始的时候将输入符号串从左到右依此填在纸带的第号格子上，其他格子保持空白（即填以空白符）。M 的读写头指向第 0 号格子， M 处于状态 q0。

机器开始运行后，按照转移函数 δ 所描述的规则进行计算。

例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x，设 δ（q，x）= （q'，x'，L），则机器进入新状态 q'，将读写头所指的格子中的符号改为 x'，然后将读写头向左移动一个格子。

若在某一时刻，读写头所指的是第 0 号格子，但根据转移函数它下一步将继续向左移，这时它停在原地不动。换句话说，读写头始终不移出纸带的左边界。

若在某个时刻 M 根据转移函数进入了状态 qaccept，则它立刻停机并接受输入的字符串；

若在某个时刻 M 根据转移函数进入了状态 qreject，则它立刻停机并拒绝输入的字符串。

注意，转移函数 δ 是一个部分函数，换句话说对于某些 q，x， δ（q，x）可能没有定义，如果在运行中遇到下一个操作没有定义的情况，机器将立刻停机。

图灵提出图灵机的模型并不是为了同时给出计算机的设计，它的意义有如下几点:

(1) 它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；

(2) 图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；

(3) 图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

通用图灵机向人们展示这样一个过程:程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。更重要的是，隐约可以看到现代计算机主要构成，尤其是冯・诺依曼理论的主要构成。

图灵完备与停机问题

图灵完备

FORTRAN语言是图灵完备的，尽管它不支持递归。

世界上所有的问题在图灵机都有办法解决吗？或者说，世界上的所有问题在图灵机都有算法吗？

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

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.

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

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.

停机问题

停机问题（Halting Problem）, 是逻辑学的焦点，也是第三次数学危机的解决方案。

问题描述: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的 S 也是可停机的。

通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行？

该问题等价于如下的判定问题：

是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。

PS: 相似的悖论理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村里所有人，当且仅当这个人不自己理发，理发师就给这个人理发。如果这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发么？停机测试悖论：计算机里有个测试程序，这个测试程序的原则是，对于计算机里所有程序，当且仅当这个程序不递归调用自己（输出停机），测试程序就调用它（对应不停机）。如果这个程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？

PS：悖论就是逻辑上的自相矛盾。

人类历史上的三次数学危机

数学三大危机，涉及无理数、微积分和集合等数学概念。

危机一，希巴斯（Hippasus，米太旁登地方人，公元前470年左右）发现了一个腰为1的等腰直角三角形的斜边（即2的2次方根）永远无法用最简整数比（不可公度比）来表示，从而发现了第一个无理数，推翻了毕达哥拉斯的著名理论。相传当时毕达哥拉斯派的人正在海上，但就因为这一发现而把希巴斯抛入大海。

危机二，微积分的合理性遭到严重质疑，险些要把整个微积分理论推翻。

危机三，罗素悖论：S由一切不是自身元素的集合所组成，那S属于S吗？用通俗一点的话来说，小明有一天说：“我正在撒谎！”问小明到底撒谎还是说实话。罗素悖论的可怕在于，它不像最大序数悖论或最大基数悖论那样涉及集合高深知识，它很简单，却可以轻松摧毁集合理论。

下面我们就来详细看看人类思想史上最为深刻的反思历程。

第一次数学危机

人类最早认识的是自然数。从引进零及负数就经历过斗争：要么引进这些数，要么大量的数的减法就行不通；同样，引进分数使乘法有了逆运算——除法，否则许多实际问题也不能解决。但是接着又出现了这样的问题，是否所有的量都能用有理数来表示? 于是发现无理数就导致了第一次数学危机，而危机的解决也就促使逻辑的发展和几何学的体系化。

方程的解导致了虚数的出现，虚数从一开始就被认为是“不实的”。可是这种不实的数却能解决实数所不能解决的问题，从而为自己争得存在的权利。几何学的发展从欧几里得几何的一统天下发展到各种非欧几何学也是如此。

在十九世纪发现了许多用传统方法不能解决的问题，如五次及五次以上代数方程不能通过加、减、乘、除、乘方、开方求出根来；古希腊几何三大问题，即三等分任意角、倍立方体、化圆为方不能通过圆规、直尺作图来解决等等。

这些否定的结果表明了传统方法的局限性，也反映了人类认识的深入。这种发现给这些学科带来极大的冲击，几乎完全改变了它们的方向。比如说，代数学从此以后向抽象代数学方面发展，而求解方程的根变成了分析及计算数学的课题。

第二次数学危机

这次危机的萌芽出现在大约公元前450年，芝诺注意到由于对无限性的理解问题而产生的矛盾，提出了关于时空的有限与无限的四个悖论：

“两分法”：向着一个目的地运动的物体，首先必须经过路程的中点，然而要经过这点，又必须先经过路程的1/4点……，如此类推以至无穷。——结论是：无穷是不可穷尽的过程，运动是不可能的。

“阿基里斯追不上乌龟”：阿基里斯总是首先必须到达乌龟的出发点，因而乌龟必定总是跑在前头。这个论点同两分法悖论一样，所不同的是不必把所需通过的路程一再平分。

“飞矢不动”：意思是箭在运动过程中的任一瞬时间必在一确定位置上，因而是静止的，所以箭就不能处于运动状态。

“操场或游行队伍”：A、B两件物体以等速向相反方向运动。从静止的c来看，比如说A、B都在1小时内移动了2公里，可是从A看来，则B在1小时内就移动了4公里。运动是矛盾的，所以运动是不可能的。

芝诺揭示的矛盾是深刻而复杂的。前两个悖论诘难了关于时间和空间无限可分，因而运动是连续的观点，后两个悖论诘难了时间和空间不能无限可分，因而运动是间断的观点。芝诺悖论的提出可能有更深刻的背景，不一定是专门针对数学的，但是它们在数学王国中却掀起了一场轩然大被。它们说明了希腊人已经看到“无穷小”与“很小很小”的矛盾，但他们无法解决这些矛盾。其后果是，希腊几何证明中从此就排除了无穷小。

罗尔曾说：“微积分是巧妙的谬论的汇集。”在那个勇于创造时代的初期，科学中逻辑上存在这样那样的问题，并不是个别现象。18世纪的数学思想的确是不严密的、直观的，强调形式的计算而不管基础的可靠。其中特别是：没有清楚的无穷小概念，从而导数、微分、积分等概念不清楚；无穷大概念不清楚；发散级数求和的任意性等等；符号的不严格使用；不考虑连续性就进行微分，不考虑导数及积分的存在性以及函数可否展成幂级数等等。

直到19世纪20年代，一些数学家才比较关注于微积分的严格基础。从波尔查诺、阿贝尔、柯西、狄里赫利等人的工作开始，到威尔斯特拉斯、狄德金和康托的工作结束，中间经历了半个多世纪，基本上解决了矛盾，为数学分析奠定了一个严格的基础。

波尔查诺给出了连续性的正确定义；阿贝尔指出要严格限制滥用级数展开及求和；

柯西在1821年的《代数分析教程》中从定义变量出发，认识到函数不一定要有解析表达式。柯西抓住极限的概念，指出无穷小量和无穷大量都不是固定的量而是变量，无穷小量是以零为极限的变量；并且定义了导数和积分；

狄里赫利给出了函数的现代定义。

威尔斯特拉斯消除了其中不确切的地方，给出现在通用的极限的定义，连续的定义，并把导数、积分严格地建立在极限的基础上。

19世纪70年代初，威尔斯特拉斯、狄德金、康托等人独立地建立了实数理论，而且在实数理论的基础上，建立起极限论的基本定理，从而使数学分析建立在实数理论的严格基础之上。

第二次数学危机，最终完善了微积分的定义和与实数相关的理论系统，同时基本解决了第一次数学危机的关于无穷计算的连续性的问题，并且将微积分的应用推向了所有与数学相关的学科中。

第三次数学危机

在第三次数学危机中，这种情况也多次出现，尤其是包含整数算术在内的形式系统的不完全性、许多问题的不可判定性都大大提高了人们的认识，也促进了数理逻辑的大发展。

数学史上的第三次危机，是由1897年的突然冲击而出现的，到现在，从整体来看，还没有解决到令人满意的程度。这次危机是由于在康托尔的一般集合理论的边缘发现悖论造成的。由于集合概念已经渗透到众多的数学分支，并且实际上集合论成了数学的基础，因此集合论中悖论的发现自然地引起了对数学的整个基本结构的有效性的怀疑。

罗素悖论：

如果存在一个集合A={X| X∉ A }，那么X∈A是否成立？如果它成立，那么X∈A，不满足A的特征性质。如果它不成立，A就满足了特征性质。

承认无穷集合，承认无穷基数，就好像一切灾难都出来了，这就是第三次数学危机的实质。尽管悖论可以消除，矛盾可以解决，然而数学的确定性却在一步一步地丧失。

公理化集合论

(1)外延公理（容积公理）：一个集合完全由它的元素所决定。如果两个集合含有的元素相同，则它们是相等的。

(2)分离公理模式：“对任意集合X和任意对X的元素有定义的逻辑谓词P(z)，存在集合Y，使z∈Y 当且仅当z∈X而且P(z)为真”

也就是说：若X是一个集合，那么可以断定，Y={x∈X|P（x）}也是一个集合。

(3)配对公理：对任意a和b是对象，则存在一个集合{a，b}，其仅有的元素是a和b。也就是说：我们可以用一个集合Z={X,Y}来表示任给的两个集合X,Y，称之为X与Y的无序对。

(4)并集公理：任给一族M，存在UM（称为M的并）它的元素恰好为M中所含元素的元素。也就是说：我们可以把族M的元素的元素汇集到一起，组成一个新集合。

注：为了方便描述，定义族表示其元素全为集合的集合。

(5)幂集公理(子集之集公理)：对任意集合X，存在集合P（X），它的元素恰好就是X的一切子集。也就是说：存在以已知集合的一切子集为元素的集合。

(6)无穷公理：存在归纳集。（存在一个集合，空集是其元素，且对其任意元素x，x+=x∪{x}也是其元素）

也就是说，存在一集合x，它有无穷多元素。

(7)替换公理模式（置换公理）：也就是说，对于任意的函数F（x），对于任意的集合T，当x属于T时，F（x）都有定义（ZF中唯一的对象是集合，所以F（x）必然是集合）成立的前提下，就一定存在一集合S，使得对于所有的x属于T，在集合S中都有一元素y，使y=F（x）。也就是说，由F（x）所定义的函数的定义域在T中的时候，那么它的值域可限定在S中。

(8)正则公理：也叫基础公理。所有集都是良基集。说明一个集合的元素都具有最小性质，例如，不允许出现x属于x的情况。

准确的定义：“对任意非空集合x，x至少有一元素y使x∩y为空集。”

以上8条公理组成了ZF公理系统，再加上选择公理，则组成了ZFC公理系统

(9)选择公理：也叫策梅洛公理，对于任意两两不交的集合族，存在集合C，使对所给的族中的每个集合X，集合X与C的交恰好只含一个元素。

现代公理集合论的大堆公理，讲真，难说孰真孰假（人类从已知的正确经验中，反过来自己定义的公理规则）。

可是又不能把它们都消除掉，它们跟整个数学是血肉相连的。所以，第三次危机表面上解决了，实质上更深刻地以其它形式延续着。

哥德尔不完全性定理

真与可证是两个概念。可证的一定是真的，但真的不一定可证。

问题：能否给出一个算法，判定一个给定的命题是否为真？对任何输入都能在有限时间内停机吗?

哥德尔证明了任何一个形式系统，只要包括了简单的初等数论描述，而且是自洽的，它必定包含某些系统内所允许的方法既不能证明真也不能证伪的命题。

“无矛盾”和“完备”是不能同时满足的！不存在解决停机问题的方法。

第一定理

任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

第二定理

如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。

什么是图灵完备？

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

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

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.

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

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

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

All general-purpose languages in wide use：

Procedural programming languages such as C, Pascal.
Object-oriented languages such as CIL, Java, Smalltalk.
Multi-paradigm languages such as Ada, C++, Common Lisp, Object Pascal.

Most languages using less common paradigms

Functional languages such as Lisp and Haskell.
Logic programming languages such as Prolog.
Declarative languages such as XSLT.
Esoteric programming languages, such as Brainfuck

除此之外的语言呢？其实，绝大部分的编程语言都是图灵完备的，他们都拥有相同的计算能力。但是，有一些我们比较常见的却不是：regular languages, XML, HTML, JSON, YAML（明显不具备计算能力，它们只是markup language)等等。

P=NP？

递归

Y组合子

函数式编程

参考资料

https://blog.csdn.net/qq_42932382/article/details/82912762

https://blog.csdn.net/lao454490095/article/details/46917355

《禅与计算机程序设计艺术》 / 陈光剑目录

第一性原理

什么是禅？

计算简史：什么是计算机？

什么是程序设计？

什么是艺术？

风味人间与计算机程序设计艺术

宇宙之起源

物质之形成

半导体材料

纳米光刻

二极管、三极管

太极阴阳与二进制

布尔代数与数字逻辑系统

模拟电子电路系统

信号与处理

信息论

图灵机模型

冯诺依曼模型

计算机演化史

什么是编程？