数学（约年—现在）

• 什么是抽取合理结论的形式化规则？

• 什么可以被计算？

• 我们如何用不确定的知识进行推理？

哲学家们标志出了 AI 的大部分重要思想，但是实现成为一门规范科学的飞跃就要求在三个基础领域完成一定程度的数学形式化：逻辑、计算和概率。

形式逻辑的思想可以追溯到古希腊哲学家（参见第七章），但是其数学的发展其实是从乔治·布尔（George Boole，1815—1864）的工作开始的，他完成了命题逻辑也称布尔逻辑（布尔，1847）的细致工作。1879年，高特洛布·弗雷格（Gottlob Frege，1848—1925）扩展了布尔逻辑，使其包含对象和关系，创建了作为当今最基本的知识表示系统的一阶逻辑[5]。阿尔弗雷德·塔斯基（Alfred Tarski，1848—1925）引入一种参考理论，可以表现如何把逻辑对象与现实世界的对象联系起来。下一步是要确定逻辑和计算能做到的极限。

一般认为第一个不可忽视的算法是欧几里德（Euclid）的计算最大公约数的算法。对于算法自身的研究要回溯到9世纪的波斯数学家al-Khowarazmi，他的著述还把阿拉伯数字和代数引入了欧洲。布尔和其他人探讨了逻辑演绎的算法，而到了19世纪晚期，把一般的数学推理形式化为逻辑演绎的努力已经展开。1900年，大卫·希尔伯特（David Hilbert，1862—1943）提出了一份包括23个问题的清单，他正确地预言了这些问题将使数学家们忙碌近一个世纪。他提出的最后一个问题是：是否存在一个算法可以判定任何涉及自然数的逻辑命题的真实性——著名的可判定性问题（Entscheidungsproblem），或称判定问题。实质上，希尔伯特要问的是，有效的证明过程的能力是否有基础的局限性。在 1930年，库特·哥德尔（Kurt Gödel，1906—1978）提出存在一个有效的过程可以证明罗素和弗雷格的一阶逻辑中的任何真值语句，但是一阶逻辑不能捕捉到刻画自然数所需要的数学归纳法原则。在 1931年，他证明了确实存在真实的局限。他的不完备性定理表明在任何表达能力足以描述自然数的语言中，在不能通过任何算法建立它们的真值的意义上，存在不可判定的真值语句。

这个基本的结果还可以解释为表明整数的某些函数无法用算法表示，即它们是不可计算的。这激发了阿兰·图灵（1912—1954）的热情，他试图精确地刻画哪些函数是能够被计算的。此观念事实上是有些问题的，因为计算或者有效过程的概念实际上是无法给出形式化定义的。然而，丘奇—图灵论题说明图灵机（图灵，1936）有能力计算任何可计算的函数，也就作为一种充分的定义而被大家所接受。图灵还说明了有一些函数是没有图灵机可以计算的。例如，没有通用的图灵机可以判断一个给定的程序对于给定的输入能否返回答案或者永远运行下去。

虽然不可判定性和不可计算性对于理解计算是很重要的，不过不可操作性有着更重要的影响。粗略地说，如果解决一个问题需要的时间随实例的规模成指数级增长，那么该问题被称为不可操作的。多项式级和指数级增长的区别最先在20世纪60年代中期得到重视（Cobham，1964；Edmonds，1965）。这显得很重要，是因为指数级增长意味着即便是普通的大规模的实例都无法在合理的时间内解决。因此，应该致力于把产生智能行为的全部问题划分成可操作的子问题，而不是不可操作的子问题。

如何才能认识不可操作问题？以斯蒂文·库克（Steven Cook，1971）和理查德·卡普（Richard Carp， 1972）为先驱进行研究的 NP—完全理论提供了一种方法。库克和卡普证明有大量各种类别的规范的组合搜索和推理问题属于NP—完全问题。任何NP—完全问题类可归约而成的问题类很可能是不可操作的。（尽管尚未证明 NP—完全问题必然不可操作，大多数理论家相信它是。）这些结果与大众新闻欢迎第一台计算机的乐观——“比爱因斯坦更快”的“电子超级大脑”！——相对立。近年来，AI帮助解释了为什么NP—完全问题的一些实例很难，而同时另外一些比较容易（Cheeseman等人，1991）。

在逻辑和计算之外，数学对AI的第三个重要贡献是概率理论。意大利人Geroamo Cardano（1501—1576）首先搭建了概率思想的框架，按照赌博事件的可能结果来描述它。概率很快成为所有需要定量的科学的无价之宝，帮助对付不确定的测量和不完备的理论。彼埃尔·费尔马（Pierre Fermat，1601—1665），布雷西·帕斯卡（Blaise Pascal，1623—1662），詹姆斯·贝努利（James Bernoulli，1654—1705），彼埃尔·拉普拉斯（Pierre Laplace，1749—1827），以及其他人推进了理论并引入新的统计方法。托马斯·贝叶斯（Thomas Bayes，1702—1761）提出了根据新证据更新概率的法则。贝叶斯法则及由其衍生出来的被称为“贝叶斯分析”的领域形成了大多数AI系统中不确定推理的现代方法的基础。