当人类开始思考世界时，很多都无法解释， 人们就会归结为魔法或喜怒无常神的意志。 这正是非机械的解释。非机械模型可以有多种形式。 许多文化都重视与人类和地球有关的天文事件， 并且我们还在继续这样做。 每当我们面对无法解释的事情时，有些人仍将其归因于外星智慧或超自然现象。 但是在寻找工具以消除虚构事实和理解支持现代科学的自然世界 方面取得进展的第一个记录始于希腊哲学 和算术和几何学中某种形式的逻辑的发展，这仍然是今天现代科学的基础。 亚里士多德是第一个以系统的方式处理形式逻辑原理的人。 逻辑的历史是有效推理的历史。 事实上，“logos”在希腊语中意思是原因。 逻辑作为一种正式的推理方式，在革命时期开始 于19世纪中期复兴，当时该主题发展成一种严谨而正式的学科， 其范式是希腊数学中使用的证明方法。 在我的个人收藏中，有幸拥有一本书，它是数学几何领域的创始人。 欧几里得的几何原本副本 于1573年出版，但它写于 公元前300年左右，远在圣经之前。 数学证明的概念在此时已达到成熟， 并在此后系统地使用。 13世纪初期见证了中世纪后希腊哲学的复兴， 并回归机械模型，一位名叫威廉奥卡姆的哲学家， 出生在我离英格兰不远的地方， 并且相信在牛津大学开始， 一直在思考与寻找理由来排除Rube Goldberg机器类型的解释相关的问题。 即使是最简单的现象也会有很复杂的解释。 我们今天知道他的论点是奥卡姆的剃刀， 也被称为简约法则。 奥卡姆剃刀 确定当提出竞争模型时，应该选择做出最少假设的模型。 因此，在Rube Goldberg 绘制的自动餐巾纸的情况下， 如果我们没有看到他们第一手操作， 我们会简单地抛弃所有机制， 我们宁愿偏向更简单的模型作为可能的解释。 例如，该人本身或其他东西操作餐巾纸而不是一个过于复杂的机器。 在科学方面，奥卡姆剃刀被用作理论模型开发和选择的指导原则， 但我们会看到有好的证据支持奥卡姆剃刀。 我对该主题的贡献之一是表明 奥卡姆的论证不仅仅是由本课程的核心概念，算法复杂性的概念形式化， 而且还是算法复杂性的数值近似。提供有力的证据支持奥卡姆的剃刀。 我们稍后会正式详细地 看到这一点。 我们将看到算法复杂性如何与奥卡姆(Occam)倡导的简单性相关联。 由于George Boole(乔治布尔)，这种类型的的代数称为布尔逻辑。 布尔逻辑对于计算机科学尤为重要，因为它非常适合二进制系统， 其中每个位的值都为1或0，就像true或false一样。 布尔逻辑在本课程的后期将非常重要，因为我们将使用一种称为布尔网络的系统。 布尔网络是具有命题公式的网络，例如真值表上 根据网络连接方式处理信息的网络。 例如，在所示的真值表中，有一个公式意思是P和Q， 符号P，Q，其中P和Q是可以是假或真的命题， 用字母F或T表示，也可以简单地为0或1。 连词和被称为布尔运算符，并为两个命题分配一个值，告诉它们是一起是真还是假。 例如，对于and运算， 只有当两个命题P和Q为真时，最终公式才是真的。 假设P表示灯亮， 命题Q表示有空座位。 这两个陈述可能都是真或假，或者如果我说灯亮了并且有空座位， 这种断言只有在P和Q同时为真的情况下才能成立。 这与布尔运算符不同，或者，如果我们声称 灯亮或有空座，那么两个命题中的任何一个为真， 即使一个是假，则由P或Q表示的命题也可以为真。 例如，如果灯关闭，但有空座位。 请注意，这种公式可以任意长，因此它们变得不那么简单， 在与其他运算符组合时可以实现更复杂的情况。 现在可以清楚地看到这种简单的逻辑如何与因果关系密切相关。 例如，如果P，Q或两者 都为真，则公式P或Q只能为真，因此 P或Q为真或假的观察告诉我们关于原因的真值的一些事情。 也就是说，P和Q的真值分别作为其真值的结果 作为式为真或假的原因。 然而，通常的数学和逻辑也更感兴趣的真理， 又连接到因果关系，但只有间接因为证明不是一种产生机构 它不能是至少建设性或不一定。 也就是说，它可能还是不写，例如，用于计算机中的程序来进行数学证明的细节。 像皮亚诺着名的对角化方法一样，不是构造性的。 但在逻辑和证明20世纪的真理被打破， 在一个非常根本不知怎的，这种方式分离， 并打破了因果关系的直接连接。 然而，当我们将在课程后面看到， 当我们覆盖计算理论的某些方面， 这种破裂是必不可少的了解，我们可以通过纯粹的推理，逻辑的方式来完成真理 和因果关系途径的一些基本性质， 机制和算法。 事实上，这种逻辑和证据是断开的并不意味着我们回到了魔法和占星术的时代来解释复杂的现象。 相反，这些领域的发展导致了新的 计算方法和我们今天处理科学的方式。 特别是，通过计算的视角，甚至更重要的是， 导致了通用计算的概念，使我们将详细探讨。 但重要的是要明白，实际上 因果关系是非常难以计算的，这些真相和证明 被形式逻辑打破了。