计算复杂性理论 computational complexity theory (Walter Dean)
首次发表于 2010 年 7 月 21 日星期三；实质性修订于 2021 年 6 月 16 日星期三
在我们日常的言论中，我们区分执行计算的物理系统（如计算机和计算器）和不执行计算的物理系统（如岩石和雨滴）。在计算设备中，我们区分更强大和不那么强大的设备。这些区别既具有实际意义，也具有理论意义：超级计算机可以在几分钟内完成一台笔记本电脑需要数十年才能完成的计算，而计算器无法做一些笔记本电脑即使在原则上也无法完成的事情。是什么决定了这些区别？岩石和计算器之间，或者计算器和计算机之间是否存在原则上的区别？回答这些问题比看起来更困难。
除了我们日常的交流之外，计算在许多科学中都起着核心作用。 计算机科学家设计、构建和编程计算机。 但是，什么才算是计算机呢？ 如果一个销售员把一块普通的石头卖给你作为计算机，你可能应该要回你的钱。 再次，这块石头缺少了什么，使得它不具备真正计算机的特征呢？
你能建造多强大的计算机？你能建造一台可以计算任何你想要的东西的机器吗？尽管经常说现代计算机可以计算任何东西（即，自然数的任何函数，或者等价地，来自有限字母表的字符串的任何函数），但这是不正确的。普通计算机只能计算这些函数的微小子集。是否在物理上有可能做得更好？哪些函数是物理上可计算的？这些问题与物理学的基础紧密相关。
计算在心理学和神经科学中也是核心内容，也许在生物学的其他领域也是如此。根据认知计算理论，认知是一种计算：认知系统的行为是通过其执行的计算来因果解释的。为了测试某种计算理论，我们需要知道在物理系统中什么算作计算。再次强调，计算的本质是经验科学的基础。
抽象计算与具体计算
计算可以通过数学方法进行研究，通过正式定义计算对象（如算法和图灵机），并证明关于它们性质的定理。计算的数学理论是数学的一个成熟分支，它处理抽象的计算，不考虑物理实现。
相比之下，科学和日常实践中大多数计算的用途涉及具体计算：物理系统中的计算，如计算机和大脑中的计算。具体计算与抽象计算密切相关：例如，我们谈论物理系统运行算法或实现图灵机。但具体计算与抽象计算之间的关系并不是计算理论的一部分，需要进一步研究（参见 Curtis-Trudel forthcoming-a，提出抽象和具体计算无法统一解释的论点）。关于具体计算的问题是本文的主要主题。然而，重要的是要记住一些基本的数学结果。
计算的最重要概念是数字计算，这是由 Alan Turing、Kurt Gödel、Alonzo Church、Emil Post 和 Stephen Kleene 在 1930 年代正式化的。他们的工作调查了数学的基础。一个关键问题是一阶逻辑是否可判定——是否存在一种算法，可以确定任何给定的一阶逻辑公式是否是定理。
Turing (1936–7) 和 Church (1936) 分别证明了答案是否定的：不存在这样的算法。为了证明这一点，他们提供了对有效可计算函数这一非正式概念的精确描述。图灵是以所谓的图灵机（TMs）的形式做到这一点——这些设备根据有限多的指令操作写在磁带上的离散符号。其他逻辑学家也做了同样的事情——他们以其他概念，如 λ-可定义函数和一般递归函数的形式，形式化了有效可计算函数的概念。
令人惊讶的是，所有这些概念都被证明在外延上是等价的：在任何这些形式体系中可计算的任何函数也可以在其他任何一个形式体系中计算。他们将此视为证据，证明他们对“算法”或“有效可计算函数”的精确定义的追求是成功的。由此产生的观点——即图灵机和其他等价形式体系捕捉了算法的非正式概念——现在被称为 Church-Turing 假设（更多内容请参见第 4 节）。由图灵等人的工作使得可计算函数的研究成为计算理论的一部分。
图灵等人关于计算概念的理论意义几乎无法言表。正如哥德尔指出的（在塔斯基之后的一次讲座中）：
塔斯基在他的讲座中强调（我认为是正确的）一般递归概念（或图灵的可计算性）的重要性。我认为这种重要性主要在于这个概念首次成功地给出了一个有趣的认识论概念的绝对定义，即不依赖于所选择的形式主义。（哥德尔，1946 年，84 页）
图灵还表明存在通用图灵机——可以计算任何其他图灵机可计算函数的机器。通用机器通过执行编码模拟机器行为的指令来实现这一点。假设了教会-图灵论题，通用图灵机可以计算任何可由算法计算的函数。这一结果对计算机科学非常重要：您不需要为不同功能构建不同的计算机；一个通用计算机就足以计算任何可计算函数。现代数字计算机在这个意义上是通用的：数字计算机可以计算任何可由算法计算的函数，只要它们有足够的时间和内存。（严格来说，通用机器具有无限的内存，而数字计算机的内存可以扩展但不是无限的，因此它们不是无限的。）
上述结果不应与计算机可以计算任何东西的常见说法混淆。这种说法是错误的：可计算性理论的另一个重要结果是，大多数函数不能被图灵机（因此也不能被数字计算机）计算。图灵机计算定义在可数域上的函数，例如来自有限字母表的字母串。这样的函数有不可数多个。但是图灵机只有可数多个；你可以通过列出每个图灵机规范（即某个有限字符串）来枚举图灵机。由于不可数无穷远大于可数无穷，因此可以得出结论，图灵机（因此数字计算机）只能计算所有函数的一小部分（在可数域上，例如自然数或字母串）。
TMs 和大多数现代计算机被称为（经典）数字计算机，即操作离散、明确定义状态字符串的计算机。数字计算机有时与模拟计算机进行对比，后者操作可以是连续的变量。连续变量是可以随时间连续改变其值并在一定区间内取任何值的变量。模拟计算机主要用于解决某些微分方程系统（Pour-El 1974，Rubel 1993）。
经典数字计算机也可以与量子计算机进行对比。量子计算机操作称为 qudits 的量子态（通常是二进制 qudits，称为量子位）。与数字计算机的计算状态不同，从某些重要方面来看，qudits 在某种程度上彼此之间并不明确可区分。本条目将主要关注经典数字计算。有关量子计算的更多信息，请参阅量子计算条目。
在计算理论中研究的相同对象——图灵机、算法等——通常被认为是由具体物理系统实现的。这带来了一个问题：当计算是由抽象数学形式定义时，如何让一个具体的物理系统执行计算？这可能被称为计算实现的问题。
计算实现问题可以用几种不同的方式来表述。柏拉图主义者将可计算性理论的形式主义解释为定义抽象对象。根据这种解释，图灵机、算法等都是抽象对象。但是一个具体的物理系统如何实现一个抽象对象，这种实现关系究竟是什么？反柏拉图主义者将可计算性理论的形式主义简单地看作是抽象的计算描述。但一个具体的物理系统如何满足一个抽象的计算描述？无论计算实现问题如何表述，解决它都需要一个关于具体计算的说明——关于一个物理系统如何执行给定计算的说明。
一个密切相关的问题是区分物理系统，比如数字计算机，它们确实进行计算（如果有的话），以及像岩石这样的物理系统，它们不进行计算（或者看起来是这样）。与计算机不同，普通的岩石不会在计算机商店出售，通常也不被视为计算机。为什么？计算机具有什么岩石缺乏的东西，以至于计算机进行计算而岩石不会？（如果确实如此的话？）换句话说，什么样的具体系统能够进行计算？对这些问题的不同回答导致了对具体计算的不同解释。
关于具体计算性质的问题不应与计算建模的问题混淆。许多物理系统的动态演化可以通过计算模型来近似——这些计算模型是模拟或预测某些感兴趣系统的动力学或运动学的计算机程序。岩石的行为——以及河流、生态系统和行星系统等等——很可能可以通过计算进行建模。但这并不意味着被建模的系统是计算设备——它们本身进行计算。乍看之下，只有相对少数且非常特殊的系统进行计算。解释这些系统何以特殊——或解释我们感觉它们特殊的原因——是具体计算性质的解释工作。
2. 具体计算的描述
任何关于具体计算的描述必须解决的基本问题可以通过以下图表来看出。考虑某个计算系统 C（例如一个抽象自动机）和一个物理系统 P。系统 C 具有计算状态 s1 和 s2，使得 C 根据 C 的规范从 s1 过渡到 s2。系统 P 具有物理状态 p1 和 p2，使得 P 根据 P 的动力学从 p1 过渡到 p2。同一类型系统状态之间的过渡——图表中的箭头——无需解释：在 C 的情况下要么是规定的，要么在 P 的情况下是众所周知的物理动力学。然而，为了让 P 被视为 C 的实现，必须解释一种系统类型的状态与另一种系统类型的状态之间的假定连接（虚线）。以下描述提供了不同的方式来表征这种连接，要么通过明确虚线代表什么，要么通过缩小可能包括 P 的物理状态或过渡，要么两者兼而有之。
图表
2.1 简单映射解释
计算的最早和最有影响力的描述之一是由希拉里·普特南提出的。在第一次近似中，这一描述表明，任何可以准确描述为计算描述 C 的东西都是实现 C 的计算系统。
更准确地说，普特南仅以图灵机（Turing Machines，TMs）的术语勾勒了他最早的观点，他引用了“机器表”这一标准定义特定 TMs 的方式。 机器表由 TM 的（有限数量的）内部状态的每一列和机器的符号类型的每一行组成。 机器表中的每个条目指定了机器在给定相关符号和内部状态时的操作。 这是普特南解释物理系统成为 TM 所需的条件。
一个“机器表”描述了一台机器，如果该机器具有与表的列对应的内部状态，并且如果它“遵守”表中的指令，即当它正在扫描一个方块，上面出现一个符号 s1，并且处于，比如说，状态 B 时，它执行表中适当行和列的“指令”（在本例中，列 B 和行 s1）。任何由刚刚举例的机器表描述的机器都是图灵机。（普特南，1960/1975a，365；另见普特南，1967/1975a，433-4）
这个论述依赖于几个未解释的概念，比如方块（of tape），符号，扫描和执行指令。此外，这个论述是用 TM 表来具体说明的，但还有其他种类的计算描述。一个关于具体计算的一般性描述应该包括除了 TM 表之外的其他计算描述。也许出于这些原因，普特南（Putnam）——很快被许多其他人跟随——放弃了对方块、符号等的引用；他用对系统的物理描述来替代它们。这种替代的结果是戈德弗雷-史密斯（Godfrey-Smith）（2009）所称的“简单映射计算”论述。
根据简单映射理论，一个物理系统 S 执行一个由描述 C 定义的计算，只要 (i) 存在一个从物理描述赋予 S 的状态到计算描述 C 定义的状态的映射，使得 (ii) 物理状态之间的状态转换反映了计算状态之间的状态转换。因此，假设 S 有状态 p1 和 p2，它们分别映射到 C 的状态 s1 和 s2。条款 (ii) 要求，对于任何形式为 s1 → s2 的计算状态转换，当 S 进入状态 s1 时，它从 p1 转换到 p2。
上述公式的一个困难在于普通物理系统有不可数多个物理状态，而普通的计算描述，比如 TM 表，由可数多个状态组成。因此，计算状态不足以映射到物理状态。解决这个问题的一个方法是颠倒映射的方向，要求将计算状态映射到（物理状态的一个子集）。另一个更常见的解决方案是选择物理状态的一个子集或等价类，并将其映射到计算状态。当这样做时，条款（i）被以下内容取代：（i'）存在一种映射，从 S 的物理状态的一个子集（或等价类）到计算描述 C 的状态。
简单映射解释事实上非常宽松：它将许多计算归因于许多系统。在没有对可接受的映射进行限制的情况下，这样的映射相对容易获得。因此，一些人认为每个物理系统都实现了每个计算（普特南，1988 年，西尔，1992 年）。这个论点，将某物视为计算系统的主张变得毫无意义，将在第 3.1 节中讨论。与此同时，避免这种主张贬值的动机之一是其他关于具体计算的解释。
2.2 因果、反事实和倾向性解释
构建更为严格的计算描述的一种方法是进一步限制可接受的映射。作为提醒，简单映射描述认为，对于形式为 s1 → s2 的任何计算状态转换，如果系统处于将映射到 s1 的物理状态 p1，那么它将进入将映射到 s2 的物理状态 p2。第二部分(ii)是一个物质条件句。这种描述可以通过将其转化为表达支持反事实的关系的条件句来加强。
在一个纯粹的反事实解释中，通过要求物理状态转换支持某些反事实（Block 1978，Maudlin 1989，Copeland 1996，Rescorla 2014，Campbell 和 Yang 2021），从而加强了条款（ii）。换句话说，这种解释要求计算和物理描述之间的映射是这样的，即物理状态之间的反事实关系与计算状态之间的反事实关系同构。
不同的作者以略有不同的方式制定相关的反事实条件：(a) 如果系统处于映射到任意计算状态的物理状态（由相关的计算描述指定），它将进入映射到相关后续计算状态的物理状态（Maudlin 1989, 415）；(b) 如果系统处于映射到 s1 的物理状态 p1，它将进入映射到 s2 的物理状态 p2（Copeland 1996, 341）；(c) 如果系统处于映射到 s1 的物理状态 p1，它将进入映射到 s2 的物理状态 p2（Chalmers 1996, 312）。无论具体的制定方式如何，这些反事实条件都不满足在计算的简单映射解释中出现的第(ii)条款的材料条件。因此，反事实解释比简单映射解释更强大。
在因果解释中，第(ii)条款通过要求物理状态之间存在因果关系而得到加强：对于任何形式为 s1 → s2 的计算状态转换，物理状态 p1（映射到计算状态 s1）导致系统进入物理状态 p2（映射到计算状态 s2）（Chrisley 1995, Chalmers 1995, 1996, 2011, Scheutz 1999, 2001）。
为了避免无限的泛计算论（在第 3 节讨论），Chalmers（1995, 1996, 2011）增加了进一步的限制，即计算系统的物理实现必须分为单独的物理组件，每个组件映射到计算形式主义指定的组件。正如 Godfrey-Smith（2009, 293）所指出的，这种因果和定位约束的结合朝着机械解释（Machamer, Darden, and Craver 2000）的方向发展。基于机械解释的计算描述将在第 2.5 节讨论。目前，因果描述仅要求计算和物理描述之间的映射使得物理状态之间的因果关系与计算描述指定的状态转换同构。因此，根据因果描述，具体的计算是物理过程的因果结构。
另一个关于具体计算的描述涉及到倾向关系，假设（大多数人认为）倾向关系支持反事实论断。诉诸倾向可能比纯粹的反事实描述在阻止不受欢迎的计算实现方面具有优势（Klein 2008 年，第 145 页，支持倾向与反事实描述的案例）。
在一种倾向性解释中，通过要求物理状态之间存在倾向性关系来加强条款(ii)：对于形式为 s1 → s2 的计算状态转换（由计算描述指定），如果系统处于映射到 s1 的物理状态 p1，系统会表现出一种倾向性，其表现是从映射到 s2 的物理状态 p2 转换的过程（Klein 2008）。物理系统是这样的，即物理状态 p1（映射到计算状态 s1）表现出转换到物理状态 p2（映射到计算状态 s2）的倾向性。换句话说，倾向性解释要求计算和物理描述之间的映射是这样的，即物理状态之间的倾向性关系与计算描述指定的状态转换同构。因此，根据倾向性解释，具体的计算是物理过程的倾向性结构。
简单映射解释与反事实、因果和倾向性解释之间的区别可以通过查看一个例子来看到。
考虑一块在早晨阳光下的岩石。在任何时间间隔内，岩石的温度上升，从 T 到 T+1，再到 T+2，最后到 T+3。现在考虑一个将其输出馈送回自身的非门。首先，假设非门接收到 '0' 作为输入；然后它返回一个 '1'。在 '1' 被馈送回非门后，非门再次返回一个 '0'，如此往复。非门在输出 '0' 和输出 '1' 之间来回切换。现在将物理状态 T 和 T+2 映射到 '0'；然后将 T+1 和 T+3 映射到 '1'。
根据简单映射理论，这块岩石实现了一个进行计算的非门，其表示为“0101”。
相比之下，根据反事实解释，岩石所谓的计算实现是虚假的，因为物理状态转换不支持反事实。如果将岩石置于状态 T，它可能会或可能不会转换为 T+1，这取决于是早上还是晚上以及其他外部因素。由于岩石的物理状态转换与 NOT 门的计算状态转换不支持反事实，根据反事实解释，岩石不实现 NOT 门。
根据因果和倾向性解释，这种假设的计算实现是虚假的，因为物理状态转换并非是由岩石及其状态的因果或倾向性属性引起的。T 并不导致 T+1，岩石在 T 状态时也没有倾向进入 T+1 状态。相反，岩石改变其状态是由太阳的作用引起的。由于岩石的物理状态转换与 NOT 门的计算状态转换不是基于岩石及其状态的因果或倾向性属性，根据因果和倾向性解释，岩石并未实现 NOT 门。
需要注意的是，在所有这些映射描述下，任何物理系统与至少一些计算描述之间存在映射。因此，根据映射描述，一切至少执行一些计算（参见第 3.2 节）。这使一些人感到过于包容。在计算机科学和认知科学中，似乎存在着计算和不计算的系统之间的区别。为了保持这种区别，一个选择是超越实施的映射描述。
2.3 语义解释
在我们日常生活中，我们通常使用计算来处理有意义的符号，以从中提取信息。计算的语义学解释将这种实践转化为一种形而上学信条：计算是对表示的处理，或者至少是以适当方式处理适当的表示。关于哪些表示性操作构成计算的观点存在很大差异（Fodor 1975; Cummins 1983; Pylyshyn 1984; Churchland and Sejnowski 1992; Shagrir 2006, forthcoming）。语义学解释的所有版本共同之处在于，它们认真对待了普特南在计算的原始解释中对符号的引用：没有表示就没有计算（Fodor 1981, 180）。
语义学解释可以被视为对可接受映射施加了进一步限制。除了因果解释所施加的因果限制（对于反事实和倾向性解释也是如此），语义学解释还施加了语义限制。只有符合代表性的物理状态才能被映射到计算描述中，从而被视为计算状态。如果一个状态不具有代表性，那么它也不是计算状态。
语义学解释可能是心灵哲学中最受欢迎的，因为它似乎最符合对认知哲学解释所需的要求。由于通常假定心灵和数字计算机操纵（正确类型的）表征，它们最终被认为是在进行计算。由于通常假定大多数其他系统不操纵（相关类型的）表征，它们不进行计算。因此，语义学解释似乎能够容纳一些关于什么算作计算系统和什么不算的常见直觉。它将心灵和计算机纳入其中，同时将大多数其他事物排除在外，从而证明认知计算理论是一个强大且非平凡的理论。
语义学解释提出了三个重要问题。首先，如何对表示进行个体化？其次，什么被视为相关类型的表示？最后，是什么赋予表示它们的语义内容？
关于计算状态的个体化的主要辩论将内部主义者与外部主义者区分开来。根据外部主义者的观点，计算载体是通过其广泛的认知内容来个体化的符号——典型地，这些符号所代表的事物（Burge 1986，Shapiro 1997，Shagrir 2001）。相比之下，大多数内部主义者认为计算载体是通过狭义认知内容来个体化的符号（Segal 1991）。狭义内容粗略地说是以系统的内在属性来定义的语义内容。认知内容则是由认知心理理论赋予系统的内容。例如，视觉系统的认知内容是视觉内容，而听觉系统的认知内容是听觉内容。
为了阐明争议，考虑两个在物理上相同的认知系统 A 和 B。A 处理的符号中包括符号 S。每当 A 置身于水体之前、想到水、制定与水互动计划等情况下，A 会产生 S 的实例。简言之，符号 S 似乎代表水。每当 A 处理 S 时，系统 B 处理符号 S′，它在物理上与 S 相同。但系统 B 生活在与 A 环境不同的环境中。每当 A 被水包围时，B 被双子水包围，这是一种在外表上难以区分但在物理上不同于水的物质。因此，符号 S′似乎代表双子水（参见 Putnam，1975b）。总之，A 和 B 生活在相关不同的环境中，使得 S 似乎代表水，而 S′似乎代表双子水；A 处理 S 的方式与 B 处理 S′的方式相同；A 和 B 之间或 S 和 S′之间没有固有的物理差异。
根据外部主义者的观点，当 A 处理 S 而 B 处理 S'时，它们处于不同类型的计算状态。根据内部主义者的观点，A 和 B 处于相同类型的计算状态。换句话说，外部主义者认为计算状态在某种程度上是通过其参照物来个体化的，而参照物至少在一定程度上由系统外部的物理特性决定。相比之下，内部主义者认为计算状态的个体化方式完全取决于认知系统的内在物理特性。
迄今为止，外部主义者和内部主义者在一件事上达成一致：计算状态是由认知内容来区分的。这一要求可以放宽，而不放弃关于计算的语义解释。根据伊根（1999），计算载体并非由任何类型的认知内容来区分，无论是广义的还是狭义的。相反，它们是由它们的数学内容来区分的——也就是，通过系统的计算理论将数学函数和对象赋予计算载体的语义内容。由于数学内容在物理复制品之间是相同的，伊根认为她的数学内容是一种狭义内容——她是一种内部主义者。
让我们现在转向代表什么。这场辩论没有那么清晰。根据一些作者的观点，只有具有类似语言的组合句法的结构，支持组合语义的结构才算是计算载体，只有尊重这些结构的语义属性的操作才算是计算（Fodor，1975 年，Pylyshyn，1984 年）。这一建议与可计算性理论和类比计算（Maley 即将发表）相悖，这两者都不对计算载体的要求提出任何这样的要求。
其他作者对哪些表示上的操纵算作计算更具包容性，但他们在划分计算和非计算过程之间并不特别成功。很少有人会将所有表示的操纵都包括在内，比如绘画一幅图片或录制一段演讲，视为计算，但在哪里划定表示上的操纵算作计算和哪些不算作计算之间并没有共识。
第三个问题是什么赋予表征其语义内容。有三种观点。工具主义者认为，将语义内容归因于事物仅仅是启发式地用于预测和解释；语义属性不是计算状态的真实属性（例如，Dennett 1987，Egan 2010）。不是自然主义者的现实主义者认为语义属性是计算状态的真实属性，但它们不能简化为非语义属性。最后，既是现实主义者又是自然主义者的人认为语义属性既是真实的又可简化为非语义属性，尽管他们在如何简化它们上存在分歧（例如，Fodor 2008，Harman 1987）。
计算的语义学解释与计算是信息处理的共同观点密切相关。这个想法并不像看起来那么清晰，因为有几个相关的信息概念。信息处理与计算之间的联系取决于所涉及的信息概念。接下来是对计算是基于四个相关信息概念的信息处理的观点的简要澄清（参见 Piccinini 和 Scarantino 2011）。
在热力学意义上，信息与热力学熵密切相关。熵是每个物理系统的属性。热力学熵粗略地衡量了观察者在考虑系统的可观测宏观性质后对系统微观状态的不确定性。计算的热力学研究是一个充满活力的领域，对物理学基础有许多影响（Leff 和 Rex，2003）。在这种“信息”的热力学意义上，系统两个可区分状态之间的任何差异都可以说携带信息。从这个意义上说，计算可以说是信息处理，但这与语义学无关。然而，热力学、计算和信息理论之间的联系是认为每个物理系统都是计算系统观点的一种可能的启发源（见第 3.4 节）。
信息论中的信息是指特定事件发生的可能性的度量，而两个随机变量的互信息是变量之间相互依赖的度量（Shannon 和 Weaver，1949）。这些度量可以用来分析和设计能够在噪声存在的情况下可靠传输信号的强大通信系统。从这个意义上说，计算也可以说是信息处理。再次强调，这并不是明确讨论语义。但互信息可以告诉我们一个变量携带关于另一个变量的多少信息，因此互信息可能是关于一个变量携带的语义信息的概念的基础（参见 Isaac，2019）。
在一个语义意义上，信息大致等同于“自然含义”（Grice 1957）。一个信号在这个意义上携带信息，只要它与一个源头有可靠的相关性（Dretske 1981）。计算是以这种意义进行信息处理的观点初看似乎不太可信，因为许多计算——比如在数字计算机上进行的算术计算——似乎并不携带任何自然含义。然而，语义信息的这种概念在这里是相关的，因为一些理论家已经用它来建立一种表征的解释（Dretske 1981，Fodor 2008）。
在另一种语义意义上，信息只是普通的语义内容或“非自然含义”（Grice 1957）。这是大多数哲学家讨论的语义内容的一种。认为计算是以这种意义进行信息处理的观点类似于对计算的一般语义解释。
虽然计算的语义学解释似乎符合心灵哲学家的需求，但似乎不太适合解释其他科学。最重要的是，在认知科学的某些领域以及可计算性理论和计算机科学中使用的计算概念中，并不似乎预设了表示，而这些领域正是计算概念产生和计算认知理论产生的学科（Fresco 2010）。如果这是正确的，那么语义学解释甚至可能不足以满足心灵哲学家的需求，至少是那些希望理解心灵与计算机科学家和可计算性理论家设计和研究的系统之间类比的心灵哲学家。对语义学解释的另一个批评是，指定与计算相关的表示和表示操作的种类可能需要一种非语义的方式来区分计算（Piccinini 2004）。这些担忧促使人们努力以非语义术语解释计算。
2.4 句法解释
正如我们所看到的，语义学解释需要指定哪些表征与计算相关。一种观点是相关的表征类似于语言，即它们具有语言中句子所展示的句法结构。因此，计算是以一种对其句法结构敏感并保留其语义属性的方式操纵类似语言的表征（Fodor，1975）。
正如前一节讨论的那样，然而，在计算的描述中使用表示的概念涉及一些困难。如果可以在不诉诸表示的情况下解释计算，那些困难就会避免。一种方法是坚持认为计算只是通过操纵类似语言的结构的句法属性来进行的，从而避开语义。被操纵的结构被假定为类似语言仅仅是因为它们具有句法属性 - 它们不必具有任何语义。在这种计算的句法描述中，根本不使用表示的概念。
语义学解释试图通过对物理状态和计算状态之间可接受映射施加语义限制来解决实施问题；只有符合（正确类型的）表征的物理状态才能映射到计算状态上。相比之下，句法学解释可以被视为取代这种语义限制：只有符合句法要求的物理状态才能映射到计算状态上，从而被视为计算状态。如果一个状态缺乏句法结构，那么它就不是计算状态。
有待观察的是什么被视为句法状态。对于物理世界中句法的重要阐述归功于斯蒂芬·斯蒂奇（1983, 150–157）。尽管斯蒂奇没有使用“计算”这个术语，但他对句法的阐述旨在奠定心理状态和过程的句法阐述。斯蒂奇的心灵句法理论反过来是他对认知科学家提出的计算理论的解释，与福多的语义解释相竞争。由于斯蒂奇对句法的阐述最终旨在奠定认知的计算理论，斯蒂奇对句法的阐述也提供了（隐含的）计算的句法阐述。
根据斯蒂奇（Stich）的观点，粗略地说，当满足两个条件时，一个物理系统包含有句法结构化的对象。首先，系统的行为相关的物理状态与一类句法类型之间存在映射，这些句法类型由一个定义了如何从（有限多个）基本句法类型形成复杂句法类型的语法来指定。其次，系统的行为是由一个理论解释的，该理论的概括是以句法类型之间的形式关系来表述的，这些句法类型映射到系统的物理状态。
计算的句法解释并不十分流行。一个常见的反对意见是，似乎很难对原始句法类型进行解释，而不预设类型的先前语义个体化（Crane 1990，Jacquette 1991，Bontly 1998）。事实上，通常通过将句法解释为一种组合符号的方式来理解句法，即语义解释的组成部分。如果以这种方式解释句法，那么它就预设了语义。如果是这样，计算的句法解释就会崩溃成语义解释。
另一个反对意见是，像语言一样的句法结构并不是计算中必需的，就像在计算机科学和可计算性理论中理解的那样。尽管计算系统确实可以操作类似语言的结构，但它们并非必须如此。它们也可以操作简单的字母序列，而不会失去作为计算机的身份。（可计算性理论家称有限字母表中的任何一组词为一种语言，但这种广义的语言概念不应与 Stich 在他对计算的句法描述中所采用的受逻辑和语言学语法启发的更狭义概念混淆。）
2.5 机械化解释
这种机械论解释（Piccinini 2007, 2015; cf. Kaplan 2011, Milkowski 2013, Fresco 2014, Duwell 2017, Coelho Mollo 2018, Curtis-Trudel forthcoming-b）避免了对语法和语义的诉诸。相反，它以系统的机械特性来解释具体的计算。根据机械论解释，具体的计算系统是一种特殊类型的功能机制——执行具体计算的机制。
一个功能机制是一个有组织的组件系统，每个组件都有要执行的功能（参见 Craver 2012，Garson 2013）。当适当的组件及其功能得到适当组织并正常运作时，它们的综合活动构成了机制的能力。相反，当我们寻找一个机制能力的解释时，我们将机制分解为其组件，并寻找它们的功能和组织。结果是对机制能力的机械解释。
这种机制的概念对生物学家和工程师来说并不陌生。两者都会根据有组织的组件系统（例如消化系统和呼吸系统，或者记忆系统和处理器）执行的功能来解释所讨论系统的能力（例如生物学家的消化或呼吸，计算机工程师的内存访问或乘法）。
根据机械论解释，泛泛而言，计算是根据对车辆属性敏感的规则来处理车辆的过程，特别是对车辆不同部分之间的差异敏感。处理是由一个功能机制执行的，即，一个其组件被功能性地组织以执行计算的机制。因此，如果机制发生故障，就会发生错误计算。
数字计算、模拟计算等等原来都是通用计算的种类。它们通过被处理的载体的更具体属性来区分。如果一个计算系统处理离散状态的字符串，那么它执行数字计算。如果一个计算系统处理可以是连续的变量，那么它执行模拟计算（但请参见 Maley, forthcoming，以获取另一种解释）。如果一个计算系统处理量子位，那么它执行量子计算。
当我们定义具体的计算和它们操作的载体时，我们无需考虑它们所有的具体物理属性，而只需考虑那些与计算相关的属性，根据定义计算的规则。一个物理系统可以被描述得更抽象或更具体。根据机械主义的观点，对物理系统的抽象描述并不是对抽象对象的描述，而是对一个省略了某些细节的具体系统的描述。对具体计算及其载体的描述足够抽象，可以独立于在特定情况下实现它们的物理媒介而定义。因此，有时会说具体计算及其载体是“媒介无关”或“基质中立”的。
换句话说，一个车辆是中介无关的，只有在定义相关计算的规则（即输入-输出映射）对车辆的不同部分沿特定变化维度的差异敏感时，它们才是不敏感于车辆的任何更具体的物理属性。换句话说，这些规则是与一组功能相关的自由度相关的状态变量的函数，这些自由度可以在不同的物理媒介中以不同的方式实现。因此，一个给定的计算可以在多种物理媒介中实现（例如，机械、电机械、电子、磁性等），只要这些媒介具有足够数量的变化维度（或自由度），可以适当地访问和操作，并且机构的组件以适当的方式进行功能组织。
与语义和句法解释一样，机械解释旨在避免泛计算主义。首先，排除了不是功能机制的物理系统。功能机制是组件的复杂系统，这些组件被组织起来执行功能。任何其组件未被组织以执行功能的系统都不是计算系统，因为它不是功能机制。其次，排除了缺乏操纵介质无关载体功能的机制。最后，排除了操纵介质无关载体的操纵未符合适当规则的机制。第二和第三个约束涉及特殊的功能属性——操纵介质无关载体，并按照定义在这些载体上的规则进行操作——这些属性仅被相对较少的物理系统所拥有。根据机械解释，这些少数系统是真正的计算系统。
机械化解释的另一个特点是它解释了误计算的可能性——这在其他解释下很难理解。为了阐明这一点，考虑一个普通计算机，程序设计用于在输入 i 上计算函数 f。假设计算机发生故障，产生的输出与 f(i) 不同。根据因果（语义）解释，计算机只是经历了一个因果过程（一种表示的操作），这可以被给予一个计算描述，因此被视为计算某个函数 g(i)，其中 g ≠ f。相比之下，根据机械化解释，计算机只是未能计算，或者至少未能正确完成其计算。考虑到在计算机的设计和使用中避免误计算的重要性，机械化解释能够解释误计算可能是优于竞争对手解释的优势（Dewhurst 2018，Tucker 2018）。
机械化解释的最后一个特点是，它精确地区分和描述许多不同类型的计算系统，这些系统基于它们操作的特定载体和特定的机械特性。机械化解释已被用来阐明数字计算、模拟计算、神经网络计算以及其他重要区别，如硬连线 vs. 可编程和串行 vs. 并行计算（Piccinini，2015）。
3. 每个物理系统都是计算的吗？
哪些物理系统执行计算？根据泛计算论，它们都执行计算。即使是岩石、飓风和行星系统——与外表相反——都是计算系统。尽管这看起来有些违反直觉，但这种观点在一些哲学家和物理学家中相当流行。
3.1 全计算论的种类
计算普适主义的种类在两个维度上有所不同。首先，它们在每个系统上归因于多少计算方面有所不同——全部、许多、少数或仅一个。我们将其称为数量维度。其次，它们在为什么这些计算可归因于物理系统方面也有所不同。我们将其称为来源维度。
泛计算论在定量维度上的最弱版本是每个物理系统至少执行一次计算（Scheutz 2001）。这个版本可以称为有限泛计算论。
泛计算论的最强版本是每个物理系统执行每个计算，或者至少，每个足够复杂的系统实现非常多的非等价计算（Putnam 1988，Searle 1992）。这可以称为无限泛计算论。
一种声称的泛计算论的来源是系统执行的计算是相对自由解释的问题。如果系统执行的计算仅仅或主要取决于系统如何被解释，而不是客观事实，那么似乎一切都在计算，因为一切都可以被视为在计算（Searle 1992）。这可以被称为解释主义泛计算论。
另一个声称支持泛计算论的来源是，计算仅仅是物理过程的因果或动力学结构，正如计算的因果解释（第 2.2 节）所主张的（Chrisley 1995，Chalmers 1995，1996，Scheutz 1999，2001）。假设一切都具有因果结构，那么一切都会执行由其因果结构构成的计算。这可以称为因果泛计算论。
第三个声称的泛计算论的来源是每个物理状态携带信息的想法，结合信息为基础的语义和对计算语义观的自由版本。根据计算语义观，计算是对表示的操纵。根据信息为基础的语义，表示是携带信息的任何东西。假设每个物理状态携带信息，那么每个物理系统执行由其携带信息状态的操纵构成的计算（参见 Shagrir，2006）。
泛计算论的最终所谓来源是计算本身是物理宇宙的本质。一些物理学家认为，在其最基本的层面上，物理世界是计算的；有时这被形式化为“从位而生”的观点（Wheeler，1989）。我们将在第 3.4 节进一步讨论这一观点。
3.2 无限泛计算主义
支持无限泛计算论的论点可以追溯到 Hinckfuss 的水桶，这是对计算功能主义的一种假设反例——即心智是大脑的软件的观点。Hinckfuss 的水桶以其提倡者 Ian Hinckfuss 命名，但首次在印刷品中被 William Lycan 讨论。一桶水包含大量微观过程：
现在所有这些活动难道不够复杂，以至于仅仅偶然间，它可能在短暂时间内实现一个人类程序（假设某些微事件与程序的输入、输出和状态符号之间存在适当的相关性）吗？（Lycan 1981, 39）
Hinckfuss 对这个问题的暗示答案是，是的，一桶水可能会执行一个人类程序（或任意计算），至少在短时间内。
其他作者沿着 Hinckfuss 的思路发展出了更详细的论点。Searle (1992)明确指出，一个物理系统是否实现了一项计算取决于观察者如何解释这个系统；因此，对于任何足够复杂的对象和任何计算，都可以描述这个对象实现了这个计算。对于无限泛计算论的第一个严格论证归功于 Putnam (1988)，他认为每个普通的开放系统都实现了每个抽象的有限自动机（没有输入和输出）。
Putnam 考虑的是本质上是对第 2.2 节中岩石示例的一般化，该示例是一个简单有限自动机在没有输入或输出的情况下通过一系列计算状态转换的示例。一个经历（可能是连续的）物理转换的任意物理系统可以被离散化，使得它的物理状态映射到任意自动机的计算状态，从而将物理状态转换映射到计算状态转换。由于物理系统和自动机是任意的，每个物理系统都实现了每个有限自动机。
这个例子不包括输入和输出（这些对于计算解释可能是必要的），所以普特南引入了一个小改变，以允许具有输入和输出的自动机。这个想法是类似的，只是必须考虑物理状态（被视为输入和输出）与相关自动机的输入和输出之间的同构映射。这种限制导致一个更弱的结论：不是每个物理系统都实现每个有限自动机，而是任何给定的物理系统实现了可数无限个有限自动机（即那些产生正确输入/输出对的自动机）。这是因为，对于任意任意的输入/输出对 <i, o>，当给定输入 i 时，有可数无限多个自动机产生输出 o（详见普特南 1988 年的附录）。
如果无限泛计算论是正确的，那么系统 S 执行某种计算的主张就变得微不足道或几乎无意义；它未能区分 S 与其他任何事物（或者也许是与具有相同输入和输出的其他任何事物）。因此，无限泛计算论威胁到认知计算理论的实用性。如果认知是计算，仅仅因为认知系统，就像其他一切一样，可以被视为在相关输入上执行更多或更少任意的计算，那么认知计算理论似乎既是微不足道的又是无意义的（尽管请参阅 Schweizer 2019 年对抵制这一结论的尝试）。同样，无限泛计算论威胁到理论计算机科学与物理计算的相关性。例如，计算复杂度理论根据计算的复杂性对计算系统进行分类；如果任何物理系统都可以实现任何计算系统，而不考虑其计算复杂度，那么这些结果对具体计算是无关紧要的。这种微不足道的威胁是对应对无限泛计算论论据的主要动机。
值得注意的是，支持无限泛计算论的论点要么隐含地，要么明确地依赖于计算的简单映射解释。它们假设从计算描述 C 到系统的物理描述的任意映射足以得出结论，即系统实现了 C。事实上，避免无限泛计算论是拒绝简单映射计算解释的一个主要动机。通过对哪些映射是合法的施加限制，其他计算解释旨在避免无限泛计算论。
作为对无限泛计算论的一种回应，Copeland (1996) 认为，该论点所依赖的映射是不合法的，因为它们是事后构建的——在计算已经给出之后。在真正计算的情况下——通常在科学中使用的那种——生成系统物理动态的连续描述的工作是由运行适当程序的计算机完成的（例如，天气预报程序）；这正是首次使用计算机的目的。如果物理动态已经被知晓——这是事后计算描述所必需的——那么使用计算机就是不必要的。
此外，Chalmers (1995, 1996) 和 Copeland (1996) 都认为，无限泛计算论所援引的映射违反了计算状态之间的反事实关系，而这些关系是上述反事实映射理论所要求的。再考虑一下普特南的切片和聚合策略来生成映射。这些映射是基于任意物理系统的任意动力学演化构建的。并没有尝试去确定如果条件不同，物理系统会发生什么。Chalmers 和 Copeland 认为这是不合法的，因为真正的实现必须展现出计算状态之间存在的相同反事实关系。这一观点支持了计算的反事实映射理论。
对于无限泛计算论的其他回应指出，物理状态之间的转换并非具有因果关系。普特南依赖的计算描述映射到物理描述，使得计算描述并不描述物理系统的因果结构。根据一些作者的观点，非因果映射是不合法的（Chrisley 1995，Chalmers 1995，1996，2011，Scheutz 1999，2001）。这种类型的回应支持了计算的因果映射解释。
另一种对无限泛计算主义的回应隐含在戈德弗雷-史密斯（2009）的观点中。尽管戈德弗雷-史密斯主要关注的是功能主义而不是计算，但他的论点在这里仍然相关。戈德弗雷-史密斯认为，为了使映射构成真正的实现，被聚集在一起的微观物理状态（以对应于给定计算状态）必须在物理上相似——不能存在任意不同物理状态的任意分组，就像无限泛计算主义的论证中所述。戈德弗雷-史密斯建议，他对合法映射的相似性限制可能会被查尔默斯（1996）提出的因果和定位限制所补充。
计算的其他解释——语义、句法和机械解释——甚至比因果和反事实解释更为严格；它们对可接受的映射施加了进一步的限制。因此，与因果和反事实解释一样，它们有资源来避免无限的全计算论。
例如，考虑语义解释，根据该解释，计算需要表示。如果成为表示是相对少数事物所拥有的客观属性，那么基于仅构成表示的少数项目是真正的计算状态的理由，无限的全普适主义被排除在外。然而，如果一切以相关方式具有代表性，那么一切都是计算的（参见切奇兰和塞诺斯基 1992 年，沙格里尔 2006 年）。此外，如果某事物是否是表示是一种解释问题，那么计算的语义解释会导致全普适主义，因为对这些表示的解释是不受限制的。类似的考虑也适用于句法和机械解释。为了避免无限的全普适主义，这些解释必须不依赖于无限制的解释。
3.3 有限泛计算论
有限泛计算论比其无限表兄弟要弱得多。它认为每个物理系统执行一种（或相对较少的）计算。给定系统执行哪些计算被认为取决于该系统的客观属性。事实上，一些对无限泛计算论作出详细回应的作者明确支持有限泛计算论（查尔默斯，1996 年，331 页，舍茨，1999 年，191 页）。
与无限泛计算论不同，有限泛计算论并不使得某物是计算的主张变得无意义。不同系统通常具有不同的客观属性；因此，根据有限泛计算论，不同系统通常执行不同的计算。然而，有限泛计算论似乎仍然使得系统是计算的主张变得琐碎。因为根据有限泛计算论，数字计算机以与岩石、飓风和行星系统相同的意义执行计算。这似乎与计算机科学和工程以及认知计算理论相矛盾。如果每个物理过程都是一种计算，计算机科学将不得不将每个物理过程纳入其研究领域，而认知计算理论——部分受到认知是通过计算得到独特解释的想法的启发——将失去很大的解释力量。
另一个反对有限泛计算论的异议始于观察到任何中等复杂系统都满足无限多个客观计算描述（Piccinini 2010）。这可以通过考虑计算建模来看到。系统的计算模型可以以更高或更低的分辨率构建。例如，可以使用不同的状态转换规则、不同的时间步长、代表不同大小空间区域的不同状态数的细胞自动机模型描述星系或大脑的动态等。此外，还可以使用无限多种其他形式主义，如图灵机，来计算由细胞自动机计算的相同函数。有限泛计算论者似乎坚称星系或大脑同时执行所有这些计算。但这似乎不是计算机（或大脑）执行计算的方式。
面对这些异议，有限泛计算论者可能会坚持认为，计算解释的解释力并不来自于系统本身是计算的主张。相反，解释力来自于系统据称执行的具体计算。因此，虽然一块石头和一台数字计算机都执行计算，但它们执行根本不同的计算这一事实解释了它们之间的差异。至于有人提出的仍然有太多计算由每个系统执行的异议，有限泛计算论者有两个主要选择：要么硬着头皮接受每个系统实现无限多计算，要么找到一种方法，从每个系统满足的众多计算描述中单独出来那个本体上特权的描述——捕捉系统执行的计算的描述。其中一种方法是假设一个基本的物理层次，其最准确的计算描述确定了系统执行的（最基本的）计算。这种回应已经融入到物理世界基本上是计算的观点中（在下一节中探讨）。
那些希望避免有限的泛计算论的人会转向更为严格的计算描述，类似于希望避免无限泛计算论的动机促使从简单映射描述转向更为严格的计算描述，比如因果描述。语义描述可能能够将真正的计算描述限制在比因果描述更少的系统中，前提是根据语义描述，计算所需的表示很难获得。同样地，句法描述和机械描述也是如此。
3.4 宇宙作为一个计算系统
一些作者认为，物理宇宙从根本上是计算的。宇宙本身是一个计算系统；因此，其中的一切也是计算系统（或其一部分）。与源自哲学的先前版本的泛计算论不同，这种实体泛计算论源自物理学。它包括一个经验主张和一个形而上学主张。尽管这两个主张在逻辑上是独立的，但实体泛计算论的支持者倾向于同时提出它们。
经验性主张是，所有基本物理量及其状态转换都可以被适当的计算形式准确描述，而无需借助标准计算建模中常见的近似方法。这一主张的形式各异，取决于将哪种计算形式认为可以准确描述宇宙。主要的两种选择是元胞自动机，这是一种经典的计算形式，以及量子计算，这是非经典的。
本体泛计算论的最早和最著名版本归功于康拉德·祖斯（1970 年，1982 年）和爱德华·弗雷德金，他们关于这一主题的未发表观点影响了许多美国物理学家（例如，费曼 1982 年，托福利 1982 年，沃尔夫拉姆 2002 年；另请参见惠勒 1982 年，弗雷德金 1990 年）。根据一些物理学家的观点，宇宙实际上是一个巨大的元胞自动机。元胞自动机是一个离散单元格的点阵；每个单元格可以处于有限多个状态之一，并且每个单元格根据其相邻单元格的状态在离散步骤中更新其状态。为了使宇宙成为一个元胞自动机，所有基本物理量必须是离散的，即它们最多只能取有限多个值。此外，时间和空间必须在基本上是离散的，或者必须从元胞自动机的离散处理中产生。在基本层面上，连续性不是世界的真实特征——没有真正的实值物理量。这与大多数主流物理学相悖，但这并非显然错误的假设。假设是，在足够小的尺度上，目前超出我们的观测和实验范围，（表面上的）连续性让位于离散性。因此，所有基本变量的所有值，以及所有状态转换，都可以完全准确地由元胞自动机的状态和状态转换所捕捉。
虽然细胞自动机已被证明能描述基础物理的许多方面，但很难看出如何使用经典形式主义（如细胞自动机）来模拟宇宙的量子力学特征（Feynman，1982）。这一关注促使了量子计算形式主义的发展（Deutsch，1985；Nielsen 和 Chuang，2000）。量子计算不依赖于数字——最常见的是二进制数字或比特——而是依赖于 qudit——最常见的是二进制 qudit 或量子位。数字和 qudit 之间的主要区别在于，数字只能取有限多个状态之一，比如 0 和 1（比特的情况），而 qudit 还可以取无限多个状态，这些状态是基础状态的叠加，程度不同，比如 0 和 1 的叠加（量子位的情况）。此外，与一组数字不同，一组 qudit 可以表现出量子纠缠。根据本体泛计算论的量子版本，宇宙不是经典计算机，而是量子计算机——一种操作量子位（Lloyd，2006）或更一般地说，qudit 的计算机。
量子本体泛计算论的版本比经典版本更为温和。经典版本从宇宙中消除了连续性，主要基于这样的理由：消除连续性使得经典计算机能够精确描述宇宙而非近似描述。因此，经典版本似乎并非受到经验证据的驱动，而是受到认识论上的考虑。尽管没有直接证据支持经典本体泛计算论，但原则上它是一个可检验的假设（Fredkin，1990）。相比之下，量子本体泛计算论可以被视为在量子计算和量子信息理论（量子位）的语言中对量子力学进行重新表述，而不改变理论的经验内容（例如，Fuchs，2004 年，Bub，2005 年）。
但实体泛计算论者并不仅仅局限于提出经验性主张。他们经常提出额外的形而上学主张。他们声称，计算（或信息，在第 2.3 节中描述的物理意义上）构成了物理宇宙。有时会通过说，在最基本的物理层面上，状态之间存在着根本的差异—关于状态的本质无需或无法再说更多。这一观点颠倒了传统的计算与物理世界之间的关系观念。
根据上述讨论的所有计算的传统概念，物理计算需要物理媒介或基质。计算是物理系统的组织和行为的一个方面；没有硬件就没有软件。因此，根据传统概念，如果宇宙是一个元胞自动机，那么宇宙的最终组成部分就是元胞自动机的物理细胞。合理地问，这些细胞是什么样的物理实体，它们如何相互作用以满足它们的元胞自动机规则。
相比之下，根据实体全计算论的形而上学主张，一个物理系统只是一个计算状态系统。计算在本体论上优先于物理过程，可以说是“‘硬件’由‘软件’构成”（Kantor 1982, 526, 534），或者“它”（物理）来自“比特”（计算）（Wheeler 1989）。根据这种非传统的概念，如果宇宙是一个元胞自动机，那么自动机的细胞并不是具体的、物理的结构，彼此之间也没有因果关系。相反，它们是软件——纯粹的“计算”实体。
这样一个形而上学主张需要解释计算、软件或物理信息是什么。如果计算不是物理实体的配置，最明显的替代方案是认为计算是抽象的、数学的实体，就像数字和集合一样。正如 Wheeler（1982, 570）所说，“宇宙的构建元素是基本的‘是’或‘否’的量子现象。它是一个抽象实体。它不在空间和时间中定位”。根据这种计算的解释，本体泛计算论的本体论主张是毕达哥拉斯主义的一种版本。在这种意义上，一切都是计算，就像更传统的毕达哥拉斯主义版本维护一切都是数字或一切都是集合（Quine 1976）。
本体泛计算论在经验和本体两方面都可能受到质疑。在经验方面，几乎没有积极证据支持本体泛计算论。支持者似乎受到对世界精确计算模型的渴望的驱使，而不是实证证据证明这些模型是正确的。即使是怀有这种渴望的人，也很可能会质疑我们为什么应该期望自然来满足它。在形而上学方面，毕达哥拉斯主义面临的反对意见是，它将抽象实体置于基本物理层次上，这些实体缺乏我们在物理世界中观察到的因果和定性属性，或者至少很难理解抽象实体如何产生物理特性及其因果力量（例如，Martin 1997）。
4. 物理可计算性
根据哥德尔-图灵论题（CTT），任何直观可计算的函数都可以被某个图灵机（即图灵可计算）计算。另一种说法是，CTT 可以被表述为任何“自然可视为可计算”的函数都是图灵可计算的论题（图灵，1936-7，135）。短语“直观可计算”和“自然可视为可计算”有些模糊。当它们被消除歧义时，CTT 会呈现不同形式。
在某种意义上，“直观可计算”意味着通过遵循算法或有效程序来进行计算。有效程序是一系列清晰指令的有限列表，用于从旧的符号结构生成新的符号结构；一个例子是根据长除法算法，仅使用纸和铅笔来进行两个数字的除法。当 CTT 以有效程序的术语解释时，它可能被称为数学 CTT，因为相关证据更多地是逻辑或数学而非物理的。数学 CTT 表明，任何可以通过有效程序计算的函数都是图灵可计算的。
有令人信服的证据支持数学 CTT（Kleene 1952，§62，§67；另见 Sieg 2006）：
没有已知的反例。
对于图灵机的对角化，并不像人们可能期望的那样，产生一个不可图灵计算的函数。
收敛论证：提出的所有形式主义，旨在通过有效过程捕捉可计算性直觉概念的形式主义，如一般递归性（Gödel 1934）、λ-可定义性（Church 1932，Kleene 1935）、图灵可计算性（Turing 1936-7）和可计算性（Gödel 1936）都证明捕捉相同的函数类。
一台图灵机似乎能够在遵循有效程序的情况下复制人类可以执行的任何操作（图灵，1936-7 年对 CTT 的主要论点）。
在另一种意义上，“直观可计算”意味着可以通过物理手段计算。当 CTT 被这样解释时，它可以被称为物理 CTT（参考 Pitowsky 1990），因为相关证据更多地是物理的而不是逻辑的或数学的。
4.1 物理 Church-Turing 假设：大胆
物理计算理论经常以非常强烈的形式表达。初步近似地，大胆的物理计算理论认为，任何物理过程——任何物理系统可以执行的事情——都可以被某个图灵机计算。
粗体物理 CTT 可以通过多种方式变得更加精确。以下是一个代表性样本，后面列出了讨论它们的参考文献：
任何物理过程都可以通过某些 TM 进行模拟（例如，Deutsch 1985，Wolfram 1985，Pitowsky 2002）。
如果一个物理系统可以被某种理想化的计算机模拟，该计算机操作实值数量，那么该物理系统只能在可数域上计算图灵可计算函数（Blum 等人，1989 年表明这是错误的）。
任何描述物理系统的方程组都会产生可计算的解（参见 Earman 1986, Pour-El 1999）。只有在给定可计算的实数作为初始条件时，解才被称为可计算，它返回可计算的实数作为值（根据图灵的说法，实数之所以可计算，是因为存在一台图灵机，其输出可以产生该数字的任意数量的数字）。
对于任何物理系统 S 和可观测量 W，存在一个图灵可计算函数 f: N → N，使得对于所有时间 t ∈ N，f(t) = W(t)（Pitowsky 1990）。
论文（A）在模拟的两个概念之间存在歧义。在一种意义上，模拟是数字计算系统（如 TM）计算与另一个数字计算系统相同函数的过程。这是通用 TM 可以模拟任何其他 TM 的意义。如果使用这种第一种模拟概念解释（A），则意味着宇宙中的一切都是数字计算系统。这是（本体泛计算论）的一种变体（第 3.4 节）。
在另一种意义上，模拟是数字计算系统的输出代表另一个系统动态演化的近似描述的过程。这就是天气的计算模型模拟天气的意义。如果使用这种第二种模拟概念来解释（A），那么只有在我们不关心我们的计算近似有多接近时，（A）才是真实的。如果我们想要接近的计算近似——通常我们都想要——那么（A）就变成了这样一种说法：任何物理过程都可以在任何给定情况下以所需的精度进行计算近似。这是否成立因情况而异，取决于系统的动态特性、对它们了解多少、在模型中采用了什么理想化和简化、在计算中使用了什么数值方法，以及有多少计算资源（如时间、处理速度和内存）可用（Piccinini 2015，第 4 章）。
论文（B）被 Blum 等人（1989）展示为直接和根本错误。Blum 等人建立了一个关于实值数量的计算的数学理论，他们认为这是对普通可计算性理论的有益扩展。在这样的理论中，他们定义了理想化的“计算”机器，这些机器将加法、减法、乘法、除法和相等性测试作为对任意实值数量的原始操作。他们很容易地证明这样的机器可以通过将特征函数编码为实值常数来计算所有由可数域定义的集合（同上，405 页）。尽管他们没有将这一结果讨论为对物理 CTT 的反驳，但他们的工作经常在物理可计算性和物理 CTT 的讨论中被引用。
这些论点 (C) 和 (D) 具有有趣的反例，这些反例与一些物理理论一致 (参见下文和 Pour-El 1999)。这些理论上的反例可能会或可能不会出现在我们具体的物理宇宙中。
(A)–(D)中的每一个都提出了关于计算机科学、物理学和数学基础的重要问题。然而，目前尚不清楚这些命题中是否有任何一个与数学 CTT 有趣的类比。以下是两个原因。
首先，(A)–(D)被无法构建和用作计算设备的过程所证伪。最明显的例子是(B)。Blum 等人的结果相当于证明了所有可数域上的函数——包括那些图灵不可计算的不可数多个函数——都可以被 Blum 等人的“计算”系统计算，这些系统允许操作任意实数的精确值。因此，(B)是彻底错误的。但与此同时，这一结果没有直接的实际应用，因为没有证据表明具体的物理系统可以像 Blum 等人的系统那样操作任意实数值的数量。
更一般地说，由随机（即非确定性）物理过程生成的序列将使(A)–(D)的表述成为虚假。根据量子力学，一些物理过程——如原子衰变——包含客观随机元素。隐藏变量解释对此提出质疑，但真正随机性的可能性是足够合理的，应该予以考虑。
考虑一个在无限时间段内产生离散输出的随机过程，例如，来自放射性样本的原子衰变。在规则的时间间隔内，它的输出是一串数字——如果在一个时间间隔内没有原子衰变，则为“0”，如果在一个时间间隔内有一个或多个原子衰变，则为“1”。简单的考虑表明，以概率为一，我们的随机过程产生的序列是不可图灵计算的。有不可数无穷多个数字串（更强烈地说，有不可数无穷多个具有任何给定极限频率的“0”和“1”的数字串）。但是只有可数无穷多个图灵可计算的无穷数字串。因此，假设每个无穷数字串以相同的概率作为随机过程的结果出现，随机过程生成图灵可计算数字串的概率为零，而数字串不可图灵计算的概率为一（对于更强的结论，即没有这样的数字串是图灵可计算的，请参见 Calude＆Svozil 2008）。因此，仅仅通过使用真正的随机过程生成一个数字串，我们就有了超越图灵可计算的物理手段。正如图灵（1950，438–439）指出的那样，带有“随机元素”的机器可以比 TM 做得“更多”。但做更多并不等同于计算更多。与有时所暗示的相反（例如，Calude 2005，10），TM 和随机过程的组合并不威胁物理 CTT。
随机过程不应视为计算：与正规计算不同，随机过程的值不能根据定义成为函数的输出。当然，随机过程可以被计算利用——在计算的某些阶段依赖于随机或伪随机选择的重要计算技术。如果一些量子随机序列在算法信息理论意义上是随机的，它们甚至可能提高依赖随机选择的计算技术获得正确解决方案的概率（Calude 2005, 10）。但是，没有任何计算技术可以等同于一系列随机选择。因此，任何会被随机过程生成的序列证伪的论点，比如大胆物理 CTT，都过于强大，无法捕捉物理可计算性的概念——即算法可计算性的物理类比。因此，与一些作者似乎假设的相反，大胆物理 CTT 过于强大，无法成为数学 CTT 的物理类比。
这些论文（A）-（D）共同具有的另一个特征是，它们相当自由地吸引任意实数量。这在（B）中是明确的。要看到它们为什么都吸引任意实数量，考虑到大多数物理理论假设许多物理量，包括时间，可以取任意实数值。因此，物理方程组，其模拟、解决方案或可观测量分别被（A）、（C）和（D）所吸引，涉及任意实数。因此，所有粗体物理 CTT 的表述明确或隐含地涉及任意实数。
实数的表达能力可以用来生成一个简单的方法来获得一个图灵不可计算函数的值。考虑一个实数的数字展开包含可数多个数字。因此，对于定义在可数域上的特征函数（即，其值为'0'或'1'的函数），包括所有图灵不可计算的函数，存在一个实数，其二进制展开编码了其值。这是因为对于特征函数的所有值，函数的第 n 个值可以被定义为一个实数的二进制展开的第 n 个数字。
假设您希望了解特定的图灵不可计算特征函数的值，例如对于其第 n 个参数的停机函数。取实数 r，其数字展开编码了停机函数的值。然后，获取 r 的二进制展开中的第 n 位数字，您就得到了所需的结果。如果您能够做到这一点，您可以获得任何定义在字符串上的特征函数的值，包括所有图灵不可计算的这类函数。
以上的配方，如果可行的话，是实数表达能力的一个微不足道的结果。然而，它在文献中被讨论为可能超越图灵机能力的物理计算的一个例子（例如，Copeland 2000）——这将证伪物理计算理论。没有理由相信这样的配方可以被实现，因为它要求测量或准备图灵不可计算的实数值量，而且需要无限精度。没有证据表明这两者都是可行的。
通过相当自由地依赖任意实值数量，许多版本的大胆物理 CTT 使自己容易受到相对琐碎（尽管可能不可行）的反驳，比如刚提到的那种方法。这对一些试图证明大胆物理 CTT 的方法是数学 CTT 的有趣物理类比的假设产生了怀疑。
(刚刚提出的观点并不影响 Pour-El（1974）标准意义上的模拟计算。 模拟计算不是操作任意实值量的精确值，而是连续变量。 尽管在大多数模拟计算中使用的连续变量可以假定在相关区间内取任意实值，但具体的模拟计算只需要对实际变量进行某种程度的近似操作和测量。 因此，模拟计算并不证伪 Bold Physical CTT（参见 Rubel 1989）。)
关于数学 CTT 和粗体物理 CTT 之间所谓类比的疑问可能会引发一个相关观察。许多当前的物理理论假设自然包含沿着连续变化的实值量。这些量可能包括物体的速度、定义它们在时空流形中重心位置的坐标等。如果这些物理理论是正确的，那么许多实体的许多属性将以任意实数作为它们的值。在任何连续区间中，大多数实数都是图灵不可计算的（即只有可数多个可计算数，但任何连续区间包含不可数多个实数）。因此，任意实值量是可计算的概率为零。因此，如果我们的物理理论是正确的，那么相关物理属性的大多数转换都是将图灵不可计算的量转换为另一种量。
例如，一个物体速度的变化，甚至是其简单的空间位置变化，可能是一个图灵不可计算的实值量转化为另一个实值量。一个图灵不可计算值转化为另一个图灵不可计算值是一个图灵不可计算的操作——如果没有别的原因，因为没有图灵机可以写下这种操作的输入和输出。根据这个观点，物理世界充满了超越图灵机能力的操作，因此大胆的物理计算理论被证伪。
没有理由相信我们可以使用图灵不可计算的操作来进行计算，这些操作刚刚提到的操作无法在认识论意义上进行计算，这正是我们对计算感兴趣的原因——解决问题，为期望的参数生成期望函数的值，理解某些物理系统等。换句话说，所讨论的操作不应被视为计算。受到这些操作威胁的粗体物理 CTT 与数学 CTT 并不有趣地类似。
为了总结我们对 Bold Physical CTT 的讨论，区分物理可计算性问题——即与数学 CTT 的物理类比相关的问题，可能是有帮助的。许多关于物理过程与可计算性之间关系的问题都值得提出。什么是物理可计算函数？这个问题应该激发 Physical CTT。在什么情况下可以对什么程度进行计算近似？这可能是(A)所追求的。尽管这个问题同样重要且有趣，但它与可以在物理上计算的问题是不同的。其他问题也激发了上述论点(B)-(D)以及文献中其他版本的 Bold Physical CTT。许多这些问题很有趣，值得研究。然而，它们并不适合讨论 CTT，因为它们与最初激发 CTT 的可计算性问题不同。
4.2 物理 Church-Turing 假设：谦虚
在物理系统计算的文献中，越来越多的人担心数学 CTT 的物理类比应该只包括可用的物理过程（例如，Németi 和 Dávid 2006；Ord 2006，Smith 2006a，Beggs 和 Tucker 2007）。鉴于这种担忧，物理 CTT 的一个合适版本应该比大胆的物理 CTT 更为谦逊。
谦逊的物理计算理论因此是以可以在物理上计算的内容来制定的——更确切地说，可以在可数域上进行物理计算的函数是什么。物理计算的典型例子是普通数字计算机及其组件的过程，包括数字电路。这些过程可以通过有效的程序进行详尽描述，这些程序已经被数学计算理论所覆盖，再加上物理状态与计算状态之间相对无争议的映射。数学计算理论表明，任何可以通过有效程序计算的函数都可以通过图灵机计算。由于图灵机可以在物理上实现（或者被计算机人取代），任何遵循有效程序的过程都是可以在物理上计算的。
但是在当前意义上，物理计算的概念比有效过程计算更广泛。即使没有有效过程来描述过程，一个过程也可能被视为物理计算，也许是因为没有构成过程的内部状态的有限瞬时描述，或者没有办法有限地并确切地指定从一个瞬时描述到下一个的转换。因此，谦虚的物理 CTT 比数学 CTT 更强大。
Gandy (1980) 是最早讨论谦逊物理 CTT 版本之一，他认为具有离散组件和合理物理限制（组件尺寸的下限和运动速度的上限）的机制只能物理计算图灵可计算函数。然而，谦逊物理 CTT 不一定受到这些限制。除了遵循有效程序的物理过程外，谦逊物理 CTT 还可能涵盖连续动力过程（如某些类型的神经网络）、跨越大部分时空的过程以及量子过程（如量子计算）。但物理计算并不包括所有物理过程。
根据这一提议，谦虚的物理 CTT 认为，任何（可数域上的）物理可计算函数都是图灵可计算的。
对于一个过程被视为物理计算，并因此与谦逊物理 CTT 相关，观察者必须能够使用它来生成独立指定函数的期望值。这一要求可以用多个约束来阐明（Piccinini 2015，第 15 章和第 16 章）。这个列表并非旨在详尽无遗：
可读的输入和输出。该过程必须接受输入并产生观察者可以无误阅读的输出，以便观察者可以将输出用作问题的解决方案或在输入上定义的函数的值。为了实现这一点，很可能需要将输入和输出化简为离散状态的字符串，就像普通数字计算机的输入和输出一样。
过程无关规则。必须有一个固定的规则或映射——与物理过程无关——将输出与输入联系起来。通过定义过程要解决的问题，这个规则告诉用户通过运行过程将学到什么。由于规则通常定义了一般的物理计算，规则不必是递归的。例如，它可以是为图灵机定义停机问题的规则。但像所有递归规则一样，规则对于属于同一问题的所有输入必须是相同的；它不能从一个输入改变到下一个输入。
可重复性。该过程必须是可重复的，至少在原则上，以便用户能够多次获得相同的结果并通过重复计算来检查计算。
可设定性。正在进行过程的系统必须是可设定的，以便用户可以选择系统计算函数的哪个参数，并设置系统计算函数的相关值。
物理可构建性。该系统必须是物理可构建的。
可靠性。系统在流程完成之前不得发生故障。
总的来说，谦虚的物理 CTT 断言，每个可以在物理上计算的函数，即，根据在字符串上定义的与过程无关的规则将输入字符串转换为输出字符串的每个可用转换，都是图灯可计算的。
由于谦虚的物理计算理论受到认识论相关标准的限制，它不会引起与大胆的物理计算理论相关的担忧，即它太容易被证伪，与激发计算理论的可计算性概念无关。而且有充分的理由相信谦虚的物理计算理论。所有已经建造或正在建造的用于计算可数域函数的计算机制都只计算图灵可计算的函数。
理解谦虚物理 CTT 的确切范围非常重要。谦虚的物理 CTT 并不意味着每个物理过程都是一种计算，或者每个物理系统都是一个计算系统。它只是说，如果某物理事物计算可数域的函数，那么它所计算的函数是图灵可计算的。
为了充分评估谦虚物理 CTT，我们应该考虑是否可能构建一台机器，类似于普通的数字计算机，可以被人类观察者使用，但与普通的数字计算机不同，它生成的函数值是图灵不可计算的。近年来，已经提出了几种超计算的设计。超计算是计算图灵不可计算函数。如果超计算被证明在物理上是可能的，那将推翻谦虚物理 CTT。
4.3 超级计算
就第一次近似而言，超级计算机是一个能够产生图灵不可计算函数值的系统。如果未明确规定什么算是产生函数值，那么在第 4.1 节讨论的任何系统，比如真正随机过程和操纵任意实值量的系统，都可以被视为超级计算机。但在讨论 Bold Physical CTT 时，我们发现仅仅产生图灵不可计算函数值，并没有进一步的约束条件，这对于真正的物理计算来说是不够的。
类比于粗体物理 CTT 和谦虚物理 CTT 之间的区别，让我们通过区分可用的超计算机和不可用的超计算过程来区分超计算的弱和强概念。
一个无法使用的超计算过程是一个物理过程，它未能满足物理计算的前四个约束之一。例如，其输入或输出为任意实值量的过程（这些量无法用无限精度读取）和真正的随机过程（其输入和输出没有规则表征，独立于过程，并且既不可重复也不可设置）。这些过程是不可用的，因为观察者无法从中获得独立定义函数在选择的输入上的任意值，就像普通计算系统可以做到的那样（只要有足够的时间和空间）。由于它们不可用，无法使用的超计算过程与谦虚物理 CTT 无关。
一个可用的超级计算机是一个满足物理计算的至少前四个约束条件的物理系统。它具有可读的输入和输出，有一个描述其输入输出特性的规则，可以独立于过程本身定义，并且其过程是可重复和可设置的。如果一个系统不满足这些条件中的一个，那么它在与谦虚物理 CTT 相关的意义上不被视为计算。
一个满足这些条件的系统——一个可用的超级计算机——可能纯粹是概念上的。例如，无限加速的图灵机（Copeland 2002）是在每次计算操作中以前一次操作的一半时间执行的图灵机。因此，无限加速的图灵机在完成无限次操作（一个超任务）时，所需时间是执行第一次操作的两倍。这使得无限加速的图灵机能够计算图灵不可计算的函数，如停机函数。但通常将无限加速的图灵机讨论为概念实体，没有证据表明它们可以被构建。当然，纯粹概念的系统并不证伪谦逊的物理计算理论。要做到这一点，一个系统必须至少满足物理计算的第五和第六个约束：它必须是可以物理构建的，并且必须能够可靠运行。
构建类似于无限加速的图灵机的一种方法是制造一台计算机，经过一些计算操作后，构建一个更小更快的自身副本（Davies 2001）。这个更小更快的副本也会执行一些操作，然后构建一个更快更小的副本，依此类推。在适当的假设下，由此产生的一系列无限缩小的机器将能够在有限时间内完成无限次计算操作，从而超越图灵机的能力。尽管无限缩小的机器似乎与牛顿力学一致，但戴维斯（2001, 672）指出，我们宇宙中物质的原子和量子机械性质使得无限缩小的机器在物理上不可能。
神经网络有时被讨论为可能超越图灵可计算性的计算系统（例如，Smolensky，1988）。如果我们将注意力限制在包含所有具有当前或可预见实际应用的系统的神经网络类别上，这种观点是不合理的。现在有大量关于大类神经网络的计算和复杂性特性的文献。最相关的系统具有数字输入和输出（以满足我们对物理计算的第一个约束），但可能具有，通常也具有，非数字内部过程（即，它们的内部过程不是数字字符串的离散逐步操作）。主要结果如下：（i）具有有限处理单元的前馈网络在计算上等效于具有有限门的布尔电路；（ii）具有有限单元的递归网络等效于有限状态自动机；（iii）具有无限带或无限单元的网络等效于图灵机（Šíma＆Orponen，2003）。
神经网络可能比图灵机更强大，然而，可以通过再次利用实数的表达能力来定义。这类网络中最著名的是模拟循环神经网络（ARNNs）（Siegelmann 1999）。ARNNs 不应与传统意义上的模拟计算机混淆（Pour-El 1974，Rubel 1993，Mills 2008）。而模拟计算机操作实数变量，而不依赖于任意实值量的精确值，ARNNs 通过操作数字串（可能）依赖于任意实值量的精确值。具体而言，ARNNs 内部连接的权重可以取任意实数的精确值，包括图灵不可计算的值，并且这些精确值在计算中被利用。当它们的权重是图灵不可计算的时，ARNNs 可以超越图灵机的能力：它们可以计算二进制串上的任何函数。比图灵机更强大的 ARNNs 无法可靠运行，因为它们需要无限精确的权重。此外，所需的权重是图灵不可计算的，因此构建比图灵机更强大的 ARNNs 需要已经具备执行超计算的能力（Davis 2004，Schonbein 2005，Siegelmann 1999，148）。
也许最著名的超级计算机提议归功于马克·霍加斯（1994 年，2004 年），他发展了伊塔马尔·皮托夫斯基（1990 年）的一个想法。相对论性超级计算机利用了一种特殊类型的时空，称为马拉门特-霍加斯时空，从物理上讲，这种时空构成了爱因斯坦广义相对论场方程的解。马拉门特-霍加斯时空包含具有无限时间轨迹 λ 的区域，可以被有限时间轨迹 γ 绕过。换句话说，λ 和 γ 有一个共同的起源，并且在 γ 上有一个时空点 p，使得 λ，尽管是无限的，完全位于 p 的时间过去。如果观察者沿着 λ 发射 TM，然后沿着 γ 行进，她可能在有限时间内发现自己处于 TM 执行的无限长计算的未来。如果 TM 能够向观察者发送信号，观察者将能够知道潜在无限长计算的结果，从而具有比（普通）TM 更强大的计算手段。例如，观察者可能能够获得 TM 的停机函数的任意实例的结果。
构建和使用相对论超级计算机是具有挑战性的。第一个问题是我们的时空是否是 Malament-Hogarth。答案目前尚不清楚。即使我们的时空在全局范围内不是 Malament-Hogarth，它仍然可能包含在局部具有 Malament-Hogarth 属性的区域。这样一个区域的例子是一个巨大的旋转黑洞；有证据表明我们的宇宙包含这样的黑洞（Etesi 和 Németi，2002）。但即使在我们的宇宙中存在 Malament-Hogarth 区域，仍然存在相当大的障碍。首先，（i）离我们最近的巨大旋转黑洞可能超出我们的能力范围以及我们后代的能力范围，（ii）完成无限计算需要无界内存，这可能需要无限量的物质，（iii）需要无限量的物质运行无限时间的机器将以概率 1 发生故障，使其变得无用（Button，2009，779）。后一挑战可能可以通过使用多个相互检查计算而不是单个机器的自我复制和自我校正机器来解决（Andréka 等，2018），尽管这似乎加剧了对无限资源的需求（另请参见 Németi 和 Dávid，2006 年，Andréka，Németi 和 Németi，2009 年）。
量子计算也被提及作为超计算的可能来源。量子计算是根据量子力学的定律操纵量子比特（更一般地说，量子位）。量子比特是变量，类似于比特，可以准备或测量为一种或两种状态，0 和 1。与比特不同，量子比特可以（i）处于 0 和 1 的叠加状态，并且（ii）在计算过程中彼此纠缠。量子计算的一个令人惊讶的特征是，它允许比任何已知的经典计算更快地计算某些函数（Shor，1994）。但是，尽管主流量子计算可能比经典计算更有效率，但它并不允许计算超出图灵机可计算的任何函数。
一些作者质疑主流量子计算范式是否足够普遍，如果不够，是否可以利用量子力学的某些方面来设计量子超级计算机（Nielsen 1997，Calude 和 Pavlov 2002）。最著名的量子超级计算机提议来自 Tien Kieu（2002，2003，2004，2005）。他认为，一个适当构建的量子系统可以决定任意丢番图方程是否有整数解——这是一个已知无法通过图灵机解决的问题。Kieu 的方法涉及将问题的特定实例编码到适当的哈密顿量中，该哈密顿量代表量子系统的总能量。Kieu 表明，这样的系统可以随时间动态演化为编码所需解的能量基态。不幸的是，Kieu 的方案似乎不可行。首先，它需要在设置和维护系统时具有无限精度（Hodges 2005）。另外，Kieu 没有提供一个成功的标准来判断系统何时演化为解状态，确定解状态何时达到的问题是图灵不可计算的（Smith 2006b，Hagar 和 Korolev 2007）。因此，操作 Kieu 提出的超级计算机将需要已经拥有超级计算能力。
总之，迄今为止提出的候选超级计算机尚未被证明是可以物理构建和可靠的。目前而言，谦逊的物理计算理论仍然是可信的。很可能，对于所有实际目的而言，任何可以物理计算的函数都是图灵可计算的。
Bibliography
Aaronson, S., 2003, “Is P Versus NP Formally Independent?” Bulletin of the EATCS, 81: 109–136.
–––, 2005, “NP-complete problems and physical reality,” ACM Sigact News, 36(1): 30–52.
–––, 2013a, Quantum Computing Since Democritus, Cambridge, England: Cambridge University Press.
–––, 2013b, “Why Philosophers Should Care About Computational Complexity,” in J. Copeland, C. Posy, & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond, pp. 261–328, Cambridge, Massachusetts: MIT Press.
Ackermann, W., 1928, “Über die Erfüllbarkeit gewisser Zählausdrücke,” Mathematische Annalen, 100(1): 638–649.
Agrawal, M., Kayal, N., and Saxena, N., 2004, “PRIMES in P,” Annals of Mathematics. Second Series, 160(2): 781–793.
Allender, E., and McCartin, C., 2000, “Basic Complexity,” in R. Downey & D. Hirschfeldt (eds.), Aspects of Complexity, pp. 1–28, Berlin: Walter de Gruyter.
Arora, S., and Barak, B., 2009, Computational Complexity: A Modern Approach, Cambridge, England: Cambridge University Press.
Artemov, S., and Kuznets, R., 2014, “Logical Omniscience as infeasibility,” Annals of Pure and Applied Logic, 165: 6–25.
Baker, T., Gill, J., and Solovay, S., 1975, “Relativizations of the P=NP? question,” SIAM Journal on Computing, 4(4): 431–442.
Balcázar, J., Diaz, J., and Gabarró, J., 1988, Structural Complexity Vol. I, Berlin: Springer Verlag.
Bellantoni, S., and Cook, S., 1992, “A new recursion-theoretic characterization of the polytime functions,” Computational Complexity, 2(2): 97–110.
Bellman, R., 1962, “Dynamic Programming Treatment of the Travelling Salesman Problem,” Journal of the ACM, 9: 61–63.
Ben-David, S., and Halevi, S., 1992, On the Independence of P Versus NP (No. 714), Technion.
Bennett, J., 1962, On Spectra (PhD thesis), Princeton.
Bernays, P., 1935, “Sur Le Platonisme Dans Les Mathématiques.” L’enseignement Mathematique, 34: 52–69.
Bernays, P., and Schönfinkel, M., 1928, “Zum Entscheidungsproblem der Mathematischen Logik,” Mathematische Annalen, 99(1): 342–372.
Bonet, M., Buss, S., and Pitassi, T., 1995, “Are there hard examples for Frege systems?” in Feasible Mathematics II, pp. 30–56, Berlin: Springer.
Brookshear, J., Smith, D., Brylow, D., Mukherjee, S., and Bhattacharjee, A., 2006, Computer Science: An Overview 9th ed., Boston: Addison-Wesley.
Buss, S., 1986, Bounded Arithmetic, Naples: Bibliopolis.
–––, 1987, “The Boolean formula value problem is in ALOGTIME,” in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 123–131.
–––, 1999, “Propositional Proof Complexity an Introduction,” in Computational Logic, pp. 127–178, Springer.
–––, 2012, “Towards NP–P via Proof Complexity and Search,” Annals of Pure and Applied Logic, 163(7): 906–917.
Carbone, A., and Semmes, S., 1997, “Making Proofs Without Modus Ponens: An Introduction to the Combinatorics and Complexity of Cut Elimination,” Bulletin of the American Mathematical Society, 34(2): 131–159.
Chagrov, A., 1985, “On the Complexity of Propositional Logics,” in Complexity Problems in Mathematical Logic, pp. 80–90, Kalinin: Kalinin State University.
Chandra, A., and Stockmeyer, L., 1976, “Alternation,” in 17th Annual Symposium on Foundations of Computer Science, 1976, pp. 98–108.
Chazelle, B., and Monier, L., 1983, “Unbounded hardware is equivalent to deterministic Turing machines,” Theoretical Computer Science, 24(2): 123–130.
Cherniak, C., 1981, “Feasible Inferences,” Philosophy of Science, 48: 248–268.
–––, 1984, “Computational Complexity and the Universal Acceptance of Logic,” The Journal of Philosophy, 81(12): 739–758.
–––, 1986, Minimal Rationality, Cambridge, Massachusetts: MIT Press.
Chernoff, H., 1981, “A Note on an Inequality Involving the Normal Distribution,” The Annals of Probability, 9: 533–535.
Cherubin, R., and Mannucci, M., 2011, “A Very Short History of Ultrafinitism,” in Juliette Kennedy & Roman Kossak (eds.), Set Theory, Arithmetic, and Foundations of Mathematics: Theorems, Philosophies, Vol. 36, pp. 180–199, Cambridge, England: Cambridge University Press.
Church, A., 1936a, “A note on the Entscheidungsproblem,” The Journal of Symbolic Logic, 1(01): 40–41.
–––, 1936b, “An unsolvable problem of elementary number theory,” American Journal of Mathematics, 58(2): 345–363.
Clarke, E., Emerson, E., and Sistla, A., 1986, “Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications,” ACM Transactions on Programming Languages and Systems, 8(2): 244–263.
Cobham, A., 1965, “The Intrinsic Computational Difficulty of Functions,“ Proceedings of the Third International Congress for Logic, Methodology and Philosophy of Science, Amsterdam, North-Holland.
Cook, S., 1971, “The complexity of theorem-proving procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM.
–––, 1973, “A hierarchy for nondeterministic time complexity,“ Journal of Computer System Science, 7(4):343–353.
–––, 2006, “The P versus NP problem,” in J. Carlson, A. Jaffe, & A. Wiles (eds.), The Millennium Prize Problem, pp. 88–104, Providence: American Mathematical Society.
Cook, S., and Kolokolova, A., 2001, “A second-order system for polytime reasoning using Gradel’s theorem,” in Logic in Computer Science, 2001. Proceedings. 16th Annual IEEE Symposium on, pp. 177–186.
Cook, S., and Mitchell, D., 1997, “Finding Hard Instances of the Satisfiability Problem,” in Satisfiability Problem: Theory and Applications: DIMACS Workshop, March 11-13, 1996, Vol. 35, pp. 1–17, American Mathematical Soc.
Cook, S., and Nguyen, P., 2010, Logical foundations of proof complexity, Cambridge, England: Cambridge University Press.
Cook, S., and Reckhow, R., 1973, “Time bounded random access machines,” Journal of Computer and System Sciences, 7(4): 354–375.
–––, 1979, “The Relative Efficiency of Propositional Proof Systems,” The Journal of Symbolic Logic, 44(01): 36–50.
Cook, W., 2012, In pursuit of the Traveling Salesman: mathematics at the limits of computation, Princeton: Princeton University Press.
Cormen, T., Leiserson, C., and Rivest, R., 2005, Introduction to Algorithms (Second Ed.), Cambridge, Massachusetts: MIT Press.
Crandall, R., and Pomerance, C., 2005, Prime Numbers (Second Ed.), Berlin: Springer.
Davis, Martin, and Putnam, Hilary, 1960, “A Computing Procedure for Quantification Theory,” Journal of the ACM (JACM), 7(3): 201–215.
DeMillo, R., and Lipton, R., 1980, “The consistency of P=NP and related problems with fragments of number theory,” in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 45–57, ACM.
Deutsch, D., 1985, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818): 97–117.
Du, D., and Ko, K., 2000, Theory of Computational Complexity, New York: John Wiley.
Dummett, M., 1975, “Wang’s Paradox,” Synthese, 30(3/4): 301–324.
Ebbinghaus, Heinz-Dieter, and Flum, Jörg, 1999, Finite Model Theory (Second Ed.), Berlin: Springer.
Edmonds, J., 1965a, “Minimum Partition of a Matroid into Independent Subsets,” Journal of Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics, 69: 67–72.
–––, 1965b, “Paths, trees, and flowers,” Canadian Journal of Mathematics, 17(3): 449–467.
Emde Boas, P. van, 1990, “Machine models and simulations,” in J. Van Leeuwen (ed.), Handbook of theoretical computer science (vol. A): algorithms and complexity, pp. 1–66, Cambridge, Massachusetts: MIT Press.
Emerson, E., and Jutla, C., 1988, “The Complexity of Tree Automata and Logics of Programs,” in 29th Annual Symposium on Foundations of Computer Science, 1988., pp. 328–337.
Fagin, R., 1974, “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,” in R. Karp (ed.), Complexity of Computation: SIAM-AMS Proceedings, Vol. 7, pp. 27–41.
Fagin, R., and Halpern, J., 1988, “Belief, Awareness, and Limited Reasoning,” Artificial Intelligence, 34(1): 39–76.
Fagin, R., Halpern, J., Moses, Y., and Vardi, M., 1995, Reasoning About Knowledge, Cambridge, Massachusetts: MIT Press.
Feynman, R., 1982, “Simulating Physics with Computers,” International Journal of Theoretical Physics, 21(6): 467–488.
Fischer, M., and Ladner, R., 1979, “Propositional Dynamic Logic of Regular Programs,” Journal of Computer and System Sciences, 18(2): 194–211.
Fischer, M., and Rabin, M., 1974, “Super-exponential complexity of Presburger arithmetic,” in R.M. Karp (ed.), Complexity of Computation, Vols. SIAM-AMS Symposium in Applied Mathematics, pp. 122–135.
Fortnow, L., 2003, “One Complexity Theorist’s View of Quantum Computing,” Theoretical Computer Science, 292(3): 597–610.
–––, 2009, “The status of the P versus NP problem,” Communications of the ACM, 52(9): 78–86.
–––, 2013, Golden Ticket: P, NP, and the Search for the Impossible, Princeton: Princeton University Press.
Fortnow, L., and Homer, S., 2003, “A short history of computational complexity,” Bulletin of the EATCS, 80: 95–133.
Fraenkel, A., and Lichtenstein, D., 1981, “Computing a perfect strategy for n×n chess requires time exponential in n,” Journal of Combinatorial Theory, Series A, 31(2): 199–214.
Gaifman, H., 2010, “Vagueness, tolerance and contextual logic,” Synthese, 174: 1–42.
Gaifman, Haim, 2012, “On Ontology and Realism in Mathematics,” Review of Symbolic Logic, 5(3): 480–512.
Gandy, R., 1980, “Church’s Thesis and principles for mechanisms,” in H.J. Keisler J. Barwise & K. Kunen (eds.), The Kleene Symposium, Vol. 101, pp. 123–148, Amsterdam: North-Holland.
Ganea, M., 2014, “Finitistic Arithmetic and Classical Logic,” Philosophia Mathematica, 22: 167–197.
Garey, M., and Johnson, D., 1979, Computers and intractability. A guide to the theory of NP-completeness, New York: W.H. Freeman; Company.
Gigerenzer, G., and Selten, R., 2002, Bounded Rationality: The Adaptive Toolbox, Cambridge, Massachusetts: MIT Press.
Goldreich, O., 2010, P, NP, and NP-completeness: The basics of computational complexity, Cambridge, England: Cambridge University Press.
Gödel, K., 1932, “Ein Spezialfall des Entscheidungsproblems der theoretischen Logik,” Ergebnisse Eines Mathematischen Kolloquiums, 2: 27–28.
–––, 1986a, “On Intuitionistic Arithmetic and Number Theory,” in S. Feferman (ed.), Collected Works Volume 1, pp. 287–295, New York: Oxford University Press.
–––, 1986b, “On undecidable propositions of formal mathematical systems (with postscript dated 1964),” in S. Feferman (ed.), Kurt Gödel Collected Works. Vol. I. Publications 1929-1936, pp. 346–371, New York: Oxford University Press.
Gödel, Kurt, 1956, “Letter to von Neumann (1956),” Reprinted in Sipser 1992, p. 612.
Greenlaw, R., Hoover, H., and Ruzzo, W., 1995, Limits to parallel computation: P-completeness theory, New York: Oxford University Press, USA.
Grover, L., 1996, “A Fast Quantum Mechanical Algorithm for Database Search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219, ACM.
Gutin, G., and Punnen, A., 2002, The Traveling Salesman Problem and Its Variations Vol. 12, New York: Kluwer.
Haken, A., 1985, “The Intractability of Resolution,” Theoretical Computer Science, 39: 297–308.
Halpern, J., and Moses, Y., 1992, “A Guide to Completeness and Complexity for Modal Logics of Knowledge and Belief,” Artificial Intelligence, 54(3): 319–379.
Harel, D., 2006, Algorithmics: The Spirit of Computing, Boston: Addison-Wesley.
Harman, G., 1986, Change in View: Principles of Reasoning., Cambridge, Massachusetts: Cambridge University Press.
Hartmanis, J., 1993, “Gödel, von Neumann and the P=NP? Problem,” in G., Rozenberg, & A. Salomaa (eds.), Current Trends in Theoretical Computer Science, pp. 445–450, Singapore: World Scientific.
Hartmanis, J., and Stearns, R., 1965, “On the computational complexity of algorithms,” Transactions of the American Mathematical Society, 117(5): 285–306.
Hájek, P., and Pudlák, P., 1998, Metamathematics of First-Order Arithmetic, Berlin: Springer.
Hemaspaandra, L., and Ogihara, M., 2002, The Complexity Theory Companion, Berlin: Springer Verlag.
Hintikka, J., 1962, Knowledge and Belief: An Introduction to the Logic of the Two Notions, Ithaca: Cornell University Press.
Homer, S., and Selman, A., 2011, Turing and the Development of Computational Complexity (No. 2011-06), SUNY Buffalo Department of Computer Science.
Hopcroft, J., and Ulman, J., 1979, Introduction to Automata Theory, Languages and Computation, Reading, Massachusetts: Addison-Wesley.
Immerman, N., 1982, “Relational Queries Computable in Polynomial Time,” in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 147–152, ACM.
–––, 1987, “Languages That Capture Complexity Classes,” SIAM Journal on Computing, 16(4): 760–778.
–––, 1999, Descriptive Complexity, New York: Springer Verlag.
Impagliazzo, R., 1995, “A personal view of average-case complexity,” in Structure in Complexity Theory, Proceedings of Tenth Annual IEEE Conference, pp. 134–147.
Impagliazzo, R., and Paturi, R., 1999, “Complexity of k-SAT,” in Computational Complexity, 1999. Proceedings. Fourteenth Annual IEEE Conference, pp. 237–240.
Isles, D., 1992, “What evidence is there that 265536 is a natural number?” Notre Dame Journal of Formal Logic, 33(4).
Iwan, S., 2000, “On the Untenability of Nelson’s Predicativism,” Erkenntnis, 53(1-2): 147–154.
Kahneman, D., 2003, “A Perspective on Judgment and Choice: Mapping Bounded Rationality.” American Psychologist, 58(9): 697–720.
Kanovich, M., 1994, “The complexity of Horn fragments of linear logic,” Annals of Pure and Applied Logic, 69(2): 195–241.
Kapovich, I., Myasnikov, A., Schupp, P., and Shpilrain, V., 2003, “Generic-Case Complexity, Decision Problems in Group Theory, and Random Walks,” Journal of Algebra, 264(2): 665–694.
Karp, R., 1972, “Reducibility Among Combinatorial Problems,” in R.E. Miller & J.W. Thatcher (eds.), Complexity of computer computations, pp. 85–103, New York: Plenum Press.
Kaye, R., 2000, “Minesweeper is NP-complete,” The Mathematical Intelligencer, 22(2): 9–15.
Kent, C., and Hodgson, B., 1982, “An arithmetical characterization of NP,” Theoretical Computer Science, 21(3): 255–267.
Kleene, S., 1936, “General recursive functions of natural numbers,” Mathematische Annalen, 112(1): 727–742.
–––, 1951, Representation of Events in Nerve Nets and Finite Automata (No. RM-704), RAND Corporation.
–––, 1952, Introduction to Metamathematics Vol. 1, Amsterdam: North-Holland.
Knuth, D., 1973, The Art of Computer Programming Vols. I–III, Reading, Massachusetts: Addison Wesley.
Kozen, D., and Parikh, R., 1981, “An elementary proof of the completeness of PDL,” Theoretical Computer Science, 14(1): 113–118.
Kuznets, R., 2000, “On the Complexity of Explicit Modal Logics,” in Computer Science Logic, pp. 371–383, Springer.
Ladner, R., 1975, “On the Structure of Polynomial Time Reducibility,” Journal of the ACM, 22(1): 155–171.
–––, 1977, “The Computational Complexity of Provability in Systems of Modal Propositional Logic,” SIAM Journal on Computing, 6(3): 467–480.
Lange, M., 2006, “Model Checking Propositional Dynamic Logic with All Extras,” Journal of Applied Logic, 4(1): 39–49.
Lautemann, C., 1983, “BPP and the polynomial hierarchy,” Information Processing Letters, 17(4): 215–217.
Leivant, D., 1994, “A Foundational Delineation of Poly-Time,” Information and Computation, 110(2): 391–420.
Lenzen, W., 1978, “Recent Work in Epistemic Logic,” Acta Philosophica Fennica, 30: 1–219.
Levesque, H., 1984, “A Logic of Implicit and Explicit Belief,” in Proceedings of the Fourth National Conference on Artificial Intelligence (AAAI-84), pp. 198–202.
Levin, L., 1973, “Universal sorting problems (Corrected Translation Published in Trakhtenbrot 1984),” Problems of Information Transmission, 9(3): 265–266.
Lewis, H., 1980, “Complexity Results for Classes of Quantificational Formulas,” Journal of Computer and System Sciences, 21(3): 317–353.
Lewis, H., and Papadimitriou, C., 1998, Elements of the Theory of Computation, Upper Saddle River, New Jersey: Prentice Hall.
Li, M., and Vitányi, P., 1997, An Introduction to Kolmogorov Complexity and Its Applications (Second Ed.), New York: Springer.
Lichtenstein, D., and Sipser, M., 1980, “Go is polynomial-space hard,” Journal of the ACM, 27(2): 393–401.
Lincoln, P., 1995, “Deciding Provability of Linear Logic Formulas,” in Proceedings of the Workshop on Advances in Linear Logic, pp. 109–122, New York: Cambridge University Press.
Lincoln, P., Mitchell, J., Scedrov, A., and Shankar, N., 1992, “Decision Problems for Propositional Linear Logic,” Annals of Pure and Applied Logic, 56(1): 239–311.
Lipton, R., and Regan, K., 2013, People, Problems, and Proofs, Berlin: Springer.
Löwenheim, L., 1967, “On Possibilities in the Calculus of Relatives (1915),” in van Heijenoort (ed.), From Frege to Gödel : A Source Book in Mathematical Logic, 1879-1931, pp. 232–251, Cambridge, Massachusetts: Harvard University Press.
Magidor, O., 2011, “Strict Finitism and the Happy Sorites,” Journal of Philosophical Logic, 41: 1–21.
Manders, K. L., and Adleman, L., 1978, “NP-complete decision problems for binary quadratics,” Journal of Computer and System Sciences, 16(2): 168–184.
Manin, Y., 1980, Computable and Uncomputable, Moscow: Sovetskoye Radio.
Marx, M., 2007, “Complexity of Modal Logic,” in P. Blackburn, J. van Benthem, & F. Wolter (eds.), Handbook of Modal Logic, pp. 140–179, Amsterdam: Elsevier.
Mermin, N., 2007, Quantum Computer Science: An Introduction, Cambridge, England: Cambridge University Press.
Miller, G., 1976, “Riemann’s Hypothesis and Tests for Primality,” Journal of Computer and System Sciences, 13(3): 300–317.
Milnikel, R., 2007, “Derivability in certain subsystems of the Logic of Proofs is ΠP2-complete,” Annals of Pure and Applied Logic, 145(3): 223–239.
Moore, C., and Mertens, S., 2011, The Nature of Computation, Oxford: Oxford University Press.
Morton, A., 2004, “Epistemic Virtues, Metavirtues, and Computational Complexity,” Noûs, 38(3): 481–502.
–––, 2012, Bounded Thinking: Intellectual Virtues for Limited Agents, Oxford: Oxford University Press.
Moschovakis, Y., 1974, Elementary Induction on Abstract Structures, Amsterdam: North Holland.
Mulmuley, K., and Sohoni, M., 2001, “Geometric complexity theory I: An approach to P vs. NP and related problems,” SIAM Journal on Computing, 31(2): 496–526.
Mundhenk, M., and Weiß, F., 2010, “The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions,” in A. Kučera & I. Potapov (eds.), Reachability Problems, Vol. 6227, pp. 146–160, Berlin; Heidelberg: Springer.
Negri, S., and Von Plato, J., 2001, Structural Proof Theory, Cambridge, England: Cambridge University Press.
Nelson, E., 1986, Predicative Arithmetic Vol. 32, Princeton: Princeton University Press.
Nielsen, M. A., and Chuang, I., 2000, Quantum Computation and Quantum Information, Cambridge, England: Cambridge University Press.
Odifreddi, P., 1999, Classical Recursion Theory. Vol. II Vol. 143, Amsterdam: North-Holland.
Papadimitriou, C., 1994, Computational Complexity, New York: Addison-Wesley.
Parikh, R., 1971, “Existence and Feasibility in Arithmetic,” Journal of Symbolic Logic, 36(3): 494–508.
Pippenger, N., 1979, “On Simultaneous Resource Bounds,” in Foundations of Computer Science, 1979., 20th Annual Symposium on, pp. 307–311, IEEE.
Post, E., 1947, “Recursive unsolvability of a problem of Thue,” Journal of Symbolic Logic, 12(1): 1–11.
Pudlák, Pavel, 2013, Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction, Berlin: Springer.
Rabin, M., 1980, “Probabilistic Algorithm for Testing Primality,” Journal of Number Theory, 12(1): 128–138.
Rabin, M., and Scott, D., 1959, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development, 3(2): 114–125.
Rantala, V., 1982, “Impossible Worlds Semantics and Logical Omniscience,” Acta Philosophica Fennica, 35: 106–115.
Razborov, A., and Rudich, S., 1994, “Natural Proofs,” in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 204–213, ACM.
Rivest, R., Shamir, A., and Adleman, L., 1978, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 21(2): 120–126.
Robson, J., 1983, “The complexity of Go,” Information Processing: Proceedings of IFIP Congress,
–––, 1984, “N by N checkers is EXPTIME complete,” SIAM Journal on Computing, 13(2): 252–267.
Rogers, H., 1987, Theory of Recursive Functions and Effective Computability (Second Ed.), Cambridge, Massachusetts: MIT Press.
Rose, H., 1984, Subrecursion: functions and hierarchies, Oxford: Clarendon Press.
Rubinstein, A., 1998, Modeling Bounded Rationality Vol. 1, Cambridge, Massachusetts: MIT press.
Savitch, W., 1970, “Relationship Between Deterministic and Non-Deterministic Tape Classes,” Journal Computer System Science, 4: 177–192.
Sazonov, V., 1995, “On Feasible Numbers,” in D. Leivant (ed.), Logic and Computational Complexity, Vol. 960, pp. 30–51, Berlin: Springer.
Schorr, A., 1983, “Physical Parallel Devices Are Not Much Faster Than Sequential Ones,” Information Processing Letters, 17(2): 103–106.
Schrijver, A., 2005, “On the history of combinatorial optimization (till 1960),” Discrete Optimization, 12: 1–68.
Scott, A., and Sorkin, G., 2006, “Solving sparse random instances of MAX CUT and MSC 2-CSP in linear expected time,” Combinatorics, Probability and Computing, 15(1-2): 281–315.
Segerlind, N., 2007, “The Complexity of Propositional Proofs,” Bulletin of Symbolic Logic, 13(4): 417–481.
Seiferas, J., Fischer, M., and Meyer, A., 1973, “Refinements of the Nondeterministic Time and Space Hierarchies,” in 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 130–137.
Shor, P., 1999, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Review, 41(2): pp. 303–332.
Sieg, W., 2009, “On Computability,” in Andrew Irvine (ed.), Philosophy of Mathematics, Vol. 4, pp. 549–630, Amsterdam: North-Holland.
Simon, H., 1957, Models of Man: Social and Rational, New York: John Wiley.
–––, 1972, “Theories of Bounded Rationality,” Decision and Organization, 1: 161–176.
Sipser, H., 2006, Introduction to the Theory of Computation, Boston: Thomson.
Sipser, M., 1992, “The history and status of the P versus NP question,” in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 603–618, ACM.
Sistla, A., and Clarke, E., 1985, “The Complexity of Propositional Linear Temporal Logics,” Journal of the ACM, 32(3): 733–749.
Skolem, T., 1956, “An ordered set of arithmetic functions representing the least ϵ-number,” Det Konigelige Norske Videnskabers Selskab Fordhandlinger, 29: 54–59.
Slot, C., and Emde Boas, P. van, 1988, “The Problem of Space Invariance for Sequential Machines,” Information and Computation, 77(2): 93–122.
Stalnaker, R., 1991, “The problem of logical omniscience, I,” Synthese, 89(3): 425–440.
–––, 1999, “The Problem of Logical Omniscience, II,” in Context and Content, pp. 255–283, Oxford: Oxford University Press.
Statman, R., 1979, “Intuitionistic Propositional Logic Is Polynomial-Space Complete,” Theoretical Computer Science, 9(1): 67–72.
Stearns, R., Hartmanis, J., and Lewis, P., 1965, “Hierarchies of memory limited computations,” in Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 179–190.
Stockmeyer, L., 1977, “The Polynomial-Time Hierarchy,” Theoretical Computer Science, 3(1): 1–22.
Stockmeyer, L., and Meyer, A., 1973, “Word Problems Requiring Exponential Time (Preliminary Report),” in Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 1–9, ACM.
Trakhtenbrot, B., 1984, “A survey of Russian approaches to perebor (brute-force searches) algorithms,” Annals of the History of Computing, 6(4): 384–400.
Troelstra, A., and Schwichtenberg, H., 2000, Basic Proof Theory 2nd ed., Cambridge, England: Cambridge University Press.
Turing, A., 1937, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 2(1): 230.
Tversky, A., and Kahneman, D., 1974, “Judgment Under Uncertainty: Heuristics and Biases,” Science, 185(4157): 1124–1131.
Urquhart, A., 1984, “The Undecidability of Entailment and Relevant Implication,” The Journal of Symbolic Logic, 49(4): pp. 1059–1073.
Van Bendegem, J., 2012, “A Defense of Strict Finitism,” Constructivist Foundations, 7(2): 141–149.
Van Dantzig, D., 1955, “Is 101010 a finite number?” Dialectica, 9(3-4): 273–277.
Van Den Dries, L., and Levitz, H., 1984, “On Skolem’s exponential functions below 22x,” Transactions of the American Mathematical Society, 286(1): 339–349.
Van Leeuwen, J., 1990, Handbook of theoretical computer science Vol. A, Amsterdam: Elsevier.
Vardi, M., 1982, “The Complexity of Relational Query Languages,” in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 137–146.
Vardi, M., and Stockmeyer, L., 1985, “Improved Upper and Lower Bounds for Modal Logics of Programs,” in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 240–251.
Visser, Albert, 2009, “The predicative Frege hierarchy,” Annals of Pure and Applied Logic, 160(2): 129–153.
Vitányi, P., 1986, “Nonsequential Computation and Laws of Nature,” in F. Makedon, K. Mehlhorn, T. Papatheodorou, & P. Spirakis (eds.), VLSI Algorithms and Architectures, Vol. 227, pp. 108–120, Berlin; Heidelberg: Springer.
Vollmer, H., 1999, Introduction to Circuit Complexity: A Uniform Approach, New York: Springer-Verlag.
Vopěnka, P., 1979, Mathematics in the Alternative Set Theory, Leipzig: Teubner.
Wagner, K., and Wechsung, G., 1986, Computational Complexity, Dordrecht: Reidel.
Wang, H., 1958, “Eighty years of foundational studies,” Dialectica, 12: 466–497.
Watrous, J., 2009, “Quantum Computational Complexity,” in Encyclopedia of Complexity and Systems Science, pp. 7174–7201, Berlin: Springer.
–––, 2006b, “P, NP and mathematics–a computational complexity perspective,” in Proceedings of the 2006 International Congress of Mathematicians, pp. 665–712.
Williams, H., 1998, Édouard Lucas and Primality Testing, New York: Wiley.
Wolper, P., 1986, “Expressing Interesting Properties of Programs in Propositional Temporal Logic,” in Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 184–193.
Wrathall, C., 1978, “Rudimentary Predicates and Relative Computation,” SIAM Journal on Computing, 7(2): 194–209.
Yanofsky, N., and Mannucci, M., 2007, Quantum Computing for Computer Scientists, Cambridge, England: Cambridge University Press.
Yessenin-Volpin, A., 1961, “Le Programme Ultra-Intuitionniste Des Fondements Des Mathématiques.” in Infinitistic Methods, Proceedings of the Symposium on the Foundations of Mathematics, pp. 201–223, Oxford: Pergamon Press.
–––, 1970, “The Ultra-Intuitionistic Criticism and the Antitraditional Program for the Foundations of Mathematics,” in A. Kino, J. Myhill, & R. Vesley (eds.), Intuitionism and Proof Theory, pp. 3–45, Amsterdam: North-Holland.
Yablonski, S. 1959, “On the impossibility of eliminating perebor in solving some problems of circuit theory,” Dokl. A.N. SSSR 124: 44–47
Zambella, D., 1996, “Notes on Polynomially Bounded Arithmetic,” The Journal of Symbolic Logic, 61(3): 942–966.
Academic Tools
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). | |
Enhanced bibliography for this entry at PhilPapers, with links to its database. |
Other Internet Resources
The P vs NP Problem, Millennium Problems, Clay Mathematics Institute
A comprehensive list of NP-complete problems, maintained by Wikipedia.
Gödel’s Lost Letter and P=NP, a weblog on computational complexity theory maintained by Richard Lipton and Kenneth Regan (some extracted articles are published in Lipton and Regan 2013).
Computational Complexity, a weblog on computational complexity theory maintained by Lance Fortnow and William Gasarch.
Shtetl-Optimized, a weblog on complexity theory and quantum computation maintained by Scott Aaronson.
Related Entries
Church-Turing Thesis | computability and complexity | computer science, philosophy of | mathematics, philosophy of | quantum theory: quantum computing | recursive functions | Turing machines
最后更新于
