信息（五）

5.1.4 用数字衡量信息

我们可以通过未指定的函数i（n）来定义数字n的信息概念。我们观察到添加和乘法指定了多集：两者都是无裁扣，交换性和关联性的。假设我们将张量操作员⊕解释为乘法×。从添加的角度来定义i（m×n）的语义是很自然的。如果我们同时收到消息M和N，则组合消息中的信息总数是单个消息中信息的总和。这导致以下约束：

定义：添加性约束：

i（m×n）= i（m）+i（n）

此外，我们希望更大的数字包含更多的信息，这给出了：

定义：单调性约束：

i（m）≤i（m+1）

我们还希望选择一个一定数量的A作为我们的基本测量单位：

定义：标准化约束：

i（a）= 1

以下定理是由Rényi（1961）引起的：

定理：对数是唯一满足添加性，单调性和归一化的数学操作。

观察：数字n的对数logan表征了我们对数字n中信息概念的直觉。当我们确定1）多组是扩展性概念的正确形式化，而2）乘法是表达添加性的正确操作，那么对数是满足我们约束的唯一测量函数。

我们定义：

定义：对于所有自然数n∈N+

i（n）=洛根。

对于A = 2，我们的测量单位是位

对于a = e（即欧拉的编号），我们的测量单位是GNAT

对于A = 10，我们的测量单位是Hartley

5.1.5 测量数字组中的信息和概率

对于有限集，我们现在可以指定当我们知道设置的某个元素有条件地了解整个集合时获得的信息量。

定义：假设S是有限集，我们有：

e∈S

然后，，

i（eoms）= loga | s |

即，集合的基数日志。

集合越大，搜索越难，当我们找到想要的东西时，我们得到的信息就越多。相反，没有任何进一步的信息，选择S的某个元素的概率是PS（x）=

1

|S|

。相关功能是所谓的Hartley函数：

定义：如果从一个有限集中统一的样本随机选择，则在Hartley函数中给出了结果后揭示的信息（Hartley 1928）：

H0（S）= Loga | S |

这些定义的组合给出了一个定理，将条件信息和概率的概念联系在一起：

统一定理：如果S是有限集，则

i（x s）= h0（s）

关于集合的元素x的信息与集合的条件相等等于我们在统一分布下选择此元素x的概率的日志，如果我们知道集合，这是对我们无知的量度设置将被选择。

观察：请注意，Hartley函数统一了由Boltzmann s = Klogw定义的熵概念，其中W是系统s的微观状态的基数，Shannon信息的概念为（x）= - logp（x） 。如果我们将s视为一组消息，那么我们从集合中选择一个元素x的概率（即，从s中获取消息）在均匀分布下

1

|S|

H0（S）也被称为S的Hartley熵。

使用这些结果，我们将有限集的子集中的条件信息定义为：

定义：如果A是有限集，而B是任意子集B a，则| a | = n和| b | = k我们有：

i（b a）= loga（

n

k

）

这只是我们信息基本定义的应用：A大小为K的亚集的基数是（

n

k

）。

概率概念的形式特性由概率的Kolmogorov公理指定：

定义：p（e）是某些事件E发生的概率P。 （ω，f，p），具有P（ω）= 1，是一个概率空间，带有样本空间ω，事件空间和概率度量。

令P（e）为某些事件E发生的概率P。令（ω，f，p），p（ω）= 1，为一个概率空间，带有样本空间ω，事件空间F和概率度量。

事件的可能性是非负实数

有一个度量单位。事件空间中发生的事件之一的可能性为1：p（ω= 1）

概率是一组独立集合：

P(

无穷大

⋃

我= 1

EI）=

无穷大

Σ

我= 1

P（EI）

后果之一是单调性：如果A⊆B暗示P（a）≤p（b）。请注意，这与为信息概念定义的添加性概念相同。在亚原子级别，添加性的kolmogorov公理失去了其有效性，而有利于更微妙的概念（请参阅第5.3节）。

5.1.6 统一的观点

从哲学的角度来看，这种构建的重要性在于，基于非常有限的公理假设基础，它导致了一个本体论中性的信息概念：

还原学家是从某种意义上说，一旦接受了类和映射等概念，就会自然出现在更复杂的数学概念的背景下，对信息的概念的定义。

从某种意义上说，这是普遍的，即集合的概念是普遍且开放的。

这是语义的意义，即集合本身的概念是一个语义概念。

它在一个连贯的概念框架中统一了各种概念（集合，基数，数字，概率，扩展性，熵和信息）。

从本体学上讲，这是一个中立的，从某种意义上说，集合或阶级的概念并不意味着对其可能成员的任何本体论限制。

这表明了香农的信息理论和鲍尔茨曼的熵概念植根于更基本的数学概念。一组消息或一组微型状态的概念是集合的更通用数学概念的专业知识。信息概念已经存在于这个更基本的层面上。尽管在信息理论与物理学之间的关系中，尤其是在统一信息理论之间的关系中仍然存在许多开放问题，但现在看起来比二十一世纪初更好。

5.1.7 信息处理和信息流动

对数热点中数量中信息量的定义使我们能够根据处理信息的能力对其他数学功能进行分类。函数的信息效率是函数输入中信息量与输出中的信息量之间的差异（Adriaans 2021 [OIR]）。它使我们能够测量信息如何流入一组功能。我们使用速记f（

¯

x

）对于f（x1，x2，…，xk）：

定义：功能的信息效率：让F：NK→N是K变量的函数。

输入信息i（

¯

x

）和

输出信息i（f（f）

¯

x

（））。

表达式f的信息效率（

¯

x

）是

δ（f（f）

¯

x

）= i（f（f）

¯

x

） - i（i

¯

x

）

如果δ（f）

¯

x

））= 0，即，它完全包含其输入参数中的信息量

如果δ（f（f）

¯

x

））＜0和

如果δ（f）

¯

x

）= c。

如果δ（f），则信息正在扩展（f（

¯

x

））＞ 0。

总的来说，确定性信息处理系统不会创建新信息。他们只处理它。以下有关信息与计算之间相互作用的基本定理是由于Adriaans和van Emde Boas（2011）：

定理：确定性程序不会扩展信息。

这符合香农的理论和Kolmogorov的复杂性。确定性程序的结果始终是相同的，因此结果的概率是1，根据香农理论（0个新信息）给出。同样，对于Kolmogorov的复杂性，程序的输出永远不会比程序本身的长度更为复杂，加上常数。 Adriaans和van Emde Boas（2011）对此进行了深入分析。在确定性的世界中，如果以下情况：

程序（输入）=输出

然后

i（输出）≤i（program）+i（输入）

信息的本质是不确定性，而概率为“ 1”的消息不包含任何信息。只要计算停止，计算数字可能需要很长时间的事实是无关紧要的。在Scott领域理论中研究了无限的计算（Abramsky＆Jung 1994）。

估计基本功能的信息效率并非微不足道。原始递归功能（请参阅递归功能的输入）具有一个信息扩展操作，增量操作，一个信息丢弃操作，选择，其他所有信息都是信息中性的。更复杂的操作的信息效率是由计数和选择的组合来定义的。从信息效率的角度来看，基本算术函数是复杂的功能系列，它们描述了具有相同结果但具有不同计算历史的计算。

一些算术操作扩展了信息，有些具有恒定信息和一些丢弃信息。在执行确定性程序的执行过程中，可能会进行信息的扩展，但是，如果程序有效，则输出的描述性复杂性是有限的。信息流取决于操作类型的连续，以及操作的复杂性与变量数量之间的平衡。

我们简要讨论了两个变量及其编码可能性的两个基本递归功能的信息效率：

添加的添加与信息存储有关符号的序列或字符串而言。它是丢弃大于1的自然数的信息。由于log（a+b）＜loga+logb，我们有δ（a+b）＜0。尽管如此，补充仍具有保留质量的信息。如果我们添加具有不同日志单元的数字，我们可以从结果数中重建单元的频率：

232 = 200+30+2

=（2×102）+（3×101）+（2×100）

= 100+100+10+10+10+10+1+1

由于构建块中的信息（100、10和1）仍可以重建数字表示。这意味着自然数在添加K的幂中代码在原理上两种信息：价值和频率。我们可以将此见解用单个自然数字编码复杂的键入信息。基本上，它允许我们以长度⌈logkn⌉的一串符号中的任何自然数进行编码，该符号指定了数字中的信息量的定量度量。有关信息理论的发现系统的重要性的历史分析，请参见第3.3节。

根据定义，乘法是保存信息。我们有：δ（a×b）= 0，因为log（a×b）= loga+logb。仍然乘法并不能保留其输入中的所有信息：操作的顺序丢失。这正是我们想要从一个广泛措施的操作员那里想要的：仅保留数字的广泛品质。如果我们乘以两个3×4的数字，那么结果12使我们能够在原始计算中重建原始计算，因为我们可以将其所有组件减少到其最基本的值：2×2×3 = 12。这导致观察到某些数字充当其他数字的信息构建块，这为我们提供了一个素数的概念：

定义：质数是一个仅由本身分开的数字或1。

素数的概念引起了算术的基本定理：

定理：每个自然数n大于1都是多素的prime的产物，而该多组对于n是唯一的。

算术的基本定理可以看作是有关信息保护的定理：对于每个自然数字，都有一组自然数，其中包含完全相同数量的信息。一个数字的因子形成了所谓的多式：一个可能包含相同元素的多个副本的集合：这使多种集体成为编码信息的强大设备，因为它编码定性信息（即数字2和3）以及定量信息（即数字2仅出现两次，数字3仅一次）。这意味着在繁殖量的繁殖方面，自然数也编码两种类型的信息：价值和频率。同样，我们可以将此见解用单个自然数字编码复杂的键入信息。

5.1.8 信息、素数和因数

基于位置的数字表示使用添加功率是直接且易于处理的，并构成了我们大多数数学功能的基础。基于乘法的编码系统并非如此。数学和信息哲学中的许多开放问题都是在算术和素数基本定理概念的背景下出现的。我们给出简短的概述：

（ir）一组素数的规律性。

由于古代，众所周知，存在无限数量的素数。证明很简单。假设Primes P集是有限的。现在，将p的所有元素和添加1乘。结果数不能除以p的任何成员，因此p不完整。估计质数定理给出的质数密度的估计（请参阅《大不列颠百科全书》中关于质数定理[OIR]的条目）。它指出，n尺寸n的自然数量中的素数大致是lnn，其中ln是基于欧拉的数字e的自然对数。由他在1859年提出的所谓的Riemannn假设给出了密度估计的完善（Goodman and Weisstein 2019 [OIR]），该假设通常被认为是数学中最深的未解决问题，尽管大多数数学家都认为该假设是假设的。真的。

（在）分解效率。

由于乘法可以保存信息，因此函数在一定程度上是可逆的。为某个自然数n寻找独特的素数集的过程称为分解。观察到“仅”在素数的定义中使用术语“仅”意味着这实际上是一个负面的特征：如果没有将其分开的1和n之间的数字，则数字n是素数。这为我们提供了一个数字n分解的有效程序（只需尝试将n除以1和n之间的所有数字），但是这种技术并非有效。

如果我们使用位置系统来表示数字n，则通过反复试验识别n的因素的过程将在最多n试验中采用确定性计算机程序，这在数字表示的长度上给出了计算时间指数⌈logg。通过反复试验和误差的分解相对简单的数字，例如，代码相当小的消息，可以轻松地将整个宇宙大小的计算机轻松占用比大爆炸以来过去的时间更长的计算机。因此，尽管从理论上讲可行，但这种算法是完全不可行的。

分解可能是所谓的陷阱门一对一函数的一个示例，它易于从一侧计算，但在其逆上非常困难。尽管大多数数学家认为问题很困难，但分解是否真的很困难仍然是一个悬而未决的问题。请注意，在此上下文中的分解可以看作是解码消息的过程。如果很难分解，则可以用作加密技术。经典的加密技术（如RSA）基于具有较大质量数量的乘法代码。假设爱丽丝（Alice）的消息编码为一个大数字，她知道鲍勃（Bob）可以使用大型Prime p。她将数字p×m = n发送给鲍勃。由于鲍勃知道p，他可以通过计算M = N/P轻松重建M。由于分解很难，任何其他接收消息n的人都会很难重建m。

原始测试与分解。

尽管目前尚不清楚在古典计算机上进行有效分组的高效技术，但有一个有效的算法为我们决定一个数字是否是素数：所谓的AKS Primations测试（Agrawal等人，2004年）。因此，我们可能知道一个数字不是素数，而我们仍然无法访问其一组因素。

经典 - 量子计算。

理论上使用Shor算法在量子计算机上有效分解（Shor 1997）。该算法具有一个非经典量子子例程，该算法嵌入确定性的经典程序中。可以根据复杂的更高维矢量空间来对量子位的集合进行建模，从原则上讲，这使我们能够分析n个对象集合之间的相关性的指数数2N。目前尚不清楚较大的量子计算机是否足够稳定以促进实际应用，但是量子级别的世界具有相关的计算可能性，不再是疑问，例如，量子随机发生器可以作为商业产品提供（请参阅Wikipedia输入，在硬件随机数生成器[OIR]上）。一旦可行的量子计算机可用，几乎所有当前的加密技术就毫无用处，尽管可以用量子版本代替加密技术（请参阅量子computiong上的条目）。

我们可以对集合n进行无限的观察值，而该集合直接由公理直接暗示，但涉及相当多的计算。

5.1.9 算术不完备性

在1931年的具有里程碑意义的论文中，库尔特·戈德尔（KurtGödel）证明，任何包含基本算术的正式系统从根本上都是不完整的，因为它包含在系统中无法证明的真实陈述。在哲学背景下，这意味着形式系统的语义足以包含基本数学，无法根据系统内的数学功能来定义基本数学，即，有些陈述在良好的意义上包含有关系统的语义信息形成，有意义和真实，没有被证明。

中心是递归功能的概念。 （请参阅递归功能的输入）。这样的功能在数字上定义。戈德尔对递归功能的概念最接近我们在日常生活中与计算相关联。基本上，它们是基本算术函数在自然数上运行的函数，例如加法，减法，乘法和除法以及所有其他可以在这些功能上定义的功能。

我们给出证明的基本结构。假设F是正式系统，具有以下组件：

它有一组有限的符号

它具有一种语法，使我们能够将符号结合到形成良好的公式

它具有一组确定性规则，使我们能够从给定语句得出新的语句

它包含Peano公理指定的基本算术（请参见上面的第5.1.3节）。

此外，假设F是一致的，即，它永远不会得出错误的陈述。在他的证明中，戈德尔利用乘法的编码可能性来构建系统的图像（请参阅Gödel不完整定理的条目中对Gödel编号的讨论）。根据算术的基本定理，任何数字都可以独特地考虑到其素数。这定义了数字和数字的多集之间的一对一关系：数字12可以根据多层{2,2,3}的基础构建，为12 = 2 = 2×2×3，反之亦然。这使我们能够以以下方式将任何符号顺序编码为特定的个体编号：

一个唯一的数字分配给每个符号

素数定位在字符串中的符号的位置

在素数因素集中，相同素数的实际数量定义了符号

在此的基础上，我们可以将任何符号顺序编码为所谓的Gödel编号，例如，数字：

2×3×3×5×5×7 = 3150

代码多式{2,3,3,3,5,7}，该}代表假设a = 1，b = 2下的字符串“ abba”。由于这种观察条件接近导致罗素悖论的观察条件：基本算术本身足以表达：普遍性，否定和自我参考。

由于算术是一致的，这并不会导致悖论，而是导致不完整。通过与骗子悖论戈德尔有关的结构证明，这样的系统必须包含真实但不可证明的陈述：“我不可证明”的形式有真实的句子。

定理：任何包含基本算术的正式系统根本不完整。它包含真实但不可证明的陈述。

在信息哲学的背景下，数学的不完整是自然数量代码信息的丰富可能性的直接结果。原则上，任何确定性形式系统都可以用基本算术函数表示。因此，如果这样的系统本身包含算术作为子系统，则它包含无限的内态链（即自身图像）。这样的系统能够对其自身的功能和证明进行推理，但是由于它在系统中无法构建悖论），因此不需要完整。