图灵机

图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

图灵测试

图灵测试（The Turing test）由艾伦·麦席森·图灵发明，指测试者与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。
进行多次测试后，如果有超过30%的测试者不能确定出被测试者是人还是机器，那么这台机器就通过了测试，并被认为具有人类智能。图灵测试一词来源于计算机科学和密码学的先驱阿兰·麦席森·图灵写于1950年的一篇论文《计算机器与智能》，其中30%是图灵对2000年时的机器思考能力的一个预测，目前我们已远远落后于这个预测。

图灵指出：“如果机器在某些现实的条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。”
从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。例如，提问与回答呈现出下列状况：
问：你会下国际象棋吗？
答：是的。
问：你会下国际象棋吗？
答：是的。
问：请再次回答，你会下国际象棋吗？
答：是的。
你多半会想到，面前的这位是一部笨机器。如果提问与回答呈现出另一种状态：
问： 你会下国际象棋吗？
答：是的。
问：你会下国际象棋吗？
答：是的，我不是已经说过了吗？
问：请再次回答，你会下国际象棋吗？
答：你烦不烦，干嘛老提同样的问题。
那么，你面前的这位，大概是人而不是机器。上述两种对话的区别在于，第一种可明显地感到回答者是从知识库里提取简单的答案，第二种则具有分析综合的能力，回答者知道观察者在反复提出同样的问题。“图灵测试”没有规定问题的范围和提问的标准，如果想要制造出能通过试验的机器，以我们的技术水平，必须在电脑中储存人类所有可以想到的问题，储存对这些问题的所有合乎常理的回答，并且还需要理智地作出选择。[2]
社会评价编辑
现代计算机之父冯·诺依曼生前曾多次谦虚地说，如果不考虑查尔斯·巴贝奇等人早先提出的有关思想，现代计算机的概念当属于艾伦·图灵。冯·诺依曼能把“计算机之父”的桂冠戴在比自己小10岁的图灵头上，足见图灵对计算机科学影响之巨大。

停机问题

停机问题是目前逻辑学的焦点，也是第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是可停机的。

停机问题（英语：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。
通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程序判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。

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

数学危机(共三次数学危机)

数学危机是数学在发展中种种矛盾， 数学中有大大小小的许多矛盾，比如正与负、加法与减法、微分与积分、有理数与无理数、实数与虚数等等。但是整个数学发展过程中还有许多深刻的矛盾，例如有穷与无穷，连续与离散，乃至存在与构造，逻辑与直观，具体对象与抽象对象，概念与计算等等。在整个数学发展的历史上，贯穿着矛盾的斗争与解决。而在矛盾激化到涉及整个数学的基础时，就产生数学危机。往往危机的解决，给数学带来新的内容，新的进展，甚至引起革命性的变革。

λ演算

λ演算，λ(Lambda（大写Λ，小写λ）读音：lan b（m） da（兰亩达）[‘læ;mdə])演算是一套用于研究函数定义、函数应用和递归的形式系统。它由 Alonzo Church 和 Stephen Cole Kleene 在 20 世纪三十年代引入，Church 运用 lambda 演算在 1936 年给出 判定性问题 (Entscheidungsproblem) 的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个 lambda 演算表达式是否等价的命题无法通过一个通用的算法来解决，这是不可判定性能够证明的头一个问题，甚至还在停机问题之先。

λ 演算可以被称为最小的通用程序设计语言。它包括一条变换规则 (变量替换) 和一条函数定义方式，λ演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的。尽管如此，λ演算强调的是变换规则的运用，而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。它一个数理逻辑形式系统，使用变量代入和置换来研究基于函数定义和应用的计算。希腊字母λ被用来在λ演算模型中表示将一个变量绑定在一个函数中。

函数式编程

函数式编程是种编程方式，它将电脑运算视为函数的计算。函数编程语言最重要的基础是λ演算（lambda calculus），而且λ演算的函数可以接受函数当作输入（参数）和输出（返回值）。
和指令式编程相比，函数式编程强调函数的计算比指令的执行重要。
和过程化编程相比，函数式编程里函数的计算可随时调用。

简单说，”函数式编程”是一种”编程范式”（programming paradigm），也就是如何编写程序的方法论。
它属于”结构化编程”的一种，主要思想是把运算过程尽量写成一系列嵌套的函数调用。

命令式程序设计语言

本词条缺少信息栏、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来编辑吧！
命令式程序设计语言是基于动作的语言，以冯诺依曼计算机体系结构为背景。机器语言及汇编语言是最早的命令式语言。在这种语言中，计算机被看做是动作的序列，程序就是用语言提供的操作命令书写的一个操作序列。用命令式程序设计语言编写程序，就是描述解题过程中每一步的过程，程序的运行过程就是问题的求解过程，因此也称为过程式语言。Fortran、ALGOL、COBOL、C、Ada、Pascal等都是命令式程序设计语言。

声明式编程和命令式编程

我们可以像下面这样定义它们之间的不同：

  • 命令式编程：命令“机器”如何去做事情(how)，这样不管你想要的是什么(what)，它都会按照你的命令实现。
  • 声明式编程：告诉“机器”你想要的是什么(what)，让机器想出如何去做(how)。
    声明式编程和命令式编程的代码例子
    举个简单的例子，假设我们想让一个数组里的数值翻倍。
    我们用命令式编程风格实现，像下面这样：
    1
    2
    3
    4
    5
    6
    7
    var numbers = [1,2,3,4,5]
    var doubled = []
    for(var i = 0; i < numbers.length; i++) {
      var newNumber = numbers[i] * 2
      doubled.push (newNumber)
    }
    console.log (doubled) //=> [2,4,6,8,10]

我们直接遍历整个数组，取出每个元素，乘以二，然后把翻倍后的值放入新数组，每次都要操作这个双倍数组，直到计算完所有元素。
而使用声明式编程方法，我们可以用 Array.map 函数，像下面这样：

1
2
3
4
5
var numbers = [1,2,3,4,5]
var doubled = numbers.map (function (n) {
  return n * 2
})
console.log (doubled) //=> [2,4,6,8,10]

过程化程序设计语言

过程化程序设计语言：即第三代程序设计语言，指需要由编写程序的人员一步一步地安排好程序的执行过程的程序设计语言。SQL是高级的非过程化编程语言，允许用户在高层数据结构上工作。它不要求用户指定对数据的存放方法，也不需要用户了解具体的数据存放方式，所以具有完全不同底层结构的不同数据库系统可以使用相同的SQL语言作为数据输入与管理的接口。它以记录集合作为操作对象，所有SQL语句接受集合作为输入，返回集合作为输出的语句

  • 第一代机器语言
  • 第二代汇编语言
  • 第三代高级语言
  • 第四代非过程化语言

结构化编程

结构化程式设计（英语：Structured programming），一种编程典范。它采用子程序、程式码区块（英语：block structures）、for循环以及while循环等结构，来取代传统的 goto。希望借此来改善计算机程序的明晰性、品质以及开发时间，并且避免写出面条式代码。

泛型编程

泛型编程（Generic Programming）最初提出时的动机很简单直接：发明一种语言机制，能够帮助实现一个通用的标准容器库。所谓通用的标准容器库，就是要能够做到，比如用一个List类存放所有可能类型的对象这样的事；泛型编程让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。

关于泛型的理解可以总结下面的一句话，它是把数据类型作为一种参数传递进来。