物理系统中的计算 in physical systems (Gualtiero Piccinini and Corey Maley)

首次发表于 2010 年 7 月 21 日星期三；实质性修订于 2021 年 6 月 16 日星期三

在我们日常的言论中，我们区分执行计算的物理系统，比如计算机和计算器，以及不执行计算的物理系统，比如岩石和雨滴。在计算设备中，我们区分更强大和不那么强大的设备。这些区别在实践和理论上都很重要：一台超级计算机可以在几分钟内完成一台笔记本电脑需要数十年才能完成的计算，而计算器甚至在原则上也无法做一些笔记本电脑可以做的事情。是什么决定了这些区别？在岩石和计算器之间，或者在计算器和计算机之间，如果有的话，有什么原则上的区别？回答这些问题比看起来更困难。

除了我们日常的交流之外，计算在许多科学中都是至关重要的。计算机科学家设计、构建和编程计算机。但是，再次，什么才算是计算机呢？如果一个销售员把一块普通的石头卖给你作为计算机，你可能应该要回你的钱。再次，这块石头缺少了什么，使得它不具备真正计算机的特征呢？

你能建造多强大的计算机？你能建造一台可以计算任何你想要的东西的机器吗？尽管经常说现代计算机可以计算任何东西（即自然数的任何函数，或者等价地，来自有限字母表的字符串的任何函数），但这是不正确的。普通计算机只能计算这些函数的微小子集。是否在物理上有可能做得更好？哪些函数是物理上可计算的？这些问题与物理学的基础紧密相关。

计算也是心理学和神经科学的核心，也许还涉及生物学的其他领域。根据认知计算理论，认知是一种计算：认知系统的行为是通过其执行的计算来因果解释的。为了测试某种计算理论，我们需要知道在物理系统中什么算作计算。再次强调，计算的本质是经验科学的基础。

1. 抽象计算与具体计算

计算可以通过形式化定义计算对象（如算法和图灵机）并证明其性质的定理来进行数学研究。计算的数学理论是数学的一个成熟分支，它处理抽象的计算，不考虑物理实现。

相比之下，科学和日常实践中大多数计算的用途涉及具体的计算：如计算机和大脑等物理系统中的计算。具体计算与抽象计算密切相关：例如，我们谈论物理系统运行算法或实现图灵机。但具体计算与抽象计算之间的关系并不是计算的数学理论的一部分，需要进一步研究（参见 Curtis-Trudel forthcoming-a，提出抽象和具体计算无法统一解释的论点）。关于具体计算的问题是本文的主要主题。然而，重要的是要记住一些基本的数学结果。

计算的最重要概念是数字计算，这是由艾伦·图灵（Alan Turing）、库尔特·哥德尔（Kurt Gödel）、阿隆佐·丘奇（Alonzo Church）、埃米尔·波斯特（Emil Post）和斯蒂芬·克利尼（Stephen Kleene）在 20 世纪 30 年代正式化的。他们的工作调查了数学的基础。一个关键问题是一阶逻辑是否可判定——是否存在一种算法，可以确定任何给定的一阶逻辑公式是否是定理。

Turing (1936–7) 和 Church (1936) 分别证明了答案是否定的：不存在这样的算法。为了证明这一点，他们提供了对有效可计算函数这一非正式概念的精确描述。图灵是以所谓的图灵机（TMs）来描述的，这些设备根据有限多条指令操作写在磁带上的离散符号。其他逻辑学家也做了同样的事情——他们用其他概念，比如 λ-可定义函数和一般递归函数，来形式化有效可计算函数的概念。

令人惊讶的是，所有这些概念都被证明在外延上是等价的：在这些形式体系中可计算的任何函数都可以在其他任何形式体系中计算。他们将此视为证据，证明他们对“算法”或“有效可计算函数”的精确定义的追求取得了成功。由此产生的观点——即图灵机和其他等价形式体系捕捉了算法的非正式概念——现在被称为 Church-Turing 论题（更多内容请参见第 4 节）。由图灵等人的工作使得可计算函数的研究成为计算的数学理论的一部分。

图灵等人关于计算概念的理论意义几乎无法言过其实。正如哥德尔指出的（在塔斯基之后的一次讲座中）：

塔斯基在他的讲座中强调（我认为是正确的）普遍递归概念（或图灵的可计算性）的重要性。我认为这种重要性主要是因为通过这个概念，人们首次成功地给出了一个有趣的认识论概念的绝对定义，即一个不依赖于所选择的形式主义的定义。（哥德尔，1946，84）

图灵还表明存在通用图灵机——可以计算任何其他图灵机可计算函数的机器。通用机器通过执行编码模拟机器行为的指令来实现这一点。假设了教会-图灵论题，通用图灵机可以计算任何可由算法计算的函数。这一结果对计算机科学非常重要：您不需要为不同的功能构建不同的计算机；一个通用计算机就足以计算任何可计算函数。现代数字计算机在这个意义上是通用的：数字计算机可以计算任何可由算法计算的函数，只要它们有时间和内存。（严格来说，通用机器具有无限的内存，而数字计算机的内存可以扩展但不是无限的，因此它们不是无限的。）

以上结果不应与计算机可以计算任何事物的常见说法混淆。这种说法是错误的：可计算性理论的另一个重要结果是，大多数函数不能被图灵机（因此也不能被数字计算机）计算。图灵机计算定义在可数域上的函数，例如来自有限字母表的字母串。这样的函数有不可数多个。但是图灵机只有可数多个；你可以通过列出每个图灵机规范（即某个有限字符串）来枚举图灵机。由于不可数无穷远大于可数无穷，因此可以得出结论，图灵机（因此数字计算机）只能计算所有函数的一小部分（在可数域上，例如自然数或字母串）。

TMs 和大多数现代计算机被称为（经典）数字计算机，即操作离散、明确定义状态字符串的计算机。数字计算机有时与模拟计算机进行对比，后者操作可以是连续的变量。连续变量是可以随时间连续改变其值并在某个区间内取任何值的变量。模拟计算机主要用于解决某些微分方程系统（Pour-El 1974，Rubel 1993）。

经典数字计算机也可以与量子计算机进行对比。量子计算机操作称为 qudits 的量子态（通常是二进制 qudits，称为量子比特）。与数字计算机的计算状态不同，从某些重要方面来看，qudits 在某种程度上彼此之间并不明确可区分。本条目将主要关注经典数字计算。有关量子计算的更多信息，请参阅有关量子计算的条目。

在计算理论中研究的相同对象——图灵机、算法等——通常被认为是由具体物理系统实现的。这带来了一个问题：当计算是由抽象数学形式定义时，如何让一个具体的物理系统执行计算？这可能被称为计算实现的问题。

计算实现的问题可以用几种不同的方式来阐述。柏拉图主义者将可计算性理论的形式主义解释为定义抽象对象。根据这种解释，图灵机、算法等都是抽象对象。但是一个具体的物理系统如何实现一个抽象对象，这种实现关系究竟是什么？反柏拉图主义者将可计算性理论的形式主义简单地看作是抽象的计算描述。但是一个具体的物理系统如何满足一个抽象的计算描述？无论计算实现的问题如何阐述，解决它都需要一个关于具体计算的说明——关于一个物理系统如何执行给定计算的说明。

一个密切相关的问题是区分物理系统，比如数字计算机，它们确实进行计算（如果有的话），以及像岩石这样的物理系统，它们不进行计算（或者看起来是这样）。与计算机不同，普通的岩石不会在计算机商店出售，通常也不被视为计算机。为什么？计算机具有什么岩石缺乏的东西，以至于计算机进行计算而岩石不会？（如果确实如此的话？）换句话说，什么样的具体系统能够进行计算？对这些问题的不同回答导致了对具体计算的不同解释。

关于具体计算的本质问题不应与计算建模的问题混淆。许多物理系统的动态演化可以通过计算模型来近似——这些计算模型是模拟或预测某些感兴趣系统的动力学或运动学的计算机程序。岩石的行为——以及河流、生态系统和行星系统等等——很可能可以通过计算模型来建模。但这并不意味着被建模的系统是计算设备——它们本身进行计算。乍看之下，只有相对少数而非常特殊的系统进行计算。解释这些系统何以特殊——或解释我们感觉它们特殊的原因——是具体计算的解释工作。

具体计算的描述

任何关于具体计算的描述必须解决的基本问题可以通过以下图表看出。考虑某个计算系统 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 的计算系统。

更准确地说，普特南（Putnam）仅以图灵机（Turing Machines，TMs）的术语勾勒了他最早的观点，引用了定义特定 TMs 的标准方式——“机器表”。机器表由每个 TM 的（有限数量的）内部状态的一列和每个机器符号类型的一行组成。机器表中的每个条目指定了在给定相关符号和内部状态时机器的操作。这是普特南解释物理系统成为 TM 所需的条件。

一个“机器表”描述了一台机器，如果该机器具有与表的列相对应的内部状态，并且如果它“遵守”表中的指令，即当它正在扫描一个方块，上面有一个符号 s1，并且处于，比如说，状态 B 时，它执行表中适当行和列的“指令”（在本例中，列 B 和行 s1）。任何由刚刚举例的机器表描述的机器都是图灵机。（普特南，1960/1975a，365；另见普特南，1967/1975a，433-4）

这个论述依赖于几个未解释的概念，比如方块（磁带的），符号，扫描和执行指令。此外，这个论述是用 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'。

根据简单映射理论，这块岩石实现了一个 NOT 门，执行着由“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 想到水时，当 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 处于相同类型的计算状态。换句话说，外部主义者认为计算状态在某种程度上是通过其参照物来个体化的，而参照物至少在一定程度上由系统外部的物理属性决定。相比之下，内部主义者认为计算状态的个体化方式完全取决于认知系统的内在物理属性。

迄今为止，外部主义者和内部主义者在一件事上达成一致：计算状态是由认知内容来区分的。这一要求可以放宽，而不放弃计算的语义解释。根据 Egan（1999）的观点，计算载体并不是由任何类型的认知内容来区分的，无论是广义的还是狭义的。相反，它们是由它们的数学内容来区分的——也就是，通过系统的计算理论将数学函数和对象赋予计算载体的语义内容。由于数学内容在物理复制品之间是相同的，Egan 认为她的数学内容是一种狭义内容——她是一种内部主义者。

让我们现在转向代表什么。这场辩论没有那么清晰地界定。根据一些作者的观点，只有具有类似语言组合句法的结构，支持组合语义的结构才算是计算载体，只有尊重这些结构的语义属性的操作才算是计算（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）都认为，无限全计算论所援引的映射违反了计算状态之间的反事实关系，而这些关系是上述反事实映射理论所要求的。再考虑 Putnam 的切片和聚合策略来生成映射。这些映射是基于任意物理系统的任意动力学演化构建的。并没有尝试去建立在条件不同的情况下物理系统会发生什么的情况。Chalmers 和 Copeland 认为这是不合法的，因为真正的实现必须展示计算状态之间存在的相同反事实关系。这一回应支持了计算的反事实映射理论。

对于无限全计算论的其他回应指出，物理状态之间的转换并非具有因果关系。普特南依赖的计算描述映射到物理描述，以至于计算描述并不描述物理系统的因果结构。根据一些作者的观点，非因果映射是不合法的（Chrisley 1995，Chalmers 1995，1996，2011，Scheutz 1999，2001）。这种类型的回应支持了计算的因果映射解释。

另一种对无限泛计算主义的回应隐含在戈德弗雷-史密斯（2009）的观点中。尽管戈德弗雷-史密斯主要关注的是功能主义而不是计算，但他的论点在这里仍然相关。戈德弗雷-史密斯认为，为了使映射构成真正的实现，被聚集在一起的微观物理状态（以对应于给定计算状态）必须在物理上相似——不能存在任意不同物理状态的任意分组，就像无限泛计算主义的论证中所述。戈德弗雷-史密斯建议，他对合法映射的相似性限制可能会被查尔默斯（1996）提出的因果和定位限制所补充。

计算的剩余解释——语义、句法和机械解释——比因果和反事实解释更加严格；它们对可接受的映射施加了进一步的限制。因此，与因果和反事实解释一样，它们有资源来避免无限的全计算论。

例如，考虑语义学解释，根据这种解释，计算需要表示。如果成为表示是相对少数事物所拥有的客观属性，那么基于只有构成表示的少数事物才是真正的计算状态的理由，无限的泛计算论被排除在外。然而，如果一切以相关方式都是表示性的，那么一切都是计算的（参见 Churchland 和 Sejnowski，1992 年，Shagrir，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 节中描述的物理意义上）构成了物理宇宙。有时会通过说，在最基本的物理层面上，状态之间存在着原始差异来表达这一观点——关于状态的本质无需或无法再说更多。这种观点颠覆了传统的计算与物理世界之间关系的观念。

根据上述讨论的所有计算的传统概念，物理计算需要物理媒介或基质。计算是物理系统的组织和行为的一个方面；没有硬件就没有软件。因此，根据传统概念，如果宇宙是一个元胞自动机，那么宇宙的最终组成部分就是元胞自动机的物理细胞。合理地问，这些细胞是什么样的物理实体，它们如何相互作用以满足它们的元胞自动机规则。

相比之下，根据实体全计算论的形而上学主张，一个物理系统只是一个计算状态系统。计算在本体论上优先于物理过程，可以说是“‘硬件’由‘软件’制成”（坎托尔 1982, 526, 534），或者“它”（物理）来自“比特”（计算）（惠勒 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 假设: 大胆

物理计算理论（Physical CTT）通常以非常强烈的形式表述。初步近似地，大胆的物理计算理论认为，任何物理过程——任何物理系统可以执行的事情——都可以被某个图灵机计算。

粗体物理 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）。因此，仅仅通过使用真正的随机过程生成一串数字，我们就有了超越图灵可计算的物理手段。正如 Turing（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 实际上是数学 CTT 的有趣物理类比。

(刚刚提出的观点并不影响 Pour-El (1974) 标准意义上的模拟计算。模拟计算不是操纵任意实值量的精确值，而是连续变量。尽管在大多数模拟计算中使用的连续变量可以假定在相关区间内取任意实值，但具体的模拟计算只需要对实际变量进行某种程度的近似操作和测量。因此，模拟计算并不证伪 Bold Physical CTT（参见 Rubel 1989）。)

关于数学 CTT 和粗体物理 CTT 之间所谓类比的疑虑可能会引发一个相关观察。许多当前的物理理论假设自然界包含沿着连续变化的实值量。这些量可能包括物体的速度、定义它们在时空流形中重心位置的坐标等。如果这些物理理论是正确的，那么许多实体的许多属性将以任意实数作为它们的值。而在任何连续区间中，大多数实数都是图灵不可计算的（即只有可数多个可计算数，但任何连续区间包含不可数多个实数）。因此，任意实值量是可计算的概率为零。因此，如果我们的物理理论是正确的，那么相关物理属性的大多数转换都是将图灵不可计算的量转换为另一种量。

例如，一个物体的速度变化，甚至是它简单的空间位置变化，可能是一个图灵不可计算的实值量转化为另一个的转化。一个图灵不可计算值转化为另一个图灵不可计算值是一个图灵不可计算的操作——如果没有别的原因，因为没有图灵机可以记录下这种操作的输入和输出。在这个观点下，物理世界充满了超越图灵机能力的操作，因此大胆的物理计算论被证伪。

没有理由相信我们可以使用刚才提到的图灵不可计算的操作来进行计算，从而满足我们对计算的兴趣，即解决问题、为期望的参数生成期望函数的值、理解某些物理系统等。换句话说，所讨论的操作不应被视为计算。受到这些操作威胁的粗体物理 CTT 与数学 CTT 并没有有趣的类比。

为了总结我们对 Bold Physical CTT 的讨论，区分物理可计算性问题——即与数学 CTT 的物理类比相关的问题，可能是有帮助的。关于物理过程与可计算性之间关系的许多问题都值得探讨。什么是物理可计算函数？这个问题应该激发对物理 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 所覆盖，再加上物理状态与计算状态之间相对无争议的映射。数学 CTT 表明，任何可以通过有效程序计算的函数都可以通过图灵机计算。由于图灵机可以在物理上实现（或者被计算人员替代），任何遵循有效程序的过程都是可以在物理上计算的。

但是在当前意义上，物理计算是比有效过程计算更广泛的概念。即使没有有效过程来描述这个过程，一个过程也可能被视为物理计算，也许是因为没有构成该过程的内部状态的有限瞬时描述，或者没有办法有限地并确切地指定从一个瞬时描述到下一个的转换。因此，谦虚的物理 CTT 比数学 CTT 更强大。

Gandy (1980) 是最早讨论谦虚物理 CTT 版本之一，认为具有离散组件和合理物理限制（组件尺寸的下限和运动速度的上限）的机制只能物理计算图灵可计算函数。然而，谦虚物理 CTT 不一定受到这些限制。除了遵循有效程序的物理过程外，谦虚物理 CTT 还可能涵盖连续动力过程（如某些类型的神经网络）、跨越大部分时空的过程以及量子过程（如量子计算）。但物理计算并不包括所有物理过程。

根据这一提议，谦虚的物理 CTT 认为，任何（可数域上的）物理可计算函数都是图灵可计算的。

为了使一个过程被视为物理计算，并因此与谦逊物理 CTT 相关，观察者必须能够使用它来生成独立指定函数的期望值。这一要求可以用多个约束来阐明（Piccinini 2015，第 15 章和第 16 章）。这个列表并非旨在详尽无遗：

可读的输入和输出。该过程必须接受输入并产生观察者可以无误阅读的输出，以便观察者可以将输出用作问题的解决方案或在输入上定义的函数的值。为了实现这一点，很可能需要将输入和输出化简为离散状态的字符串，就像普通数字计算机的输入和输出一样。
过程无关规则。必须有一个固定的规则或映射——可以独立于物理过程指定——将输出与输入联系起来。通过定义过程要解决的问题，这个规则告诉用户通过运行过程将学到什么。由于规则通常定义了一般的物理计算，规则不必是递归的。例如，它可以是为图灵机定义停机问题的规则。但像所有递归规则一样，规则对于属于同一问题的所有输入必须是相同的；它不能从一个输入改变到下一个输入。
可重复性。该过程必须是可重复的，至少在原则上，以便用户能够多次获得相同的结果并通过重复计算来检查计算。
可设定性。正在进行过程的系统必须是可设定的，以便用户可以选择系统计算函数的哪个参数，并设置系统计算函数的相关值。
物理可构建性。该系统必须是物理可构建的。
可靠性。在过程完成之前，系统不得发生故障。

总的来说，谦虚的物理 CTT 断言，每个可以在物理上计算的函数，即，根据作用于字符串的过程无关规则将输入字符串转换为输出字符串的每个可用转换，都是图灵可计算的。

由于谦虚的物理 CTT 受到认识论相关标准的限制，它不会引起与大胆的物理 CTT 相关的担忧，即它太容易被证伪，与激发 CTT 的可计算性概念无关。而且有充分的理由相信谦虚的物理 CTT。所有已经建造或正在建造的用于计算可数域函数的计算机制都只计算图灵可计算的函数。

理解适度物理 CTT 的确切范围是很重要的。适度物理 CTT 并不意味着每个物理过程都是一种计算，或者每个物理系统都是一个计算系统。它只是说，如果某物理事物计算可数域的函数，那么它所计算的函数是图灵可计算的。

要充分评估谦虚物理 CTT，我们应该考虑是否可能构建一台机器，类似于普通的数字计算机，可以被人类观察者使用，但与普通的数字计算机不同，能够生成图灵不可计算的函数值。近年来，已经提出了几种超计算的设计。超计算是计算图灵不可计算函数。如果超计算被证明在物理上是可能的，那将推翻谦虚物理 CTT。

4.3 超级计算

就第一次近似而言，超级计算机是一个能够产生图灵不可计算函数值的系统。如果未明确规定什么算是产生函数值，那么在第 4.1 节讨论的任何系统，比如真正随机过程和操纵任意实值量的系统，都可以被视为超级计算机。但在讨论 Bold Physical CTT 时，我们发现仅仅产生图灵不可计算函数值，并没有进一步的约束条件，这对于真正的物理计算是不够的。

通过类比于大胆物理 CTT 和谦虚物理 CTT 之间的区别，让我们通过区分可用的超计算机和不可用的超计算过程来区分超计算的弱和强概念。

一个无法使用的超计算过程是一个物理过程，它未能满足物理计算的前四个约束之一。例如，这些过程的输入或输出是任意实值数量（无法用无限精度读取）和真正随机过程（其输入和输出没有规则表征，独立于过程，并且既不可重复也不可设置）。这些过程是不可用的，因为观察者无法从中获得独立定义函数在选择的输入上的任意值，就像普通计算系统可以做到的那样（只要有足够的时间和空间）。由于它们不可用，无法使用的超计算过程与谦虚物理 CTT 无关。

一个可用的超级计算机是一个满足至少前四个物理计算约束的物理系统。它具有可读的输入和输出，有一个规则描述其输入输出特性，可以独立于过程本身定义，并且其过程是可重复和可设置的。如果一个系统不满足这些条件中的一个，那么它在与谦虚物理 CTT 相关的意义上不被视为计算。

一个满足这些条件的系统——一个可用的超级计算机——可能是纯粹概念上的。例如，无限加速的图灵机（Copeland 2002）是在每次计算操作中以前一次操作时间的一半执行的图灵机。因此，无限加速的图灵机在两倍于执行第一次操作所需时间内完成无限次操作（一个超任务）。这使得无限加速的图灵机能够计算图灵不可计算的函数，如停机函数。但通常将无限加速的图灵机作为概念实体进行讨论，没有证据表明它们可以被构建。当然，纯粹概念上的系统并不证伪谦逊的物理 CTT。要做到这一点，一个系统必须至少满足物理计算的第五和第六个约束：它必须是物理可构建的，并且必须可靠运行。

构建类似于无限加速的 TM 的一种方法是制造一台计算机，经过一些计算操作后，建造一个更小更快的自身的副本（Davies 2001）。这个更小更快的副本也会执行一些操作，然后建造一个更快更小的副本，依此类推。在适当的假设下，由此产生的一系列无限缩小的机器将能够在有限时间内完成无限次计算操作，从而超越 TM 的能力。尽管无限缩小的机器似乎与牛顿力学一致，但 Davies（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

Andréka, H., Németi, I., and P. Németi, 2009, “General Relativistic Hypercomputing and Foundation of Mathematics,” Natural Computing, 8(3): 499–516.
Andréka, H., Madarász, J. X., Németi, I., Németi, P. and Székely, G., 2018, “Relativistic computation,” in Cuffaro and Fletcher (eds.) 2018.
Beggs, E. J., and J.V. Tucker, 2007, “Can Newtonian Systems, Bounded in Space, Time, Mass and Energy Compute all Functions?” Theoretical Computer Science, 371(1–2): 4–19.
Block, N., 1978, “Troubles with Functionalism,” in Perception and Cognition: Issues in the Foundations of Psychology, C. W. Savage (ed.), Minneapolis, University of Minnesota Press, pp. 261–325.
Blum, L., Cucker F., Shub M., and S. Smale, 1998, Complexity and Real Computation, New York: Springer.
Bontly, T., 1998, “Individualism and the Nature of Syntactic States,” British Journal for the Philosophy of Science, 49(4): 557–574.
Bub, J., 2005, “Quantum Mechanics is About Quantum Information,” Foundations of Physics, 35(4): 541–560.
Burge, T., 1986, “Individualism and Psychology,” Philosophical Review, 45: 3–45.
Button, T., 2009, “SAD Computers and Two Versions of the Church-Turing Thesis,” British Journal for the Philosophy of Science, 60(4): 765–792.
Calude, C. S., 2005, “Algorithmic Randomness, Quantum Physics, and Incompleteness,” in Proceedings of the Conference “Machines, Computations and Universality” (MCU 2004), M. Margenstern (ed.), Berlin: Springer, pp. 1–17.
Calude, C. S., and B. Pavlov, 2002, “Coins, Quantum Measurements, and Turing’s Barrier,” Quantum Information Processing, 1(1–2): 107–127.
Calude, C. S., and K. Svozil, 2008, “Quantum Randomness and Value Indefiniteness,” Advanced Science Letters, 1(2): 165–168.
Campbell, D. I., and Yang, Y., 2021, “Does the solar system compute the laws of motion?” Synthese, 198: 3203–3220.
Chalmers, D. J., 1995, “On Implementing a Computation,” Minds and Machines, 4: 391–402.
–––, 1996, “Does a Rock Implement Every Finite-State Automaton?” Synthese, 108: 310-333.
–––, 2011, “A Computational Foundation for the Study of Cognition,” Journal of Cognitive Science, 12(4): 323–57.
Chrisley, R. L., 1995, “Why Everything Doesn’t Realize Every Computation,” Minds and Machines, 4: 403–430.
Church, A., 1932, “A Set of Postulates for the Foundation of Logic,” Annals of Mathematics, 33: 346–366.
–––, 1936, “An Unsolvable Problem in Elementary Number Theory,” The American Journal of Mathematics, 58: 345–363.
Churchland, P. S., and T. J. Sejnowski, 1992, The Computational Brain, Cambridge, MA: MIT Press.
Coelho Mollo, D., 2018, “Functional Individuation, Mechanistic Implementation: The Proper Way of Seeing the Mechanistic View of Concrete Computation,” Synthese, 195(8): 3477–97.
Copeland, B. J., 1996, “What is Computation?” Synthese, 108(3): 335–359.
–––, 2000, “Narrow Versus Wide Mechanism: Including a Re-Examination of Turing’s Views on the Mind-Machine Issue.” The Journal of Philosophy, XCVI(1): 5–33.
–––, 2002, “Accelerating Turing Machines,” Minds and Machines, 12(2): 281–301.
Crane, T., 1990, “The Language of Thought: No Syntax Without Semantics,” Mind and Language, 5(3): 187–212.
Craver, C. F., 2012, “Functions and Mechanisms: A Perspectivalist Account,” in P. Huneman (ed.), Functions, Dordrecht: Springer.
Cuffaro, Michael E., and Samuel C. Fletcher (eds.), 2018, Physical Perspectives on Computation, Computational Perspectives on Physics, Cambridge: Cambridge University Press.
Cummins, R., 1983, The Nature of Psychological Explanation, Cambridge, MA: MIT Press.
Curtis-Trudel, A., forthcoming-a, “Why Do We Need A Theory of Implementation?” British Journal for the Philosophy of Science. doi:10.1086/714791
Curtis-Trudel, A., forthcoming-b, “Implementation as Resemblance,” Philosophy of Science. doi:10.1086/714872
Davies, E. B., 2001, “Building Infinite Machines,” British Journal for the Philosophy of Science, 52(4): 671–682.
Davis, M., 2004a, “The Myth of Hypercomputation,” in Alan Turing: Life and Legacy of a Great Thinker, C. Teuscher (ed.), Berlin: Springer, pp. 195–211.
––– (ed.), 2004b, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Dover: Mineola.
Dennett, D. C., 1987, The Intentional Stance, Cambridge, MA: MIT Press.
Deutsch, D., 1985, “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer,” Proceedings of the Royal Society of London A, 400: 97–117.
Dewhurst, J., 2018, “Computing Mechanisms without Proper Functions,” Minds and Machines, 28: 569–88.
Dretske, F. I., 1981, Knowledge and the Flow of Information, Cambridge, MA: MIT Press.
Duwell, A., 2017, “Exploring the Frontiers of Computation: Measurement Based Quantum Computers and the Mechanistic View of Computation,” in A. Bokulich and J. Floyd (eds.), Turing 100: Philosophical Explorations of the Legacy of Alan Turing (Boston Studies in the Philosophy and History of Science: Volume 324), New York: Springer, 219–32.
Earman, J., 1986, A Primer on Determinism, Dordrecht: D. Reidel.
Earman, J., and J. Norton, 1993, “Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes,” Philosophy of Science, 60: 22–42.
Egan, F., 1999, “In Defence of Narrow Mindedness.” Mind and Language, 14(2): 177–194.
–––, 2010, “Computational Models: A Modest Role For Content,” Studies in the History and Philosophy of Science, 41(3): 253–259.
Etesi, G., and I. Németi, 2002, “Non-Turing Computations via Malament-Hogarth Spacetimes,” International Journal of Theoretical Physics, 41: 342–370.
Feynman, R. P., 1982, “Simulating Physics with Computers,” International Journal of Theoretical Physics, 21(6–7): 467–488.
Fodor, J. A., 1975, The Language of Thought, Cambridge, MA: Harvard University Press.
–––, 1981, “The Mind-Body Problem,” Scientific American, 244: 114–125.
–––, 2008, LOT 2: The Language of Thought Revisited, Oxford: Oxford University Press.
Fredkin, E., 1990, “Digital Mechanics: An Information Process Based on Reversible Universal Cellular Automata,” Physica D, 45: 254–270.
Fresco, N., 2010, “Explaining Computation Without Semantics: Keeping It Simple,” Minds and Machines, 20: 165–181.
–––, 2014, Physical Computation and Cognitive Science, New York: Springer.
Fuchs, C. A., 2004, “Quantum Mechanics as Quantum Information (and only a little more),” in Quantum Theory: Reconsiderations of Foundations, A. Khrennikov (ed.), Växjö, Sweden: Växjö University Press, pp. 463–543.
Gandy, R., 1980, “Church’s Thesis and Principles for Mechanism,” in J. Barwise, H. J. Keisler, K. Kunen (eds.), The Kleene Symposium: Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland Publishing.
Garson, J., 2013, “The Functional Sense of Mechanism,” Philosophy of Science, 80: 317–333.
Gödel, K., 1934, “On Undecidable Propositions of Formal Mathematical Systemsm,” in The Undecidable, M. Davis (ed.), Ewlett, NY: Raven, pp. 41–71.
–––, 1936. “Über die Lange von Beweisen,” Ergebnisse eines mathematischen Kolloquiums, 7: 23–24.
–––, 1946, “Remarks Before the Princeton Bicentennial Conference on Problems in Mathematics,” reprinted in Davis 2004b, pp. 84–88.
Godfrey-Smith, P., 2009, “Triviality Arguments Against Functionalism,” Philosophical Studies, 145(2): 273–295.
Grice, H. P., 1957, “Meaning,” The Philosophical Review, 66(3): 377–388.
Hagar, A., and A. Korolev, 2007, “Quantum Hypercomputation--Hyper or Computation?,” Philosophy of Science, 74(3): 347–363.
Hamkins, J. D., 2002. “Infinite Time Turing Machines,” Minds and Machines, 12: 521–539.
Harman, G., 1987, “(Nonsolipsistic) Conceptual Role Semantics,” in New Directions in Semantics, E. Lepore (ed.), London: Academic Press, pp. 55–81.
Hogarth, M. L., 1994, “Non-Turing Computers and Non-Turing Computability,” PSA 1994(1): 126–138.
–––, 2004, “Deciding Arithmetic Using SAD Computers,” British Journal for the Philosophy of Science, 55: 681–691.
Isaac, A., 2019, “The Semantics Latent in Shannon Information,” British Journal for the Philosophy of Science, 70(1): 103–125.
Jacquette, D., 1991, “The Myth of Pure Syntax,” in Topics in Philosophy and Artificial Intelligence, L. Albertazzi and R. Rolli (eds.), Bozen: Istituto Mitteleuropeo di Cultura, pp. 1–14.
Kantor, F. W., 1982, “An Informal Partial Overview of Information Mechanics,” International Journal of Theoretical Physics, 21(6–7): 525–35.
Kaplan, D. M., 2011, “Explanation and Description in Computational Neuroscience,” Synthese, 183(3): 339–373.
Kieu, T. D., 2002, “Quantum Hypercomputation,” Minds and Machines, 12(4): 541–561.
–––, 2003, “Computing the Noncomputable,” Contemporary Physics, 44: 51–71.
–––, 2004, “A Reformulation of Hilbert’s Tenth Problem through Quantum Mechanics,” Proceedings of the Royal Society A, 460(2045): 1535–1545.
–––, 2005, “An Anatomy of a Quantum Adiabatic Algorithm that Transcends the Turing Computability,” International Journal of Quantum Information, 3(1): 177–183.
Kleene, S. C., 1935, “A Theory of Positive Integers in Formal Logic,” American Journal of Mathematics, 57: 153–173 and 219–244.
–––, 1952, Introduction to Metamathematics, Princeton: Van Nostrand.
Klein, C., 2008, “Dispositional Implementation Solves the Superfluous Structure Problem,” Synthese, 165: 141–153.
Leff, H. S. and A.F. Rex, (eds.), 2003, Maxwell’s Demon 2: Entropy, Classical and Quantum Information, Computing, Bristol: Institute of Physics Publishing.
Lloyd, S., 2006, Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos, New York: Knopf.
Lycan, W., 1981, “Form, Function, and Feel,” Journal of Philosophy, 78(1): 24–50.
Machamer, P. K., Darden, L., and C. Craver, 2000, “Thinking About Mechanisms,” Philosophy of Science, 67: 1–25.
Maley, C. J., forthcoming, “Analog Computation and Representation,” British Journal for the Philosophy of Science. doi:10.1086/715031
Martin, C. B., 1997, “On the Need for Properties: The Road to Pythagoreanism and Back,” Synthese, 112(2): 193–231.
Maudlin, T., 1989, “Computation and Consciousness,” Journal of Philosophy, 86(8): 407–432.
Milkowski, M., 2013, Explaining the Computational Mind, Cambridge, MA: MIT Press.
Mills, J. W., 2008, “The Nature of the Extended Analog Computer,” Physica D: Nonlinear Phenomena, 237(9): 1235–1256.
Németi, I., and G. Dávid, 2006, “Relativistic Computers and the Turing Barrier,” Journal of Applied Mathematics and Computation, 178(1): 118–142.
Nielsen, M. A., 1997, “Computable Functions, Quantum Measurements, and Quantum Dynamics,” Physical Review Letters, 79(15): 2915–2918.
Nielsen, M. A., and I. L. Chuang, 2000, Quantum Computation and Quantum Information, New York: Cambridge University Press.
Ord, T., 2006, “The Many Forms of Hypercomputation,” Applied Mathematics and Computation, 178(1): 143–153.
Papayannopoulos, P., 2020, “Computing and modelling: Analog vs. Analogue,” Studies in History and Philosophy of Science, 83: 103–120.
Piccinini, G., 2004, “Functionalism, Computationalism, and Mental Contents,” Canadian Journal of Philosophy, 34(3): 375–410.
–––, 2007, “Computing Mechanisms,” Philosophy of Science, 74(4): 501–526.
–––, 2010, “The Mind as Neural Software? Understanding Functionalism, Computationalism, and Computational Functionalism,” Philosophy and Phenomenological Research, 81(2): 269–311.
–––, 2015, Physical Computation: A Mechanistic Account, Oxford: Oxford University Press.
Piccinini, G. and A. Scarantino, 2011, “Information Processing, Computation, and Cognition,” Journal of Biological Physics 37(1): 1–38.
Pitowsky, I., 1990, “The Physical Church Thesis and Physical Computational Complexity,” Iyyun, 39: 81–99.
–––, 2002, “Quantum Speed-Up of Computations,” Philosophy of Science, 69: S168-S177.
Pour-El, M. B., 1974, “Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers),” Transactions of the American Mathematical Society, 199: 1–28.
–––, 1999, The Structure of Computability in Analysis and Physical Theory: An Extension of Church’s Thesis. In Handbooks of Computability Theory, E.R. Griffor (ed.), New York: Elsevier, pp. 449–471.
Putnam, H., 1960, “Minds and Machines,” in Dimensions of Mind: A Symposium, S. Hook (ed.), New York: Collier, pp. 138–164; Reprinted in Putnam 1975a, pp. 362–386.
–––, 1967, “Psychological Predicates,” in Art, Mind, and Religion, W.H. Capitan & D.D. Merrill (eds.), Pittsburgh, PA: University of Pittsburgh Press, pp. 37–48. Reprinted in Putnam 1975a as “The Nature of Mental States,” pp. 150–161.
–––, 1975a, Philosophical Papers: Volume 2, Mind, Language and Reality, Cambridge: Cambridge University Press.
–––, 1975b, “The Meaning of ‘Meaning’,” in Language, Mind and Knowledge. Minnesota Studies in the Philosophy of Science, vol. 7, K. Gunderson (ed.), Minneapolis: University of Minnesota Press, pp. 131–193. Reprinted in Putnam 1975a, pp. 215–271.
–––, 1988, Representation and Reality, Cambridge, MA: MIT Press.
Pylyshyn, Z. W., 1984, Computation and Cognition, Cambridge, MA: MIT Press.
Quine, W. V. O., (1976), “Whither Physical Objects?” in Essays in Memory of Imre Lakatos, (Series: Boston Studies in the Philosophy of Science), R.S. Cohen, P.K. Feyerabend, & M.W. Wartofsky (eds.), Dordrecht: Reidel, pp. 497–504.
Rescorla, M., 2014, “A Theory of Computational Implementation,” Synthese, 191: 1277–1307.
Rubel, L. A., 1989, “Digital Simulation of Analog Computation and Church’s Thesis,” Journal of Symbolic Logic, 54(3): 1011–1017.
–––, 1993, “The Extended Analog Computer,” Advances in Applied Mathematics, 14(1): 39–50.
Scheutz, M., 1999, “When Physical Systems Realize Functions …,” Minds and Machines, 9(2): 161–196.
–––, 2001, “Causal versus Computational Complexity,” Minds and Machines, 11(4): 534–566.
Schonbein, W., 2005, “Cognition and the Power of Continuous Dynamical Systems,” Minds and Machines, 15(1): 57–71.
Searle, J. R., 1992, The Rediscovery of the Mind, Cambridge, MA: MIT Press.
Segal, G., 1991, “Defence of a Reasonable Individualism,” Mind, 100(400): 485–493.
Shagrir, O., 2001. “Content, Computation and Externalism,” Mind, 110(438): 369–400.
–––, 2006, “Why We View the Brain as a Computer,” Synthese, 153(3): 393–416.
–––, forthcoming, The Nature of Physical Computation, Oxford: Oxford University Press.
Shagrir, O., and I. Pitowsky, 2003, “Physical Hypercomputation and the Church-Turing Thesis,” Minds and Machines, 13(1): 87–101.
Shannon, C. E., and W. Weaver, 1949, The Mathematical Theory of Communication, Urbana: University of Illinois Press.
Shapiro, L. A., 1997, “A Clearer Vision,” Philosophy of Science, 64(1): 131–153.
Shor, P. W., 1994, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” in Proceedings of the 357th Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, pp. 124–134.
Sieg, W., 2006, “On Computability,” in Philosophy of Mathematics (Handbook of the Philosophy of Science), A. Irvine (ed.) Amsterdam: Elsevier, pp. 535–630.
Siegelmann, H. T., 1999, Neural Networks and Analog Computation: Beyond the Turing Limit, Boston: Birkhäuser.
Šíma, J., and P. Orponen, 2003, “General-purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results,” Neural Computation, 15: 2727–78.
Smith, B. C., 2002, “The Foundations of Computing,” in Computationalism: New Directions, M. Scheutz (ed.), Cambridge, MA: MIT Press, pp. 23–58.
Smith, W. D., 2006a, “Church’s Thesis Meets the N-body Problem,” Applied Mathematics and Computation, 178(1): 154–183.
–––, 2006b, “Three Counterexamples Refuting Kieu’s Plan for Quantum Adiabatic Hypercomputation; and Some Uncomputable Quantum Mechanical Tasks,” Applied Mathematics and Computation, 178(1): 184–193.
Stannett, M., 1990, “X-Machines and the Halting Problem: Building a Super-Turing Machine,” Formal Aspects of Computing, 2(1): 331–341.
Stich, S., 1983, From Folk Psychology to Cognitive Science, Cambridge, MA: MIT Press.
Toffoli, T., 1982, “Physics and Computation,” International Journal of Theoretical Physics, 21(3–4): 165–175.
Tucker, Chris, 2018, “How to Explain Miscomputation,” Philosophers’ Imprint, 18(24). [Tucker 2018 available online]
Turing, A. M., 1936–7, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceeding of the London Mathematical Society, 42(1): 230–265, reprinted in Davis 2004b, pp. 116–154.
–––, 1950, “Computing Machinery and Intelligence,” Mind, LIX(236): 433–460.
Wheeler, J. A., 1982, “The Computer and the Universe,” International Journal of Theoretical Physics, 21(6–7): 557–572.
–––, 1989, “Information, Physics, Quantum: The Search for Links,” Proceedings III International Symposium on Foundations of Quantum Mechanics, Tokyo, 354–358.
Wolfram, S., 2002, A New Kind of Science, Champaign, IL: Wolfram Media.
Zuse, K., 1970, Calculating Space, Cambridge, MA: MIT Press.
–––, 1982, “The Computing Universe,” International Journal of Theoretical Physics, 21(6–7): 589–600.

Academic Tools

Other Internet Resources

Hodges, A., 2005, “Can quantum computing solve classically unsolvable problems?” [PDF].
special issue of the journal Entropy, published by MDPI (aka Multidisciplinary Digital Publishing Institute).
Bibliography on Computation and Physical Systems, at the PhilPapers website.
Hypercomputation Research Network

Acknowledgments

Many thanks to Neal Anderson, David Chalmers, Nir Fresco, Mark Sprevak, Fred Kroon, Ray Turner, and several anonymous referees for helpful comments on previous drafts. Thanks to James Virtel for editorial assistance. This material is based in part upon work supported by the National Science Foundation under Grant No. SES-0924527.

上一页*计算 computation 下一页计算复杂性理论 computational complexity theory (Walter Dean)

最后更新于14小时前