信息（六）
5.2 信息和符号计算
递归功能是根据自然数定义的抽象关系。原则上可以定义它们，而无需提及空间和时间。必须将这些功能与我们用于计算它们的操作区分开。这些操作主要取决于我们为它们选择的符号表示的类型。我们可以将数字表示为单位编号||||||，二进制编号111，罗马数字VII或阿拉伯数字7，并且根据我们的选择，可以使用其他类型的顺序符号操纵来计算添加两个添加两个加五是七个，可以表示为：
||+|||||= |||||||
10+101 = 111
II+V = VII
2+5 = 7
因此，我们可以将这四个句子读成相同数学真理的四个句子，或者作为指定四个不同操作结果的陈述。
观察：（至少）有两种不同的观点，我们可以从中研究计算的概念。在这些解释下，符号的语义是不同的。
递归函数范式根据空间和时间外部自然数的抽象功能研究计算。当解释为数学事实时，10 + 101 = 111中的 +符号表示称为添加的数学函数，=符号指定平等。
符号操纵范式根据符号字符串的空间表示的顺序操作研究计算。当被解释为操作时，10 + 101 = 111中的 +符号表示符号操纵的顺序过程的输入，并且=符号指定该操作或输出的结果。这样的算法可能具有以下形式：
10
+101
111
这导致了以下暂定定义：
定义：根据确定性规则，可以将宏观量表上的确定性计算定义为对离散对象的局部，顺序的操纵。
在自然界中，还有许多其他方法可以执行此类计算。可以使用算盘，研究化学过程，或者简单地在海滩上操纵卵石序列。我们操纵的对象是离散的事实，即数据集是自指的观察，这意味着数据域原则上是Dedekind Infinite：
定义：一个集合的无限为deDekind，如果它具有双学位f：s→s'到适当的子集s'。
由于数据元素是离散的，并且有限的数据域将是可数的无限，因此与自然数组相同。
定义：如果有一组自然数n，则无限套件是可计数的。
对于无限可数集，信息的概念定义为如下：
定义：假设s是可数且无限的，函数f：s→n定义了一对一的对应关系，然后：
i（a a，f）= logf（a）
即，给定f中a的索引中的信息量。
请注意，对应F是明确指定的。一旦为现实世界中的一类对象定义了这样的索引函数，就可以将这些对象的操作解释为一种计算形式。
5.2.1 图灵机
一旦我们选择了一组有限的符号，并且我们的操作规则系统开始产生有关世界的陈述。
观察：元句子：
符号“ 0”是零的符号。
指定语义信息与语句e∈A的集合相同（请参见第6.6节）。该声明是完善的，有意义的和真实的。
我们可以在抽象层面上一般研究符号操纵，而没有任何语义含义。这种理论由艾伦·图灵（Alan Turing，1912– 1954年）发表。图灵（Turing）开发了一种一般的计算理论，重点是数学家执行的符号上的实际操作（Turing 1936）。对他来说，一台计算机是一个真正的数学家坐在桌子后面的抽象-Tray（输出）。
图灵首先提出了沿这些线的一般计算理论的概念。他提出了在带有三个符号的无限磁带上操作的抽象机器：空白（b），零（0）和一（1）。因此，图灵机的数据域是一组相关的磁带配置，可以与由零和一个组成的二进制字符串组成。这些机器可以在磁带上读写符号，并且具有在各种条件下决定其动作的过渡功能。在抽象的水平上，图灵机可以像功能一样运行。
定义：如果Ti是带有索引I和X的Turing Machine是零的字符串，并且磁带上的一个字符串作为输入，则Ti（X）表示机器停止后的磁带配置，即其输出。
有无限的图灵机。图灵（Turing）发现，有所谓的通用图灵机UJ可以模仿任何其他Turing Machine Ti。
定义：uj表达式（
¯
钛
x）表示UJ在阅读自我删除描述后，表示计算Ti（X）的结果
¯
钛
机器TJ。
自缩放代码是必要的，因为UJ的输入被编码为一个字符串
¯
钛
X。通用机器UJ分开输入字符串
¯
钛
x进入其两个组成部分：机器的描述
¯
钛
以及该计算机X的输入。
一般计算系统的自指本性使我们能够构建模仿其他机器的机器。这表明可能存在“超级机器”，该“超级机器”模拟所有可能的机器上所有可能的计算并预测其结果。使用一种称为对角线化的技术，其中一个人分析了所有可能的机器在所有可能的机器上运行的机器的枚举，图灵证明了这种机器不存在。更正式：
定理：没有图灵机可以预测任何其他图灵机，无论它是否停止在某个输入上。
这意味着对于某个通用机ui，它在有限时间内停止的一组输入是不可计算的。近年来，还研究了关于图灵机上无限计算的概念（Hamkins和Lewis2000。）并非每台机器都会停止每个输入，而是在某些情况下，无限计算计算有用的输出（考虑数字PI的无限扩展） 。
定义：停止集是图灵机和输入x的组合集，使计算Ti（x）停止。
通用图灵机的存在表明该类体现了通用计算的概念：可以在特定的图灵机上执行的任何计算也可以在任何其他通用图灵机上执行。这是通用可编程计算机概念的数学基础。这些观察结果与信息理论有关：定义了某些信息量度，例如Kolmogorov复杂性，但不可计算。
图灵机类中存在不可兼容的功能的证据与基本算术的Gödel结果不完整结果相似。由于图灵机被定义为研究计算概念，因此包含基本算术。图灵机的类别本身足以表达：普遍性，否定和自我参考。因此，图灵机可以对自己的普遍负面陈述进行建模。图灵的不可及性证明也是出于骗子悖论的动机，而在某个输入上停止的机器的概念类似于某个陈述的证明的概念。同时，Turing Machines满足了Gödel定理的条件：它们可以建模为包含基本Peano算术的正式系统F。
观察：由于它们可以互相模仿，因此递归函数范式和符号操纵范式具有相同的计算强度。可以按定义计算一个可以在一个范式中计算的任何函数。
这种见解可以概括：
定义：如果无限的计算功能与图灵机的通用类具有相同的计算能力，则图丁函数将完成。在这种情况下，它称为图林等效。这样的系统就像图灵机类一样通用：它可以模仿任何可计算的功能。
这种观察的哲学含义是强大而丰富的，不仅是计算理论，而且对于我们对信息概念的理解。
5.2.2 普适性和不变性
通用计算的概念与信息的概念之间存在复杂的评分。恰恰是图灵系统是普遍的事实，使我们可以说它们处理信息，因为它们的普遍性需要不变性：
小型不变定理：字符串x中的信息概念，该X的最小符号的长度是通用图灵机u的程序的最小符号s，以使u（s）= x是不变的，modulo是一个添加剂，在选择下不同的通用图灵机
证明：证明与信息哲学相关。令l（x）为符号x字符串的长度。假设我们有两台不同的通用图灵机UJ和英国。由于它们是通用的，因此它们都可以在输入x上模仿Turing Machine Ti的计算Ti（x）：
UJ（
¯
时间
j
我
x)
英国（
¯
时间
k
我
x)
在这里l（l（
¯
时间
j
我
）是UJ和L上Ti代码的长度（
¯
时间
k
我
) 是 Uk 上 Ti 的代码长度。假设 l(
￣
时间
j
我
x)≪l(
￣
时间
k
我
x)，即 Uk 上的 Ti 代码比 Uj 上的代码效率低得多。观察到 Uj 的代码具有恒定长度，即 l(
￣
U
k
j
)=c.由于英国是通用的，我们可以计算：
英语（
￣
U
k
j
￣
时间
j
我
x)
此计算的输入长度为：
升(
￣
U
k
j
￣
时间
j
我
x)=c+l(
￣
时间
j
我
x)
因此，通用机 Uk 上计算 Ti(x) 的输入规格永远不需要长于常数。 ◻
该证明构成了柯尔莫哥洛夫复杂性理论的基础，最初由所罗门诺夫 (Solomonoff) (1964a,b) 提出，并由柯尔莫哥洛夫 (1965) 和 Chaitin (1969) 独立发现。请注意，这种不变性概念可以推广到图灵完备系统类别：
大不变定理：对于图灵完备系统来说，以计算输入的长度来衡量的信息概念是不变的，以加性常数为模。
证明：假设我们有一个图灵完备系统 F。根据定义，图灵机上的任何计算 Ti(x) 都可以在 F 中模拟，反之亦然。将有一个特殊的通用图灵机 UF 来模拟 F 中的计算 Ti(x)： UF(
￣
时间
F
我
x）原则。
￣
时间
F
我
可能会使用一种非常低效的方式来编写程序，例如
￣
时间
F
我
可以有任意长度。观察 UF 模拟的任何其他通用机 Uj 的代码具有恒定长度，即 l(
￣
U
F
j
)=c.由于 UF 是通用的，我们还可以计算：
超滤(
￣
U
F
j
￣
时间
j
我
x)
此计算的输入长度为：
升(
￣
U
F
j
￣
时间
j
我
x)=c+l(
￣
时间
j
我
x)
因此，通用机 UF 上计算 Ti(x) 的输入规格永远不需要长于常数。 ◻
当我们更详细地分析图灵完备系统的类别时，这个结果有多强就变得清楚了。在二十世纪上半叶，针对一般计算理论提出了三个根本不同的建议：哥德尔的递归函数（Gödel 1931）、图灵的自动机（Turing 1937）和丘奇的 Lambda 微积分（Church 1936）。这些提案中的每一个都以自己的方式阐明了计算概念的各个方面。后来更多的例子接踵而至。图灵等效系统的类别多种多样。除了明显的候选语言（如所有通用编程语言（C、Fortran、Prolog 等））之外，它还包含一些意想不到的元素，如各种游戏（例如，Magic: The Gathering [Churchill 2012 OIR]）。下表概述了一些概念上有趣的系统：
一些图灵完备系统的概述
系统数据域
一般递归函数自然数
图灵机及其泛化符号串
丢番图方程整数
Lambda 演算术语
Type-0 语言 句子
台球计算 理想台球
元胞自动机 一维细胞
康威的生命游戏二维细胞
我们做了以下几点：
观察：图灵等价系统的类是开放的，因为它是根据计算之间的纯粹操作映射来定义的。
这一观察的直接结果是：
观察：完整图灵机类定义的计算和信息的一般理论在本体论上是中立的。
除了计算系统和数据域是一般数学运算和结构这一事实之外，不可能得出计算系统和数据域的任何必要品质。图灵等价系统定义的数据域不一定是物理的、时间的、空间的、二进制的或数字的。任何时候都可以引入班级的新成员。我们知道有些计算系统比图灵机类（例如常规语言）更弱。我们不能排除有一天我们会遇到一个更强大的系统的可能性。这种系统不存在的论点被称为丘奇-图灵论（参见丘奇-图灵论）：
丘奇-图灵论文：图灵机类别准确地描述了算法计算的概念。
我们概述了支持和反对该论文的论点：
支持该论文的论据：图灵机理论似乎是我们可以制定的最普遍的理论，因为它基于关于计算是什么的一组非常有限的假设。它的普遍性这一事实也表明了它的普遍性。很难想象一个更强大的系统在什么意义上可以“更”普遍。即使我们可以想到这样一个更强大的系统，这样一个系统的输入和输出也必须是有限和离散的，并且计算时间也是有限的。因此，最终，任何计算都将具有有限数据集之间的有限函数的形式，并且原则上，所有此类关系都可以在图灵机上建模。到目前为止，我们定义的所有已知计算系统都具有相同的能力，这一事实也证实了这一论点。
反对该论文的论点：该论文目前的形式是无法证明的。图灵完备系统类别是开放的。它是在已知系统之间存在等价关系的基础上定义的。从这个意义上说，它并没有本质上定义计算的概念。它并没有为我们提供一个哲学理论来定义计算到底是什么。因此，它不允许我们从先验类别中排除任何系统。任何时候都可能会出现一种从根本上来说更强大的计算概念提案。更重要的是，大自然以量子计算的形式为我们提供了更强大的计算概念。量子比特实际上是与符号操作相关的比特的正常概念的概括，尽管最终量子计算似乎并不需要我们重新定义迄今为止的计算概念。我们永远不能排除物理学、生物学或化学方面的研究将定义迫使我们这样做的系统。事实上，许多作者都提出了这样的系统，但目前在令人信服的候选人方面尚未达成共识（Davis 2006）。 Dershowitz 和 Gurevich (2008) 声称已经证实了这一假设，但这一结果并未被普遍接受（参见其他互联网资源 [OIR] 中关于“可计算性——反驳丘奇-图灵论文意味着什么”的讨论） 。
对于（正式）系统来说，图灵完备似乎是一个非常自然的条件。任何足够丰富来表示自然数和基本算术运算的系统都是图灵完备的。所需要的是在一组离散的有限数据元素上定义的有限操作集，该操作集足够丰富以使系统自引用：其操作可以由其数据元素来描述。这在一定程度上解释了为什么我们可以使用数学来描述我们的世界。计算的抽象概念被定义为抽象世界数学中数字的函数，而我们周围的日常世界中通过操作对象进行计算的具体概念是一致的。递归函数范式和符号操作范式所隐含的信息端计算的概念是相同的。
观察：如果人们接受丘奇-图灵论点是开放的这一事实，这意味着关于信息的普遍概念是否存在的问题也是开放的。在研究的现阶段，不可能指定这种一般理论的先验条件。
5.3 量子信息及其他
我们对经典计算的概念有了合理的理解，但量子物理学对计算和信息的影响可能会决定未来几十年甚至更长的哲学研究议程。但很明显，这项研究对传统哲学立场产生了影响：认为宇宙本质上是决定论的拉普拉斯观点（Laplace 1814 [1902]）似乎被经验观察所证伪。量子随机发生器是商业上可用的（参见维基百科有关硬件随机数发生器 [OIR] 的条目），并且量子涨落确实会在宏观尺度上影响神经、生物和物理过程（Albrecht & Phillips 2014）。我们的宇宙实际上是一个永久生成信息的过程。经典的确定性计算似乎是一个太弱的概念，无法理解其结构。
宏观尺度上的标准计算可以定义为根据确定性规则对离散对象进行局部、顺序的操作。 Is 在自然数集 N 的运算中具有自然的解释，并且在对数运算 log:N→R 中具有自然的测量函数，将实数与每个自然数相关联。该定义为我们提供了可数无限集的充分信息度量，包括像整数 Z（在减法下封闭）和有理数 Q（在除法下封闭）这样的数字类。
与相关对数函数的乘法运算准确地表征了我们对信息概念的可加性的直觉。它导致自然数集 N 和数字多重集（即质因数集）之间的自然双射。多重集的概念与交换性和结合性的性质相关。当我们研究更高维度的除法代数时，这个程序可以扩展到其他类型的数字。下表概述了一些相关的数字类别以及这些类别的乘法运算的属性：
数类符号维数可数线性交换结合律
自然数 N 1 是 是 是 是
整数 Z 1 是 是 是 是
有理数 Q 1 是 是 是 是
实数 R 1 否 是 是 是
复数 C 2 否 否 是 是
四元数 H 4 否 否 是
八元数 O 8 否 否 否
该表按照通用性不断增强的原则进行排序。从自然数集合 N 开始，考虑到减法 Z 和除法 Q 下的闭包，各种扩展是可能的。对于这些数类，我们在宏观尺度上有足够的有限符号表示。对于实数 R 的元素，这样的表示不可用。实数 R 引入了在一次操作中操纵无限量信息的方面。
观察：对于几乎所有 e∈R，我们有 I(e)=∞。
当我们引入虚数作为负平方 i2=−1 时，可以定义更复杂的除法代数。我们现在可以定义复数：a+bi，其中a是实部，bi是虚部。复数可以解释为二维平面中的向量。因此，它们缺乏符号之间严格线性顺序的概念。加法非常简单：
(a+bi)+(c+di)=(a+b)+(c+d)i
乘法遵循正态分布规则，但结果不太直观，因为它涉及 i2 生成的负项：
(a+bi)(c+di)=(ac−bd)+(bc+ad)i
在这种情况下，乘法不再是纯粹的扩展运算：
