教会图论文（七）_数学联邦政治世界观()

6.2计算复杂性：延长的教会图论文

图灵机现在不仅在可计算性理论中持有一个中央处，而且在复杂性理论中。 Quantum Computation研究人员Bernstein和Vazirani说：

正如可计算性理论在教会上论文中的基础上，计算复杂性理论就在现代加强本文时依赖于此论文。（伯尔尼斯坦＆Vazirani 1997：1411）

事实上，现代计算机科学文献中的教会教学论文的两种不同的复杂性 - 理论版本。两者都被称为“延长的教会图论文”。第一个由姚明于2003年呈现：

扩展的教堂 - 图灵论文（ECT）使得...断言，图定型机模型也是有效的，因为任何计算设备都可以是有效的。也就是说，如果函数是由某些硬件设备的计算可计算的

（

）

�

（

�

）

输入大小

�

，然后它是由图灵机可计算的

（

）

（

�

（

�

）

�

对于一些固定的

�

（取决于问题）。（姚2003：100-101）

姚明指出，ECT有一个强大的含义：

至少原则上，要使未来的计算机更有效，只需要专注于改善当今计算机设计的实现技术。（2003：101）

与原始教会的教学论文（其状态是“定理和定义”之间的某些东西，ECT既不是Logico-数学定理也不是定义。如果是真的，那么它的真相是物理法则的结果 - 它可能不是真的。（虽然如果与计算机科学中的标准但经过未经经过经过原因的假设，但它是微不足道的，但是P = NP。）

论文的第二个复杂性 - 理论版本涉及概率图定型机的概念（由于Rabin＆Scott 1959）。 Vazirani和Aharonov国家论文：

[T]他扩展了教会图书论文...断言，可以通过经典计算的标准模型来有效地模拟任何合理的计算模型，即概率的图灵机。（Aharonov＆Vazirani 2013：329）

这两个相关的论文与原始教会的教学论文有很大不同，尤其是两个扩展的论文都是经验假设。此外，还有正在进行的辩论，以及Quantum Computer是否实际上是伪造这些论文。（对于本次辩论介绍，请参阅2019年的COPELAND＆SHAGRIR，以及更详细的治疗方法，参见AHARONOV＆VAZIRANI 2013.）

6.3脑仿真和教会图论

有时表示，教堂图论文对计算模拟范围有关。例如，Searle写道：

是否可以在数字计算机上模拟大脑的操作？ ......答案在我看来......显着的是“是”......这是自然解释的，问题意味着：大脑的一些描述，使得在该描述下可以做出大脑操作的计算模拟。但是，给予教会的论文，可以在数字计算机上模拟可以在数字计算机上模拟一组步骤的精确表征的任何东西，因此这个问题具有肯定答案。（Searle 1992：200）

另一个例子：

我们可以依靠有一个图灵机来捕获大脑的功能关系，

这么久

输入和输出之间的这些关系在功能上表现得足够足以可以描述......数学关系...我们知道一些特定版本的图灵机将能够模仿它们。（Guttenplan 1994：595）

Andréka，Németi和Németi州更长的一般论文关于图灵机的力量，以模拟其他系统：

[t]他的身体教会图论文......是猜想，无论物理计算设备（在更广泛的意义）或物理思想实验中都是由未来的任何文明设计的，它将始终是由图灵机模拟的。（andréka，németi，＆németi2009：500）

andréka，németi和németi甚至说他们在这里的论点“在20世纪30年代被制定并普遍接受”（同上）。

然而，并不是关于在20世纪30年代制定的教会和图灵制定的物理系统的模拟，而是一种关于人类计算的完全不同的论点 - 这是后者在20世纪30年代和20世纪40年代普遍接受的后者。

它肯定是泥泞的水域致电关于模拟“教会论文”或“教会的论文”的论点，因为教会和图灵用于支持他们的实际论文的论点根本无法支持在几个报价中阐述的论文以上。尽管如此，什么可以称为“模拟论文”在现代形式的教会上论文的目录中有其位置：

模拟论文：

可以通过数学关系（GuttenPlan）描述其操作作为一组步骤（Searle）或其输入输出关系的系统可以由图灵机模拟。

如果模拟论文旨在涵盖所有可能的系统，那么它肯定是假的，因为Doyle的设想平衡系统伪造它（第5.3.3节）。另一方面，如果论文旨在仅涵盖实际的物理系统，包括大脑，那么模拟论点就像扩大的教会图论论文一样，经验论文 - 因此与图灵的论文和教会的论文截然不同。 “实际物理系统”版本的仿真论文的真实性取决于物理法。

一种潜在的反对意见，即模拟论文的任何上升者都需要面对令人难以努力为论文筹集的难题（第5.1节）。没有离散的物理系统 - 例如Gandy的“基本上模拟机” - 以伪造仿真论文，因为具有连续动态的系统的变量采取任意的实数作为它们的值，而图灵机仅限于可计算的真实数字，因此不能完全模拟连续系统。

这将讨论正常到了该地区最有趣的主题之一，所谓的教会图论论文的“物理版本”。

6.4教堂的论文和物理学

6.4.1德意志 - Wolfram论文

1985年，Wolfram制定了一篇论文，他被描述为“教会图假设的身体形式”：

[u]八联化计算机在其计算能力中具有强大的功能，因为任何物理可实现的系统都可以，因此它们可以模拟任何物理系统。（Wolfram 1985：735）

德意志（落在量子计算的基础）独立地阐述了类似的论文，1985年再次描述了它作为教会图所论文的“物理版”：

我现在可以说明教堂的物理版本：“每个有限可变的物理系统都可以通过有限手段运行的通用模型计算机完美地模拟”。这种配方既比表达它的方式更好地定义和更多的物理。（Deutsch 1985：99）

本论文肯定是“更有物质”而不是图灵的论文。然而，从图灵的自己的自行方式是完全不同的索赔，因此潜在令人困惑地展示它作为所说的“更好的定义”版本。正如已经强调的那样，图灵正在谈论有效的方法，而Deutsch和Wolfram介绍的论文涉及所有（可实现的）物理系统 - 无论系统的活动是否有效。

在这次早期工作的德意志和沃尔佛之后，“教会教学论文的身体形态”，“教会的物理版本” - 即使是“物理教会图论论文” - 现在在目前的文献中非常常见。然而，这种术语可能更好地避免，因为这些物理论文非常遥远，从图灵的论文和教会的论文中非常遥远。

在1985年的纸质中，德意志继续指出，如果描述“通过有限手段运行的通用模型计算机”被“通用图灵机”更换，那么结果：

每个有限可实现的物理系统都可以通过通用图灵机完美地模拟

不是真的。他说的原因是第6.3节结束时讨论的重点，关于非离散物理系统。 Deutsch认为，通用的图灵机“不能完全模拟任何经典动态系统”，因为“[O]机翼到经典动态的连续性，经典系统的可能状态必须形成连续体”，而通用图灵机是一个离散的系统（Deutsch 1985：100）。 Deutsch然后继续介绍一个通用量子计算机的重要概念，说（但没有证据）这是“能够完全模拟每个有限，可实现的物理系统”（1985：102）。

以下制定与Wolfram和Deutsch的论文的细节不同，但可以说可以捕捉两者的精神。鉴于Deutsch-Gandy Point关于连续系统，完美仿真的概念被模拟概念所取代，以任何所需的准确度：

Deutsch-Wolfram论文：

每个有限的物理系统都可以通过通用图灵机模拟任何特定的准确度。（COPELAND＆SHAGRIR 2019）

Earmman 1986年，Pip-El和Richards 1989，PiTowsky 1990，Blum等人获得了相关的身体论文。 1998年和其他人。 Deutsch-Wolfram论文与Gandy的论文M密切相关，并且最大的最大性论文（第5.4节）。事实上，德意志 - Wolfram论文需要后者（但不反之亦然，因为最大雄性论文仅涉及机器，而Deutsch-Wolfram论文涉及所有有限的物理系统的行为 - 虽然任何思考每个有限的物理系统都是计算机会的不同意;看看，Pitowsky 1990）。

Deutsch-Wolfram论文是真的吗？这是一个开放的问题（Copeland＆Shagrir 2020） - 对于弱的最大性论文也是如此。一个辩论的重点是是否存在物理随机性，如果存在，伪造这些论文（Calude等，2010; Calude＆Svozil 2008; Copeland 2000）。但是即使在非随机系统的情况下，猜测即使在至少六十年中延伸，可能存在的真实物理过程（等等，可能是机器操作），其行为既不是通过通用图灵机的可计算也不近似的。例如，参见，例如，Scarpellini 1963，Pour-El和Richards 1979,1981，1981年，1967年，1974年，1982年，Geroch和Hartle 1986，PiTowsky 1990，Stannett 1990，Da Costa和Doria 1991,1994，1994年，塞格尔曼和Sontag 1994，Copeland和Sylvan 1999，Kieu 2004,2006（参见其他互联网资源），Penrose 1994，2011,2011，2016年。

举例来说，选择来自此列表的一篇论文：Pour-El和Richards在1981年的文章中显示，根据熟悉的三维波动方程从可计算的初始条件发展的系统能够表现出伪造德国的行为 - Wolfram论文。但是，现在，它是一个打开的问题，无论这些初始条件是否可以是可能的。

6.4.2“Gandy论点”

Gandy（1980）对其行为无法通过通用图灵机来计算的是否有确定性，离散系统进行了深刻的讨论。现在着名的“甘地论点”旨在表明，考虑到某些合理的物理假设，每个离散确定性机制的行为是通过图灵机来计算的。在某些方面，Gandy的论点类似于并扩展了图灵的论点，并且Gandy将其视为改进和更普遍的图灵的替代品（1980：145）。他强调（与图灵的论点不同），他的论点将“平行致电”（1980：124-5）; 与图灵的相比，这是康迪分析的大部分额外复杂性的额外复杂性。

Gandy观看了他的论点（每个离散确定性机制的行为都是通过图灵机来计算的，如相对优先考虑的，基于设置非常一般的物理假设的设定理论推导（即，四个公理第3.4节中提到。这些假设包括例如机制组件的尺寸上的下限，以及效果和信号传播速度的上限。（该论点旨在涵盖遵循相对性原则的机制。例如，原理III，例如，捕获了机器状态唯一地组装的基本部件类型（原子）的界限的想法; 和原则IV - 哪个甘地称为“局部因果关系原则” - 这是每个状态过渡必须由当地环境确定转型机制的本地环境。

Gandy非常清楚，他的论点不适用于连续系统 - 模拟机，因为他称为非相对论系统。（从未发表的工作提取Gandy，他试图为模拟机制定伴侣论证，包括在Copeland＆Shagrir 2007中。）但是，Gandy论证的范围也有限地限于其他方式，而不是由Gandy本人注意到。例如，一些异步算法落在Gandy原则的范围之外（Gurevich 2012; Copeland＆Shagrir 2007）。 Gurevich的结论是，甘露没有显示“他的公理由所有离散的机械设备满意”，而Sha表现得没有“要求甘地特征有限机械计算的基础”（Gurevich 2012：36，Shagrir 2002：234）。提供一些离散确定性系统的例子将以一种或地，以某种方式避开甘地的结论，即每个这样的系统的行为是通过图灵机可计算的。

首先，如果嵌入在其物理法则具有内容内置的宇宙中，可以从可计算输入的宇宙中产生无可计算的输出的机制，这可能相对较大，但是，如果嵌入在其实际法则，例如，通过时间变量Shagrir 2007）。此外，一些异步算法落在Gandy原则的范围之外（Gurevich 2012; Copeland＆Shagrir 2007）。其次，某些（名义）离散确定性的“相对论计算机”也落在Gandy原则的范围之外。在1987年的PiTowsky（PiTowsky 1990）和1994年和Etesi＆Németi2002中描述了相对论的计算机。该想法在物理系统中的计算过程中概述; 有关进一步讨论，请参阅Shagrir和PiTowsky 2003，Copeland和Shagrir 2020。

Németi相对论计算机利用重力延长效应，以计算（在广义上）通过通用图灵机（例如，暂停函数）可证明不能计算的功能。 Németi和他的同事强调Németi电脑“与目前接受的科学原则”并不冲突“，特别是”量子力学的原则并非侵犯“。此外，他们提出了人类可能会“甚至在未来的某个时候建立相对论的计算机”（Andréka，Németi，＆németi2009：501）。

据甘迪说，

“一个离散的确定性机械装置满足原则I-IV”（他称这个“论文P”; Gandy 1980：126），和

“可以通过满足原理I-IV的设备计算的内容是可计算的”（他标记了这个“定理”）。

图1和2一起将产量：可以通过离散确定性机械装置计算的是（图测机器）计算的。

然而，Németi计算机是离散的，确定性机械设备，但却能够计算不计算机器可计算的功能。也就是说，相对论的计算机是对甘地的论文P的反击性。简而言之，这是因为这种原因是在GANDY的原则上隐含地规定的“确定性”的感觉（“GANDY-MENSTIMISTIC”）较窄直观的“确定性”，确定性系统是一种遵守无随机性或随机性的法律。相对论的计算机是决定性的，但不是GANDY确定的。（对于更全面的讨论，请参阅Copeland，Shagrir，＆Sprevak 2018.）

总之，Gandy的分析对目前对机器计算的理解作出了相当大的贡献。但是，重要和照明虽然甘露的论点是，但德国 - 沃尔弗拉姆论文是否是真实的，它肯定不会解决这个问题。

6.4.3量子效应和“总”论文

德意志 - 沃佛拉姆论文存在更强大的形式，称为槟榔和血清2019年的“总论文”。

总论文：

可以通过通用图灵机来计算任何物理系统的行为的每个物理方面（以任何特定的准确度）计算。

逻辑上，全文由通用图灵机本身反击这是因为没有用于计算通用图灵机器是否在每个给定的输入-1上停止的算法。，没有计算机器行为的那个方面的算法。然而，问题仍然是总体论文是否由任何“更具物理”的系统侵犯，这些系统比环球机器更具“更具物理”。（请注意，这种系统（如果有的话）不一定也侵犯Deutsch-Wolfram论文，因为它可能是可以通过关于系统的某些物理问题的答案，但是系统仍然能够通过图灵机模拟。）

有趣的是，最近的凝聚物量子物理学的工作表明，可能 - 量子多体系可以侵犯总论文。 2012年，Eisert，Müller和Gogolin建立了令人惊讶的结果

确定在重复量子测量中不能发生某些结果序列是否不能发生的非常自然的物理问题是不可行的，即使经典测量的同样问题是容易辨别的。（Eisert，Müller＆Gogolin 2012：260501.1）

这是一个关于一系列巨大戏剧性的窗帘，关于量子阶段过渡，由Cubitt及其团体（Cubitt，Perez-Garcia，＆Wolf 2015; Bausch，Cubitt，Lucia，＆Perez- Garcia 2020; Bausch，Cubitt和Watson 2021）。这些结果涉及“光谱间隙”，是一种物质性质的重要决定因素。如果系统具有高于系统的地面能级的明确限定的下一个能量水平，则据说Quantum许多身体系统是“堵塞”，否则否则被言论为“无透视”（即，如果能量谱是连续的）。 “光谱差距问题”是确定给定的许多身体系统是否被覆盖的问题或无效。

Cubitt等人的无要力结果。源于他们的发现，即在光谱间隙问题中可以编码停止问题。确定他们所研究的类型的模型系统是针对的，或者给定局部相互作用的描述，是“至少像解决停滞问题的那样难以解决”（Bausch，Cubitt，＆Watson 2021：2）。此外，这不仅仅是一种无疑性的情况，无明确概括。即使初始条件是可计算的 Cubitt等人。强调：

即使对于其参数的可计算（甚至代数）值，相位图也是无解扣的

�

。实际上，它在可计数器 - 无限的可计算（或代数）值中是未象征的

�

。（Bausch，Cubitt，＆Watson 2019：8）

但是，Cubitt承认证据中使用的模型有些人为：

结果是否可以扩展到更多的自然模型。（Cubitt，Perez-Garcia＆Wolf 2015：211）

简而言之，它是一个开放和迷人的问题，是否存在未能满足总论文的现实物理系统。

（本章完）