信息（七）

可以定义更复杂的数字系统，并在 4 维和 8 维中推广此类乘法。 Kervaire (1958) 和 Bott & Milnor (1958) 独立证明了基于实数的唯一四个除法代数是 R、C、H 和 O，因此该表全面介绍了定义广度概念的所有可能的代数。对于表中的每个数字类别，可以基于乘法的性质开发单独的信息测量理论。对于可数类 N、Z 和 Q，这些理论等同于图灵等价概念所隐含的标准信息概念。就实数而言，这些理论满足了我们对信息广泛性的直观概念。对于复数，乘法信息效率的概念被破坏了。四元数缺乏交换性，八元数缺乏结合性。这些模型不仅仅是抽象结构，因为代数在我们对自然的描述中发挥着重要作用：

复数用于指定量子物理的数学模型（Nielsen & Cchang 2000）。

四元数对爱因斯坦的狭义相对论也有同样的作用（De Leo 1996）。

一些物理学家认为八元数构成了强力和电磁力统一理论的理论基础（例如，Furey 2015）。

我们简要讨论向量空间在量子物理学中的应用。经典信息以比特为单位来衡量。自然界中比特的实现涉及具有至少两种不同稳定状态和低能量可逆跃迁过程的宏观物理系统（即开关、继电器、晶体管）。在原子水平上存储自然界信息的最基本方法涉及量子位。量子位由两级量子力学系统中的状态向量描述，其形式上相当于复数上的二维向量空间（Von Neumann 1932；Nielsen & Chuang 2000）。在某些情况下，量子算法的复杂性从根本上来说较低（例如，Shor 的整数因式分解算法（Shor 1997））。

定义：量子位或量子位是经典位的推广。量子位的量子态表示为两个正交基向量的线性叠加：

|0⟩=[

1

0

],|1⟩=[

0

1

]

这里使用了所谓的狄拉克或“bra-ket”概念：其中 |0⟩ 和 |1⟩ 发音为“ket 0”和“ket 1”。这两个向量共同构成了计算基础 {|0⟩,|1⟩}，它定义了二维希尔伯特空间中的向量。 n 个量子位的组合由 2n 维希尔伯特空间中的叠加向量表示，例如：

|00⟩=[

1

0

0

0

],|01⟩=[

0

1

0

0

],|10⟩=[

0

0

1

0

],|11⟩=[

0

0

0

1

]

纯量子位是基本状态的相干叠加：

|ψ⟩=α|0⟩+β|1⟩

其中 α 和 β 是复数，约束条件：

|α|2+|β|2=1

通过这种方式，这些值可以解释为概率：|α|2 是量子位值为 0 的概率，|β|2 是量子位值为 1 的概率。

在这个数学模型下，我们对计算作为根据确定性规则对离散对象进行本地、顺序、操作的直觉演变成更丰富的范式：

无限信息实数的引入促进了对无限描述复杂性的对象的操纵，尽管目前没有迹象表明这种表达性在量子物理学中实际上是必要的。

非经典概率 复数促进了更丰富的广泛性概念，其中概率不再是经典的。柯尔莫哥洛夫的第三条公理因概率相互增强或抑制而失去了有效性，从而失去了信息的广泛性。

叠加和纠缠用复杂的高维向量空间表示量子位意味着量子位不再是孤立的离散对象。量子比特可以处于叠加状态，即它们同时处于两种离散状态。量子位波动，从而产生信息。此外，即使信息承载者在空间中相距很远，量子位的量子态也可以关联。这种被称为纠缠的现象破坏了经典计算的局域性（参见量子纠缠和信息的条目）。

从这个分析中可以清楚地看出，在非常小（和非常大）的尺度上描述我们的宇宙涉及到与我们日常生活中的现实体验格格不入的数学模型。让我们理解世界的属性（稳定、离散的物体的存在，在空间和时间上保持其同一性）似乎是一个更加复杂的现实的新兴方面，除了数学公式之外，我们无法理解这个现实。然而，在宏观层面上，宇宙促进了基本过程，例如计数、测量长度和符号操作，使我们能够开发出一致的数学模型层次结构，其中一些模型似乎描述了现实的更深层次的基础结构。

从某种意义上说，四千年前推动美索不达米亚基本会计系统发展的相同数学特性仍然帮助我们深入了解亚原子结构的世界。在过去的十年中，信息似乎已成为物理学中的一个重要概念。 Seth Lloyd 等人（Zuse 1969；Wheeler 1990；Schmidhuber 1997b；Wolfram 2002；Hutter 2010）分析了各种物理系统的计算模型。信息的概念似乎在黑洞分析中发挥着重要作用（Lloyd & Ng 2004；Bekenstein 1994 [OIR]）。 Erik Verlinde (2011, 2017) 提出了一种用信息来分析重力的理论。目前这些模型似乎纯粹是描述性的，没有任何经验验证的可能性。

6. 异常、悖论和问题

信息哲学中的一些基本问题与现有的哲学问题密切相关，另一些则似乎是新的。在本段中，我们讨论了一些可能决定未来研究议程的观察结果。一些相关问题是：

是否存在不包含有关其所指对象的所有信息的唯一标识描述？

计算会创造新信息吗？

构建搜索和系统搜索之间有区别吗？

自弗雷格以来，大多数数学家似乎都相信第一个问题的答案是肯定的（Frege 1879，1892）。 “晨星”和“昏星”的描述与识别金星的程序相关，但它们并不能提供有关该物体本身的所有信息。如果真是这样，那么“黄昏之星”实际上也是“晨星”的发现就毫无意义了。如果我们想维持这个立场，我们就会陷入冲突，因为根据信息论，第二个问题的答案是否定的（参见第 5.1.7 节）。然而，这种观察是非常违反直觉的，因为它意味着我们永远无法在确定性计算的基础上构造新信息，这导致了第三个问题。这些问题围绕着信息哲学的基本开放问题之一：

开放问题 信息与计算之间的相互作用是什么？

如果根据我们已知的信息测量，确定性计算不会产生新信息，我们为什么还要计算呢？这个问题可以改写为：我们应该使用 Kolmogorov 或 Levin 复杂度（Levin 1973、1974、1984）作为我们的基本信息度量吗？事实上，这两种选择都会导致相关但根本不同的信息理论。当使用莱文测度时，计算会生成信息，并且上述三个问题的答案是“是”，而当使用柯尔莫哥洛夫测度时，情况并非如此。这些问题与数学和计算机科学中的许多问题有关。近似、可计算性和部分信息等相关问题也在斯科特域的背景下进行了研究（Abramsky & Jung 1994）。下面我们讨论一些相关的观察结果。

6.1 系统搜索的悖论

信息的本质在于它减少了不确定性。这种观察会导致不透明上下文中的问题，例如，当我们搜索对象时。美诺悖论可以说明这一点（参见认知悖论条目）：

苏格拉底，你如何探究你不知道的事情呢？您将提出什么作为调查主题？如果你找到了你想要的东西，你怎么知道这是你不知道的东西呢？ （柏拉图，美诺，80d1-4）

这个悖论与计算机科学和哲学中的其他开放问题有关。假设约翰正在寻找独角兽。独角兽不太可能存在，因此，根据香农的理论，如果约翰找到独角兽，他就会获得很多信息。然而，从描述性柯尔莫哥洛夫的角度来看，约翰没有获得新信息，因为他已经知道独角兽是什么。系统搜索的相关悖论可以表述如下：

任何可以通过系统搜索找到的信息都没有价值，因为只要有足够的时间，我们就一定能找到它。因此，只有当我们不确定信息的存在时，信息才有价值，但是，由于我们已经知道我们在寻找什么，所以当我们发现它存在时，我们不会得到新的信息。

示例：哥德巴赫在 1742 年猜想，每个大于 2 的偶数都可以写成两个素数之和。直到今天这个猜想仍未得到证实。考虑术语“第一个违反哥德巴赫猜想的数字”。它不会向我们提供有关该号码的所有信息，因为该号码可能不存在。前缀“第一个”确保描述（如果存在）是唯一的，并且它为我们提供了查找数字的算法。它是部分唯一标识描述。这个算法只有当数字确实存在时才有效，否则它将永远运行。如果我们找到了这个数字，这将是个好消息，但从描述复杂性的角度来看，这个数字本身将完全无趣，因为我们已经知道找到它的相关属性。请注意，即使我们有一个数字 n 是哥德巴赫猜想的反例，也可能很难验证这一点：我们可能必须检查几乎所有 ≤n 的素数。这可以有效地完成（我们总是会得到结果），但据我们所知，效率并不高（可能需要“接近”n 个不同的计算）。

一种可能的解决方案是指定约束，即用部分描述来衡量对象的信息内容是非法的，但这会破坏我们的描述复杂性理论。请注意，对象的复杂度是在通用图灵机上生成对象的最短程序的长度。从这个意义上说，“第一个违反哥德巴赫猜想的数字”是对程序的完美描述，它充分衡量了这样一个数字的描述复杂性。简短的描述反映了这样一个事实：如果该数字存在，那么它是非常特殊的，因此它在某些数学背景下出现的可能性很高。

存在着一些经过深入研究的哲学问题的关系，例如安瑟姆对上帝存在的本体论论证和康德的反主张，即存在不是谓词。为了避免类似的问题，罗素建议对独特的描述进行存在性解释（Russell 1905）：像“法国国王是秃头”这样的句子将具有以下逻辑结构：

∃(x)(KF(x)∧∀(y)(KF(y)→x=y)∧B(x))

这种解释无助于我们分析涉及存在的决策问题。假设如果我正在寻找 x，谓词 L 对于 x 为真，那么短语“我正在寻找法国国王”的逻辑结构将是：

∃(x)(KF(x)∧∀(y)(KF(y)→x=y)∧L(x)),

也就是说，如果法国国王不存在，那么我在寻找他就不可能是真的，这是不令人满意的。 Kripke（1971）批评了罗素的解决方案，并提出了他所谓的因果指称理论，其中一个名字通过最初的“洗礼”行为获得了它的指称。然后它成为一个严格的指示符（参见刚性指示符的条目），可以通过因果链追溯到最初的行为。通过这种方式，诸如“约翰是今天早上第四个走出电梯的人”之类的临时描述可以为名称建立语义。

在数学和信息论的背景下，相应的概念是数字的名称、构造谓词和临时谓词。对于任何数字，原则上都会有无数个关于该数字的真实陈述。由于初等算术是不完整的，因此会有一些关于数字的陈述是真实的但无法证明。在极限情况下，数字的消失片段将具有真正压缩其描述的真实谓词。考虑以下陈述：

符号“8”是数字八的名称。

数字 x 是第 1000 个斐波那契数。

数字x是第一个违反哥德巴赫猜想的数字。

第一个语句只是指定一个数字的名称。第二个陈述给出了部分描述，具有建设性、信息压缩性和独特性。第 1000 个斐波那契数有 209 位数字，因此“第 1000 个斐波那契数”的描述比该数的实际名称有效得多。此外，我们有一个算法来构造这个数字。第三条语句中的描述可能并非如此。我们不知道第一个违反哥德巴赫猜想的数字是否存在，但如果存在，则描述很可能是临时的，因此无法为我们提供构建该数字的线索。这引发了这样的猜想：存在数据压缩有效的临时描述：

猜想：存在由非构造性唯一有效描述压缩的数，即给定数可以有效地检查描述的有效性，但不能从描述中有效地构造出数，除非通过系统搜索。

该猜想是所谓的 P 与 NP 命题的更一般的变体（参见第 6.3 节）。如果用“有效”一词替换“有效”一词，就会得到 P≠NP 命题的表述。

6.2 有限集中的有效搜索

当我们将自己限制在有限集合中的有效搜索时，部分描述以及构造与搜索的问题仍然存在。似乎很自然地假设，当一个人有了一组数字的定义时，那么也就拥有了关于该集合的成员及其子集的所有信息，但事实并非如此。一般来说，计算一组数字中的信息量是一个非常重要的问题。我们给出一些结果：

引理集合 S 的子集 A⊂S 可以包含比集合本身更多的以集合为条件的信息。

证明：考虑所有小于n的自然数的集合S。该集合的描述复杂度（以位为单位）为 log2n+c。现在通过随机选择 S 的一半元素来构造 A。观察到：

I(A∣S)=log2(

n

n/2

）

我们有：

林

n→无穷大

我(A∣S)

n

=

林

n→无穷大

log2(

n

n/2

）

n

=1

该集合的条件描述复杂度为：I(A∣S)≈n+c≫logn+c。 ◻

直接的后果是，当我们合并两个集合时，我们可能会丢失信息。更强有力的结果是：

引理：集合的元素可以包含比集合本身更多的信息。

证明：考虑小于 2n 的自然数集合 S。 S 的基数为 2n。该集合的描述复杂度是 logn+c 位，但是对于 S 的一半元素，我们需要 n 位来描述它们。 ◻

在这种情况下，集合本身的描述是高度可压缩的，但它仍然包含不可压缩的元素。当我们合并或拆分数字集，或者添加或删除元素时，对信息量的影响通常难以预测，甚至可能无法计算：

定理：信息在集合理论运算下不是单调的

证明：上述引理的直接结果。 ◻

这表明信息的概念如何渗透到我们的日常生活中。当约翰的口袋里有两个苹果时，他似乎可以用它们做任何他想做的事，但事实上，一旦他选择了两个苹果之一，他就创造了（新的）信息。搜索问题的后果很明显：我们总是可以有效地对集合的元素和子集进行有界搜索。因此，当我们通过部分描述搜索这样一组子集时，结果会生成（新的）信息。从表面上看，这种分析似乎迫使我们接受这样的事实：数学中存在简单的描述，使我们能够通过系统搜索来识别复杂的对象。当我们寻找物体时，我们只有很少的信息，当我们最终找到它时，我们的信息就会增加到有关所搜索物体的完整事实集。这与我们当前的信息理论（香农和柯尔莫哥洛夫）相冲突：任何允许我们通过确定性搜索有效识别对象的描述都包含有关该对象的所有相关信息。搜索过程的时间复杂度就无关紧要了。

6.3 P与NP问题，描述复杂性与时间复杂性

在过去的十年里，数学家们一直在思考一个相关的问题：假设检查我是否找到了我要找的东西很容易，那么找到这样一个物体有多难呢？在数学和计算机科学中，似乎有一类决策问题无法在多项式时间内建设性地解决，即 t(x)=xc，其中 c 是常数，x 是输入的长度），而只能通过系统化求解搜索大部分解空间，这可能需要指数时间，t(x)=cx。这种差异大致与计算上可行的问题与计算上不可行的问题的分离一致。

此类问题存在的问题已被定义为可以在时间多项式中求解的 P 类决策问题与 NP 类问题的输入的可能等价性，其中可以在时间多项式中检查解决方案（Garey & Johnson 1979；另请参阅 Cook 2000 [OIR] 以获得很好的介绍。）

例子： NP 类中一个众所周知的例子是所谓的子集和问题：给定一组有限的自然数 S，是否存在一个子集 S′⊆S 的总和等于某个数字 k？显然，当有人提出这个问题的解决方案 X⊆S 时，我们可以轻松检查 X 的元素加起来是否等于 k，但我们可能必须检查 S 的几乎所有子集才能找到这样的解决方案。

这是所谓决策问题的一个例子。答案很简单“是”或“否”，但可能很难找到答案。观察到以 S 为条件的问题的表述具有描述复杂性 logk+c，而 S 的大多数随机子集具有条件描述复杂性 |S|。因此，任何加起来为 k 的子集 S′ 的描述复杂度可能比搜索问题的公式还要大。从这个意义上说，搜索似乎产生了信息。问题是，如果存在这样的集合，则搜索过程是有界的，因此是有效的，这意味着短语“S 的第一个子集加起来为 k”是一个充分的描述。如果P=NP，那么我们发现集合S′的柯尔莫哥洛夫复杂度和莱文复杂度大致一致，如果P≠NP，那么在某些情况下Kt(S′)≫K(S′)。从不同的角度来看，搜索的理论都会产生新的信息，而搜索的理论则是违反直觉的。

PS与NP问题似乎非常困难，它一直是计算机科学和数学研究的丰富来源，尽管其哲学相关性相对较少。斯科特·亚伦森（Scott Aaronson）的一句话说明了解决方案可能具有深远的哲学影响：

如果p = np，那么世界将是一个与我们通常假设的地方完全不同的地方。 “创造性飞跃”没有特殊的价值，解决问题与解决方案后，没有任何根本的差距。每个能欣赏交响曲的人都是莫扎特。每个可以逐步论证的人都将是高斯……。 （Aaronson 2006 - 在其他互联网资源中）

实际上，如果p = np，则每个具有不太大且易于检查的描述的对象也很容易找到。

6.4模型选择和数据压缩

在当前的科学方法论中

观察：观察现象和有关其原因的询问。

诱导：假设的制定 - 该现象的归一化解释。

推论：实验将测试假设的实验（即，如果为true，请确认它们，如果是错误的，请反驳它们）。

测试：测试假设并收集数据的程序。

评估：对数据的解释和理论的表述 - 绑架了实验结果，是对现象的最合理解释。

在信息理论的背景下，观察集将是一个数据集，我们可以通过观察该数据集中的规律性来构建模型。科学旨在建立我们现实的真实模型。从这个意义上讲，这是一项语义企业。在21世纪，理论形成和测试的过程将通过在大型数据库中自动完成的最大部分。图灵奖得主吉姆·格雷（Jim Gray）将电子科学的新兴学科框架为第四个数据驱动的科学范式。其他是经验，理论和计算。因此，基于数据的自动理论构建过程是科学方法论的一部分，因此是信息哲学的一部分（Adriaans＆Zantinge 1996; Bell，Hey＆Szalay 2009; Hey，Tansley和Tolle 2009）。许多著名的学习算法，例如决策树诱导，支持向量机，归一化信息距离和神经网络，使用基于熵的信息度量来从大数据库中提取有意义且有用的模型。数据库中的学科知识发现的名称（KDD）是大数据研究计划的野心。