算法 | 王成飞博客

在数学和计算机科学中，算法是解决一类问题的明确说明。算法可以执行计算、数据处理、自动推理和其他任务。

作为一种有效的方法，一种算法可以在有限的空间和时间内，用一种定义良好的形式语言表示，用于计算一个函数从初始状态和初始输入（可能为空）开始，指令描述了一种计算，当执行时，通过有限个定义进行计算，最终产生“输出”，并最终在结束状态终止。从一个状态到下一个状态的转换不一定是确定性的；一些被称为随机化算法的算法结合了随机输入。

算法的概念已经存在了几个世纪。希腊数学家使用埃拉托斯滕斯筛中的算法来寻找素数，使用欧几里得算法来寻找两个数的最大公约数。

单词algorithm本身源自9世纪的数学家。部分形式化成为现代算法的概念始于试图解决由大卫希尔伯特在1928年提出的Entscheidungsproblem（决策问题）。后来的形式化是试图定义“有效的可计算性”或“有效的方法”。这些形式化包括1930、1934和1935年的G_del–Herbrand–Kleene递归函数、1936年的Alonzo Church的lambda微积分、1936年的Emil Post公式1以及1936-37和1939年的Alan Turing机器。

缘起

“算法”一词的词源于将穆罕默德伊本穆萨的名字拉丁化，这是到Algorismus的第一步，他是波斯数学家、天文学家、地理学家和学者。

大约825年，al-khwarizmi写了一篇关于印度教-阿拉伯数字系统的阿拉伯语论文，在12世纪被翻译成拉丁语，标题为algoritmi de numero indorum。这个标题的意思是“印地安人的数字上的算法”，其中“算法”是翻译al-khwarizmi名字的拉丁化。选择他的名字，简单的意思是“十进制数字系统”。15世纪，在希腊语单词“算术”的影响下，拉丁语单词改为algorithmus，相应的英语术语“算法”在17世纪首次得到证实；19世纪引入了现代意义。

在英语中，它最初在1230年被使用，然后在1391年被使用。英语采用了法语术语，但直到19世纪末，“算法”才有了现代英语的含义。

这个词的另一个早期用法是1240年，在亚历山大德维尔迪欧撰写的名为《卡门·德阿尔戈里斯莫》的手册中。由此开始：

算法主义是目前我们使用印度数字2乘以5的艺术。

这首诗有几百行长，总结了印度骰子，塔利布斯印度语，或印度数字的新风格计算的艺术。

非正式定义

非正式的定义可以是“一组精确定义操作序列的规则”。包括所有计算机程序，包括不执行数值计算的程序。通常，程序只有在最终停止时才是一种算法。

一个典型的算法例子是欧几里得算法，用于确定两个整数的最大公因数；后面的章节例子描述了这个算法（还有其他的例子）。

Boolos，Jeffrey&1974，1999在以下引文中提供了该词的非正式含义：

没有人能写得足够快、足够长或足够小†（†“越来越小，没有限制……你应该试着写在分子、原子、电子上”），列出一个可枚举的无限集合的所有成员，用一些符号一个接一个地写下他们的名字。但是人类可以做同样有用的事情，在某些可枚举的无限集合的情况下：他们可以给出明确的指令来确定集合的第n个成员，对于任意有限的n。这些指令要非常明确地给出，在某种形式下，它们可以被一台计算机跟随，或者由一个能够驾驶汽车的人跟随。只对符号进行非常基本的运算。

“可枚举无限集”是其元素可以与整数一一对应的集合。因此，Boolos和Jeffrey说，一个算法暗示了一个过程的指令，该过程从一个或多个任意的“输入”整数“创建”输出整数，理论上，这些整数可以任意大。因此，一个算法可以是一个代数方程，例如y=m+n——两个任意的“输入变量”m和n，它们产生一个输出y。但是，不同作者试图定义这个概念，表明这个词的含义远不止这个，它的顺序是（例如加法）：

精确的指令（用“计算机”所理解的语言表示）。对于一个快速、高效、良好的过程，该过程规定了“计算机”的“移动”（机器或人，具有必要的内部信息和能力）。查找、解码，然后处理任意输入整数/符号m和n、符号+和=…以及“有效地”在“合理的”时间内，在指定的地点，以指定的格式，产生个整数y。

算法的概念也被用来定义可判定性的概念。这个概念对于解释正式系统是如何从一组小的公理和规则开始形成的至关重要。在逻辑上，一个算法需要完成的时间是无法测量的，因为它显然与我们习惯的物理维度无关。由于这些不确定性，即正在进行的工作的特征，导致算法定义不可用，既适合具体（在某种意义上）又适合术语的抽象用法。

形式化

算法对于计算机处理数据的方式至关重要。许多计算机程序都包含详细说明计算机执行特定任务（按特定顺序）应执行的特定指令的算法，例如计算员工工资或打印学生报告卡。因此，一个算法可以被认为是任何可以被图灵完整系统模拟的操作序列。主张这篇论文的作者包括明斯基（1967年）、萨维奇（1987年）和古列维奇（2000年）：

明斯基：“但我们也会保持，图灵……任何可以“自然”被称为有效的过程，实际上都可以通过（简单的）机器来实现。虽然这看起来很极端，但争论…对它有利是很难反驳的。

古列维奇：“…图灵支持他的论文的非正式论点证明了一个更强有力的论点：每种算法都可以被图灵机器模拟……根据Savage，算法是由图灵机定义的计算过程。

通常，当算法与处理信息相关联时，可以从输入源读取数据，写入输出设备，并存储数据以进行进一步处理。存储的数据被视为执行算法的实体的内部状态的一部分。实际上，状态存储在一个或多个数据结构中。

对于某些这样的计算过程，必须严格定义算法：以它在所有可能出现的情况下应用的方式指定。也就是说，任何有条件的步骤都必须系统地逐个处理；每种情况的标准必须是明确的（并且是可计算的）。

由于算法是精确步骤的精确列表，因此计算顺序对算法的运行始终至关重要。通常假定指令被明确地列出，并且被描述为“从上到下”的开始，这是一种更正式地由控制流描述的思想。

到目前为止，对算法形式化的讨论假定了命令式编程的前提。这是最常见的概念，它试图用离散的“机械”的方式来描述一个任务。对于这种形式化算法的概念来说，唯一的一点就是赋值操作，即设置变量的值。它源于“记忆”作为草稿的直觉。下面有这样一个例子。

有关构成算法的其他概念，请参阅函数编程和逻辑编程。

表示算法

算法可以用多种符号表示，包括自然语言、伪代码、流程图、Drakon图、编程语言或控制表（由译员处理）。算法的自然语言表达往往是冗长和模棱两可的，很少用于复杂或技术算法。伪代码、流程图、drakon图和控制表是表示算法的结构化方法，避免了自然语言语句中常见的许多不明确之处。编程语言主要用于以计算机可以执行的形式表示算法，但通常用作定义或记录算法的方法。

有各种各样的表示可能，人们可以将给定的图灵机程序表示为一系列机器表（更多见有限状态机、状态转换表和控制表）、流程图和drakon图（更多见状态图）或称为“q集”的基本机器代码或汇编代码的形式。

算法的表示可分为图灵机器描述的三个可接受级别：

高级描述

“忽略实现细节。在这个层次上，我们不需要提及机器如何管理其磁带或磁头。”

实现描述

“用于定义图灵机使用其头部的方式以及在磁带上存储数据的方式。在这个层次上，我们不提供状态或过渡函数的细节。”

正式描述

最详细的“最低级别”给出了图灵机的“状态表”。

有关所有三个级别中描述的简单算法“添加m+n”的示例，请参见算法示例。

设计

算法设计是指求解问题的一种方法或数学过程以及工程算法。算法的设计是运筹学许多解理论的一部分，如动态规划、分治等。设计和实现算法设计的技术也称为算法设计模式，例如模板方法模式和装饰器模式。

算法设计的一个最重要的方面是创建一个具有高效运行时的算法，也称为大O。

算法开发的典型步骤：

问题定义
模型的开发
算法说明
设计算法
检查算法的正确性
算法分析
算法的实现
程序测试
文件准备

实现

大多数算法都是作为计算机程序来实现的。然而，算法也可以通过其他方式实现，例如在生物神经网络（例如，人脑实现算法或昆虫寻找食物）、电路或机械装置中。

计算机算法

在计算机系统中，算法基本上是软件开发人员在软件中编写的逻辑实例，对于预期的“目标”计算机从给定的（可能为空）输入产生输出是有效的。即使是在旧硬件中运行的优化算法，也会比在更高效的硬件中运行的非最优（时间复杂度更高）算法产生更快的结果；这就是为什么算法（如计算机硬件）被视为技术的原因。

“优雅”（紧凑）程序，“良好”（快速）程序：在克努斯非正式地出现“简单和优雅”的概念，如此：

Knuth：“……我们需要一些定义松散的美学意义上的好算法。一个标准…是执行算法所用的时间长度…其他标准包括算法对计算机的适应性、简单性和优雅性等。

Chaitin：“……一个程序是“优雅的”，我的意思是它是产生输出的最小可能的程序。

在他的定义前加了一句话：“我将向你展示，你无法证明一个程序是‘优雅的’”——这样的证明可以解决停顿问题（同上）。

算法与可由算法计算的函数：对于给定的函数，可能存在多个算法。这是真的，即使没有扩展可供程序员使用的指令集。罗杰斯观察到“这是…重要的是要区分算法的概念，即过程和可由算法计算的函数的概念，即由过程生成的映射。同一个函数可能有几个不同的算法。

不幸的是，在好（速度）和优雅（紧凑）之间可能存在一种权衡——一个优雅的程序可能需要更多的步骤来完成计算，而不是一个不那么优雅的程序。下面是一个使用欧几里得算法的例子。

计算模型：计算机是一种受限制的机器，是一种盲目遵循其指令的“离散确定性机械装置”。不可区分的计数器代理和相对于代理的能力有效的指令列表。

明斯基在他的“非常简单的可计算性基础”中描述了兰贝克的“算盘”模型的一个更为契合的变体。除了停止之外，明斯基的机器还包括三种分配操作：零（例如，被0:L←0替换的位置的内容）、继承者（例如，L←L+1）和减量（例如，L←L−1）。程序员很少需要用如此有限的指令集编写“代码”。但明斯基（和梅尔扎克和兰贝克一样）表明，他的机器只有四种基本类型的指令：条件goto、无条件goto、分配/替换/替换和停止。

模拟算法：计算机（Computor）语言：Knuth建议读者“学习算法的最佳方法是尝试它”。…立即拿笔和纸做一个例子，但模拟或执行真实的东西呢？程序员必须将算法翻译成模拟器/计算机/计算机可以有效执行的语言。斯通举了一个例子：当计算二次方程的根时，计算机必须知道如何取平方根。如果不这样做，那么算法必须提供一组规则来提取平方根，才能有效地发挥作用。

这意味着程序员必须知道相对于目标计算代理（计算机/计算机）有效的“语言”。

但是模拟应该使用什么模型呢？vanEmdeBoas观察到，“即使我们把复杂性理论建立在抽象的基础上而不是具体的机器上，模型选择的任意性仍然存在。此时，模拟的概念进入了，当测量速度时，指令集很重要。例如，欧几里得算法中计算余数的子程序执行速度要快得多，如果程序员有一个“模”指令，而不仅仅是减法（或者更糟的是：只有明斯基的“减法”）。

结构化编程、规范结构：根据丘奇-图灵理论，任何算法都可以通过已知图灵完备的模型来计算，并且根据明斯基的演示，图灵完备只需要四种指令类型：条件goto、无条件goto、赋值、停止。Kemeny和Kurtz观察到，虽然无条件goto和有条件if-then goto的“无纪律”使用会导致“意大利面条代码”，但是程序员可以只使用这些指令编写结构化程序；另一方面，“用结构化语言编写结构化差的程序也可能，而且不太难。” Tausworthe增加了三个规范结构：序列、if-then-else和while-do，还有两个：do-while和case。结构化程序的另一个好处是，它使用数学归纳法来证明正确性。

标准流程图符号：图形辅助工具称为流程图，提供了描述和记录算法（以及一个计算机程序）的方法。就像minsky机器的程序流程一样，流程图总是从页面的顶部开始向下。它的主要符号只有四个：显示程序流的定向箭头、矩形（序列、GoTo）、菱形（if-then-else）和点（或tie）。标准结构由这些原始形状构成。子结构可以“嵌套”成矩形，但前提是上部结构只有一个出口。符号及其用于构建规范结构的用途如图所示。

例子

算法示例

最简单的算法之一是在随机顺序的数字列表中找到最大的数字。找到解决方案需要查看列表中的每个数字。由此得出一个简单的算法，可以用英语散文的高级描述来说明，如下所示：

高层次的描述：

如果集合中没有数字，则没有最高数字。
假设集合中的第一个数字是集合中最大的数字。
对于集合中的每个剩余数字：如果此数字大于当前最大数字，则将此数字视为集合中的最大数字。
当集合中没有要迭代的数字时，请将当前最大的数字视为集合中最大的数字。

（准）形式描述：用散文写，但更接近于计算机程序的高级语言，以下是用伪代码或pidgin代码对算法进行更正式的编码：

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largest ← L[0]
  for each item in L, do
    if item > largest, then
      largest ← item
  return largest

“←”表示分配。例如，“最大←项”是指最大值的值变化到项的值。

“返回”终止算法并输出以下值。

欧几里得算法

欧几里得计算两个数的最大公约数（gcd）的算法在其元素的第七卷（“初等数理论”）中出现。欧几里得提出了这样一个问题：“给定两个数互不相乘，以找到它们的最大公约数。”他定义“一个由单位组成的多个数”：一个计数数，一个不包括零的正整数。“测量”是将较短的测量长度s沿较长的长度l连续放置（q次），直到剩余部分r小于较短的长度。在现代词汇中，余数r=l−q×s，q是商，或余数r是“模”，即除法后剩余的整数分数部分。

为了使欧几里得方法成功，起始长度必须满足两个要求：长度不能为零，并且减法必须是“适当的”；即，测试必须保证两个数字中较小的数字从较大的数字中减去（或者，两个数字可以相等，以便减法得出零）。

欧几里得的原始证明又增加了第三个要求：两个长度不能是素数。欧几里得规定了这一点，这样他就可以建立一个约简和荒谬的证据，证明两个数字的共同度量实际上是最大的。虽然尼科马丘斯的算法与欧几里得的算法相同，但当这些数字互为素数时，就产生了它们共同度量的数字“1”。所以，准确地说，下面的算法确实是尼科马丘斯的算法。

欧几里得算法的计算机语言

执行欧几里得算法只需要几个指令类型：一些逻辑测试（条件goto）、无条件goto、赋值（替换）和减法。

位置用大写字母表示，例如S、A等。

一个地点的不同数量（数字）用小写字母书写，并且（通常）与该地点的名称相关。例如，起始位置L可能包含数字L=3009。

欧几里得算法的一个差程序

以下算法的框架是Knuth的Euclid’s和Nicomachus的四步版本，但它不是使用除法来查找余数，而是使用剩余长度r中较短长度s的连续减法，直到r小于s。用粗体显示的高级描述改编自Knuth 1973:2-4：

INPUT：

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
  INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
  R ← L

E0：确保R≥S

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
  IF R > S THEN
    the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
    GOTO step 6
  ELSE
    swap the contents of R and S.
4   L ← R (this first step is redundant, but is useful for later discussion).
5   R ← S
6   S ← L

E1：[求余数]：直到R中剩余的长度r小于S中较短的长度s，重复地从R中剩余的长度r中减去S中的测量数字s。

7 IF S > R THEN
    done measuring so
    GOTO 10
  ELSE
    measure again,
8   R ← R − S
9   [Remainder-loop]:
    GOTO 7.

E2：[余数是零吗？]：（i）最后一个度量精确，r中的余数为零，程序可以停止，要么（ii）算法必须继续：最后一个度量在r中留下的余数小于s中的度量数。

E3：【交换S和R】：欧几里得算法的核心。使用余数r来测量以前较小的数s；l用作临时位置。

11  L ← R
12  R ← S
13  S ← L
14  [Repeat the measuring process]:
    GOTO 7

OUTPUT：

1	16 HALT, END, STOP.

欧几里得算法的一个好程序

以下版本的欧几里得算法只需要六个核心指令就可以完成“不雅”的十三个指令；更糟的是，“不雅”需要更多类型的指令。在本文的顶部可以找到“优雅”的流程图。在（非结构化）基本语言中，步骤是编号的，指令let[]=[]是用←符号表示的赋值指令。

5 REM Euclid's algorithm for greatest common divisor
6 PRINT "Type two integers greater than 0"
10 INPUT A,B
20 IF B=0 THEN GOTO 80
30 IF A > B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 PRINT A
90 END

“优雅”是如何工作的：代替外部的“欧几里得循环”，“优雅”在两个“CO循环”之间来回移动，A>B循环计算A←A−B，A B≤A循环计算B←B−A。这是因为，当minutend m最后小于或等于subtrahend s（difference=minutend−subtrahend）时，minutend可以变为s（新的测量长度），副斜线可以变为新的r（要测量的长度）；换句话说，减法的“意义”相反。

以下版本可用于面向对象的语言：

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B){
     A=Math.abs(A);
     B=Math.abs(B);
     while (B!=0){
          if (A>B) A=A-B;
          else B=B-A;
     }
     return A;
}

检查欧几里得算法

算法是否按照作者的要求执行？一些测试用例通常对核心功能有一定的信心。但测试是不够的。对于测试用例，一个源代码使用3009和884。Knuth建议40902，24140。另一个有趣的例子是两个相对质数14157和5950。

但是“例外情况”必须被识别和测试。当r>s，s>r，r=s时，“烂代码”会正常运行吗？“优雅”同上：b>a，a>b，a=b？（对所有人都是）。当一个数字为零，两个数字都为零时会发生什么？（“烂代码”在所有情况下永远计算；“优雅”在a=0时永远计算。）如果输入负数会发生什么？分数？如果输入的数字，即由算法/程序计算的函数的域，只包含正整数（包括零），则在零处的失败表示算法（以及实例化它的程序）是一个部分函数而不是一个总函数。一个值得注意的失败由于例外是阿里安5号飞行501火箭失败（1996年6月4日）。

欧几里得算法的测量与改进

优雅（紧凑）与善良（速度）：只有六个核心指令，“优雅”是明显的赢家，而“不雅”是13个指令。然而，“不雅”的速度更快（它以更少的步骤到达停止）。算法分析指出了这种情况的原因：“Elegant”在每个减法循环中执行两个条件测试，而“Elegant”只执行一个条件测试。由于算法（通常）需要许多循环通过，所以在执行“b=0”时平均要浪费很多时间。仅在计算余数后才需要的测试。

算法可以改进吗？：一旦程序员判断一个程序“合适”和“有效”——也就是说，它计算出作者想要的函数，那么问题就变成了，它能被改进吗？

通过消除五个步骤，可以提高“不雅”的紧凑性。但是Chaitin证明了压缩算法不能用广义算法实现自动化；相反，它只能用启发式的方法实现，即通过穷尽搜索（在繁忙的海狸身上找到的例子）、试错、聪明、洞察力、归纳推理的应用等。观察到步骤4、5和6在步骤11、12和6中重复。这些步骤以及步骤2和3可以被消除。这将核心指令的数量从13个减少到了8个，这使得它在9个步骤中“比”优雅“更优雅”。

移动“b=0”可以提高“优雅”的速度。在两个减法循环之外进行测试。此更改需要添加三个指令（b=0？A＝0？GOTO）。现在，“优雅”计算示例数更快；对于任何给定的a、b和r、s，是否总是这样，都需要进行详细的分析。

算法分析

通常重要的是要知道给定算法理论上需要多少特定资源（如时间或存储）。已经开发了用于分析算法以获得定量答案（估计值）的方法；例如，上述排序算法的时间要求为o（n），使用n作为列表长度的大o符号。在任何时候，算法只需要记住两个值：迄今为止发现的最大值，以及它在输入列表中的当前位置。因此，如果不计算存储输入数字所需的空间，则称其具有O（1）的空间要求；如果计算输入数字，则称其具有O（n）的空间要求。

不同的算法可以用不同的指令集在比其他算法更少或更多的时间、空间或“努力”内完成相同的任务。例如，当用于排序列表或数组上的表查找时，二进制搜索算法（具有cost o（log n））优于顺序搜索（cost o（n））。

形式与经验

对算法的分析和研究是计算机科学的一门学科，通常是抽象地实践，而不使用特定的编程语言或实现。从这个意义上讲，算法分析与其他数学学科相似，因为它关注算法的基本属性，而不是任何特定实现的细节。

通常，伪代码用于分析，因为它是最简单和最一般的表示。然而，最终，大多数算法通常在特定的硬件/软件平台上实现，它们的算法效率最终通过实际代码进行测试。

对于“一次性”问题的解决，特定算法的效率可能不会产生重大后果（除非n非常大），但对于设计用于快速交互、商业或长寿命科学应用的算法，这可能是至关重要的。从小n到大n的缩放经常暴露出效率低下的算法，否则是良性的。

经验测试很有用，因为它可能揭示影响性能的意外交互作用。基准点可用于比较程序优化前后的潜在改进与程序优化后的算法。然而，经验检验不能取代正式的分析，以公平的方式进行分析也不容易。

执行效率

为了说明即使在成熟的算法中也可能有潜在的改进，最近一项与FFT算法（在图像处理领域中大量使用）相关的重大创新可以将处理时间缩短1000倍，用于医疗成像等应用。一般来说，速度的改进取决于这一问题在实际应用中非常普遍。这种规模的加速使计算机设备能够广泛地利用图像处理（如数码相机和医疗设备）来降低功耗。

连续算法

形容词“continuous”应用于“algorithm”一词时可以表示：

一种对表示连续量的数据进行运算的算法，即使该数据由离散近似表示，这种算法也在数值分析中进行研究；或一种微分方程形式的算法，在模拟计算机上连续地对数据进行运算。

法律问题

算法本身通常不具有专利权。在美国，仅由抽象概念、数字或信号的简单操作组成的主张不构成“过程”（USPTO 2006），因此算法不具有专利权（如Gottschalk v.Benson）。然而，算法的实际应用有时是可申请专利的。例如，在Diamond v.Diehr中，应用简单反馈算法帮助合成橡胶固化被认为是可申请专利的。软件专利是一个极具争议的领域，涉及算法的专利备受批评，尤其是数据压缩算法，如Unisys的LZW专利。

此外，一些加密算法有导出限制。

算法的发展

古代近东

古希腊使用了算法。两个例子是埃拉托斯坦的筛子，这是尼科马克《算术导论》中描述的：Ch9.2和欧几里得算法，这是在欧几里得元素（约公元前300年）中首次描述的。Ch9.1巴比伦粘土片描述和使用算法程序来计算重要天文事件的时间和地点。

离散和可分辨符号

理货记号：为了记录他们的羊群、他们的粮食袋和他们的钱，古人使用理货：在木棍上堆积石头或留下记号，或在粘土中制作离散的符号。通过巴比伦和埃及对标记和符号的使用，最终罗马数字和算盘得以发展（Dilson，第16-41页）。在图灵机器和后图灵机器计算中使用的一元数字系统算法中，计数标记突出显示。

作为数字“占位符”的符号处理：代数

古希腊几何学家（欧几里得算法）、印度数学家布拉马库塔（Brahmagupta）和波斯数学家阿尔赫瓦里兹米（Algorism和Algorithmi是从他们的名字衍生而来）以及西欧数学家的工作最终达到了莱布尼兹的微积分比率（ca 1680）的概念：

莱布尼兹提出了逻辑代数，这是一种代数，它规定了用普通代数规定数字运算规则的方式来处理逻辑概念的规则。

具有离散状态的机械装置

博尔特认为重量驱动的钟的发明是“关键发明[中世纪的欧洲]”，特别是边缘逃逸为我们提供了一个机械钟的滴答声。从13世纪开始，精确的自动机器”。立即导致了“机械自动化”，最终导致了“计算机器”—19世纪中叶查尔斯·巴贝奇和艾达·洛维拉斯伯爵夫人的差分引擎和分析引擎。作为计算机巴贝奇的分析引擎，第一台设备被认为是一台真正的图灵完整的计算机，而不仅仅是一台计算器，因此有时也被称为“历史上的第一个程序员”，尽管巴贝奇的第二台设备的完整实现在她有生之年之后才得以实现。

逻辑机器1870年——斯坦利·杰文斯（Stanley Jevons）的“逻辑算盘”和“逻辑机器”：技术问题是当以类似于现在所称的卡诺图的形式呈现时，减少布尔方程。Jevons（1880）首先描述了一个简单的“算盘”，它是一种用别针装饰的木头滑片，其设计使任何部分或类别的[逻辑]组合都能被机械地挑选出来。然而，最近，我把这个系统简化成一个完全机械的形式，从而把整个间接的推理过程体现在所谓的逻辑机器上：“他的机器配备了“某些可移动的木杆”和“脚上有21个键，如钢琴的键等等”。用这台机器，他可以分析“三段论或任何其他简单的逻辑论证”。

1870年，他在英国皇家学会的研究员面前展示了这台机器。然而，另一位逻辑学家约翰·文恩（JohnVenn）在1881年的《符号逻辑》（Symbolic Logic）一书中，却对这一努力的目光：“我对有时被称为逻辑机器的东西的兴趣和重要性没有很高的估计……在我看来，目前已知的或可能被发现的任何发明都不应该被称为逻辑机器”，请参阅算法特征。但不甘示弱，他也提出了“一个计划，有点类似，我理解，以教授的算盘，对应于Jevons教授的逻辑机，可以描述以下发明。我宁愿称之为一个逻辑图机器。但我认为，它可以完全完成任何逻辑机器所能合理预期的一切工作。

提花织机、Hollerith穿孔卡片、电报和电话——机电继电器：Bell和Newell（1971年）指出，提花织机（1801年）、Hollerith卡片的前身（穿孔卡片，1887年）和“电话交换技术”是导致第一台计算机发展的一棵树的根。电报，电话的前身，在全世界使用，它的离散和可区分的字母编码作为“点和破折号”一个共同的声音。到19世纪末，售票机磁带（约1870年代）开始使用，1890年美国人口普查中使用的是霍利斯卡。然后电传打字机（约1910年）带着穿孔纸，在磁带上使用波特码。

机电式继电器的电话交换网络（发明于1835年）是数字加法装置的发明者乔治·斯蒂比茨（1937年）的工作的基础。当他在贝尔实验室工作时，他观察到机械计算器与齿轮的“繁重”使用。他在1937年的一个晚上回家，打算测试他的想法…修补工作结束后，Stibitz构建了一个二进制添加设备。

Davis（2000）观察了机电式继电器的特殊重要性（其两个“二进制状态”打开和关闭）：

只有从20世纪30年代开始，随着使用电气继电器的机电计算器的发展，机器的制造才有了巴贝奇预想的范围。

19世纪到20世纪中叶的数学

符号和规则：在快速连续的过程中，乔治·布尔（1847、1854）、戈特洛布·弗雷格（1879）和朱塞佩·皮诺（1888-1889）的数学将算术简化为一系列由规则操纵的符号。皮亚诺的算术原理，由一种新方法（1888年）提出，是“在符号语言中对数学公理化的第一次尝试”。

但是海耶诺特给了弗雷格（1879）这个荣誉：弗雷格的“也许是有史以来最重要的逻辑著作”。…其中我们看到一种“公式语言”，即一种语言特征，一种用特殊符号书写的语言，“纯粹的思想”，即没有修辞修饰…由特定的符号构成，这些符号按照明确的规则进行操作。弗雷格的作品在《数学原理》（1910-1913）中被阿尔弗雷德·诺斯怀特黑德和伯特兰·罗素进一步简化和放大。

悖论：同时，文献中出现了许多令人不安的悖论，特别是布阿里-富蒂悖论（1897年）、拉塞尔悖论（1902-03年）和理查德悖论。由此产生的考虑导致了Kurt G_del的论文（1931年），他特别引用了骗子悖论，它完全降低了递归的数字。

有效可计算性：为了解决希尔伯特在1928年精确定义的EntscheidungsProblem问题，数学家首先着手定义“有效方法”或“有效计算”或“有效可计算性”（即成功的计算）的含义。随后，出现了以下内容：阿隆佐·丘奇（Alonzo Church）、斯蒂芬·克莱恩（Stephen Kleene）和J.B.罗瑟（J.B.Rosser）的《λ-微积分》（λ-微积分）：根据雅克·赫伯兰（Jacques Herbrand）的建议（参见1934年G·戴尔普林斯顿（Princeton）的演讲）和克莱恩（Kleene）随后的简化，对“一般递归”（Entscheidu）进行了精细的定义。

问题是无法解决的，埃米尔·波斯特把有效的可计算性定义为一个工人在不经意地遵循一系列指示的情况下，在一系列房间里左右移动，或者在那里标记或擦除一张纸，或者观察纸，并对下一条指示作出“是”或“否”的决定。ungsproblem是无法解决的，因为他使用了他的“A-[自动-]机器”——实际上几乎等同于波斯特的“公式”，J.Barkley Rosser对“有效方法”的定义，即“机器”。S.C.Kleene提出了“教会论文”的前身，他称之为“论文一”，几年后，Kleene将他的论文重命名为“教会论文”。并提出了”图灵论文”。

埃米尔（1936年）和阿兰·图灵（1936-1939）

Emil Post（1936）将“计算机”（人类）的行为描述如下：

“…涉及两个概念：一个符号空间的概念，在该空间中执行从问题到答案的工作，以及一组固定不变的方向。

他的符号空间是：

“双向无限的空间或盒子序列…问题解决者或工作人员将在这个符号空间中移动和工作，能够一次只在一个框中移动和工作……一个框只允许有两种可能的条件，即空的或没有标记的，并且其中只有一个标记，例如垂直笔画。

“一个盒子被挑出来称为起点。…一个特定的问题是由有限数量的框（即输入框）以符号形式给出，并用笔画进行标记。同样地，答案[即输出]将以符号形式通过这样一个标记框的配置给出…

“适用于一般问题的一组指导方针在应用于每个特定问题时会建立一个确定性过程。此过程仅在到达（c）型方向[即停止]时终止。更多信息请参见后转向机。

阿兰·图灵的作品早于斯蒂比茨（1937年）；斯蒂比茨是否知道图灵的作品还不得而知。图灵的传记作者相信图灵使用一种类似打字机的模型是出于年轻人的兴趣：“艾伦小时候就梦想着发明打字机；图灵夫人有一台打字机，他很可能从问自己把打字机称为‘机械’是什么意思开始。”考虑到摩尔斯电码和电报的流行，蒂克克尔磁带机和电传打字机，我们可能猜测所有的影响。

图灵他的计算模型现在被称为图灵机器，正如波斯特所做的那样，开始分析一台人类计算机，他将其简化为一组简单的基本运动和“精神状态”。但他继续向前一步，创建了一个机器作为计算数字的模型。

计算通常是通过在纸上写一些符号来完成的。我们可以假设这篇论文像孩子的算术书一样被分成正方形……然后我假设计算是在一维的纸上进行的，也就是说，在被分成正方形的磁带上进行的。我还要假设，可以印刷的符号数量是有限的…

计算机在任何时刻的行为都是由他所观察到的符号和他在那一时刻的“精神状态”决定的。我们可以假设有一个b与符号或正方形的数量绑定，计算机可以在一个时刻观察到。如果他想观察更多，他必须使用连续的观察。我们还将假设需要考虑的心理状态的数量是有限的…

“让我们想象一下，计算机执行的操作被分割成‘简单操作’，这些操作非常简单，不容易想象它们被进一步分割。”

图灵的约化得到以下结果：

“因此，简单的操作必须包括：“

（a）观察到的一个方块上符号的变化“

（b）观察到的其中一个正方形变为之前观察到的其中一个正方形的L平方内的另一个正方形。

“这可能是因为其中的一些变化必然会引起精神状态的变化。因此，最一般的单一操作必须视为以下操作之一：

“（a）符号可能发生的变化（a）以及思想状态可能发生的变化。

（b）观察到的正方形可能发生的变化（b），以及可能的精神状态变化。

“我们现在可以建造一台机器来完成这台计算机的工作。”

几年后，图灵用这种有力的表达扩展了他的分析（论文，定义）：

如果一个函数的值可以通过某种纯粹的机械过程找到，那么它被称为“有效可计算的”。虽然很容易直观地理解这个概念，但还是需要有一些更明确的、数学上可表达的定义。我们可以从字面上理解这句话，通过一个纯粹的机械过程来理解，这个过程可以通过一台机器来实现。可以用某种正常形式对这些机器的结构进行数学描述。这些思想的发展导致了作者对可计算函数的定义，以及对可计算性的识别†与有效的可计算性。

我们将使用表达式“可计算函数”来表示机器可计算的函数，并且我们让“有效可计算”指的是直观的概念，而不需要对这些定义中的任何一个进行特别的识别。”

Rosser（1939年）和S.C.克林（1943年）

J.Barkley Rosser以以下方式定义了“有效方法”：

“有效方法”在这里是一种相当特殊的方法，它的每一步都是精确确定的，并且一定会以有限的步骤产生答案。有了这个特殊的含义，迄今为止已经给出了三种不同的精确定义。其中最简单的陈述（由于post和turing）基本上是说，如果一个人能制造出一台机器，在没有人为干预的情况下解决集合的任何问题，除了插入问题和（稍后）阅读答案，就存在解决某些问题的有效方法。这三个定义都是等价的，所以使用哪一个并不重要。此外，这三者都是等价的，这是证明任何一个的正确性的有力论据。”（罗瑟1939:225-226）

Rosser的脚注5引用了Church和Kleene的著作及其对λ-可定义性的定义，特别是Church在他的初等数理论的一个无法解决的问题（1936）中对它的使用；Herbrand和G_del及其对递归的使用，特别是G_del在他著名的论文中对形式上不可决定的pri命题的使用。NCPIA Mathematica和相关系统I（1931）；以及Post（1936）和Turing（1936-37）在其计算机制模型中。

史蒂芬C克莱恩把他现在著名的“论文一”定义为教会图灵论文。但他是在以下情况下做的（原文中的粗体字）：

“12。算法理论…在建立一个完整的算法理论时，我们要做的是描述一个过程，该过程对于独立变量的每一组值都是可执行的，该过程必然终止，并且以这样的方式，从结果中我们可以看到一个明确的答案，“是”或“否”，对于问题，“谓词值是真的吗？”（克莱恩1943:273）

1950年以后的历史

许多努力都是为了进一步完善“算法”的定义，由于围绕数学（特别是丘奇-图灵理论）和思想哲学（特别是关于人工智能的争论）的问题，活动正在进行中。有关更多信息，请参见算法特征化。

算法

缘起