AIT 中的信息与熵

作者: LostAbaddon | 来源:发表于2020-02-04 02:28 被阅读0次

我们可以将图灵机定义为这么一种特殊的函数 $T$ ：

$T(a) = \{s, b\}$

其中，如果 $T$ 接受输入参数 $a$ ，则 $s = 0$ ，且 $b$ 为图灵机输出结果；
如果 $T$ 拒绝输入参数 $a$ ，则 $s = 1$ ，且 $b$ 可以是任意值；
如果 $T$ 在输入参数为 $a$ 时不停机，则 $s = 2$ ，且 $b$ 可以是任意值。

下面，用 $\Sigma$ 代表字符集（数量为 $\sigma$ ），而 $\Gamma = \Sigma ^*$ 为所有可能字符串构成的集合。这样，我们就可以就可以建立等价类：

$C_T = \left\{ X | \forall s \in \Gamma: X(s) = T(s) \right\}$

也就是说，图灵机 $T$ 的等价类中的元素，在任意输入参数下的返回都和 $T$ 相同。

任意图灵机 $T$ 都有两个特征值，一个是长度 $L(T)$ ，即在选定语言中 $T$ 的字符数；另一个是序号 $I(T)$ ，它给出了在选定语言中代表 $T$ 的字符串对应的编码值，是一个整数，且任意两个不同的字符串的序号值不同，这个常见的编码方法就可以是哥德尔数。

因此，现在在这个等价类中，我们可以选择一个“代表”，被称为最简图灵机，它是整个等价类中长度最小的所有图灵机中序号最小的那个，记为 $M(T)$ 。

于是，我们可以构建一个集合，它是所有最简图灵机构成的集合，记为 $\mathrm{MT}$ 。

对任意一个图灵机构成的集合 $G$ ，我们可以构造它的“最简集” $\mathrm{M}(G)$ ，满足：

$\forall T \in G: M(T) \in \mathrm{M}(G)$
$\forall T \in \mathrm{M}(G): \exists R \in G : M(R) = T$

这样构造出来的最简集与原集从“功能”的角度看是完全一样的。

我们可以给出任意一个图灵机构成的集合 $G$ 的两个最常用的属性：

$\mathrm{cnt}(G) = |\mathrm{M}(G)|$ ，也即 $G$ 的最简集的元素数量；
$\mathrm{ave}(G) = \frac{\sum_{T \in \mathrm{M}(G)} |T|}{\mathrm{cnt}(G)}$ ，也即 $G$ 的最简集中元素的平均长度。

$\mathrm{MT}$ 中的图灵机 $M$ ，如前所述，可以视为一种特定的函数，我们可以将其简化为偏函数：

$M(s) = r$

$M$ 的所有可接受参数构成的集合称为 $M$ 的语言 $\mathrm{lang}(M)$ ，而其所有输出构成的集合称为 $M$ 的表达 $\mathrm{expr}(M)$ 。显然“最简”这一要求不能保证任意两个最简图灵机的语言与表达不会相等。

而MRDP定理则告诉我们，对任意图灵机 $M$ 总能找到一个丢番图集 $P$ 使 $\mathrm{lang}(M) = P$ ，反之亦然。

下面，我们来看联合映射：

$T_1 (T_2 (s)) = r$

如果有：

$\forall s \in \mathrm{lang}(T_2) \cup T_2(s) \in \mathrm{lang}(T_1): M(s) = T_1 (T_2 (s)) \cup \mathrm{lang}(M) = \mathrm{T_2} \cup \mathrm{expr}(M) = \mathrm{expr}(T_1)$

则称 $M$ 是 $T_1$ 与 $T_2$ 的联合映射，或说 $M$ 可分解为 $T_1$ 与 $T_2$ （注意是有序的），记为：

$M = T_2 \oplus T_1$

这样的 $M$ 也称为是“可分解”的。一般联合映射后的表达会是联合映射中第一个图灵机的表达子集（但未必是真子集）。

显然我们可以得出一个三角不等式：

$M = A \oplus B \Rightarrow L(M) \leq L(A) + L(B)$

联合映射当然也可以不是两次的：

$M = \bigoplus \{ T_i | i = 1 ... n\} = T_n \oplus ... \oplus T_1$

同样的，也就有了如下不等式：

$M = \bigoplus \{ T_i | i = 1 ... n\} \Rightarrow L(M) \leq \sum_{i=1}^n L(T_i)$

有了联合应用，我们就可以构造两个图灵机构成的集 $A$ 与 $B$ 之间的这么一种特殊的关系：

$B \triangleright A = A \triangleleft B \leftrightarrow\forall T \in A: \exists G \subset B^*: T = \bigoplus G$

于是，我们就可以得到任意图灵机构成的集合 $G$ 的一个“最小不可分解最简图灵机集”，记为 $\mathrm{MM}(G)$ （如果 $G$ 是所有图灵机构成的集合 $\mathrm{AT}$ 或 $\mathrm{MT}$ ，则记为 $\mathrm{MMT}$ ），它是所有满足 $A \triangleright G$ 的集合中元素最少的中平均长度最小的那个。以及还可以定义 $G$ 的“最短不可分解最简图灵机集”，记为 $\mathrm{SM}(G)$ （对 $\mathrm{AT}$ 与 $\mathrm{MT}$ 记为 $\mathrm{SMT}$ ），它是所有满足 $A \triangleright G$ 的集合中总长度（ $\mathrm{cnt}(A) \times \mathrm{drt}(A)$ ）最小的中平均长度最小的那个。

最后，我们可以定义一个图灵机集 $G$ 的拓张为 $\mathrm{ext}(G) = \mathrm{M}(\{ T | \exists l \in G^* : T = \bigoplus l \})$ 。

我们感兴趣的是在任意图灵机构成的集合 $G$ 中两个字符串之间的关系。

图灵机的输入与输出当然可以不只是一个字符串，甚至都可以不是字符串，但我们总可以通过恰当的编码，让它的输入与输出各用一个字符串就可以表达了。

如果 $M \in G$ 、 $i \in \Gamma$ 、 $o \in \Gamma$ ，且满足 $M(i) = o$ ，则称“ $i$ 通过 $M$ 生成了 $o$ ”，记为 $i \Rightarrow_M o$ ；或者可以简称“ $i$ 生成了 $o$ ”，或“ $o$ 被 $i$ 生成了”，记为 $i \Rightarrow o$ 。

现在，我们可以建立五个集合：

集合 $\mathrm{expr}(o) = \{ i | \exists M \in G: M(i) = o \}$ 为字符串 $o$ 的表达集；
集合 $\mathrm{gen}(i) = \{ o | \exists M \in G: M(i) = o \}$ 为字符串 $i$ 的生成集；
集合 $\mathrm{in}(o) = \{ M | \exists r \in \Gamma: M(i) = o \cup M \in G \}$ 为字符串 $o$ 的表达链集；
集合 $\mathrm{out}(i) = \{ M | \exists o \in \Gamma: M(i) = o \cup M \in G \}$ 为字符串 $i$ 的生成链集；
集合 $\mathrm{conn}(i, o) = \{ M | M \in \mathrm{ext}(G) \cup M(i) = o \}$ 为字符串 $i$ 与 $o$ 的链集。

于是，我们可以这么来定义两个字符串在 $G$ 中的“距离”：

$D(i, o) = \min \left( \{ L(M) | M \in \mathrm{conn}(i, o) \} \right)$

而我们常见的目标字符串的算法熵 $K(s)$ 则可以定义为：

$k(s) = \min \left( \{ D(r,s) + |r| + C_L | r \in \mathrm{expr}(s) \} \right)\\ K(s) = \min(k(s), |s|)$

其中 $C_L$ 是一个语言决定的、与函数调用参数相关的常数。

很显然，将 $G$ 限定为所有图灵机构成的集合 $\mathrm{AT}$ 与限定为 $\mathrm{MT}$ 的结果是一样的，但限定在 $\mathrm{IMT}$ 上则可能产生不同的结果，因为可分解图灵机 $M = T_1 \oplus T_2$ 的长度可能比 $T_1$ 与 $T_2$ 的长度合更小，而不可压缩表示可能会通过一个可分解图灵机来获得目标字符串。

显然，如果 $r \Rightarrow_M s$ ，则有 $K(s) \leq K(r) + L(M) + C_L$ 。

我们可以通过 $k(s)$ 来构造这样两个集合：

$\mathrm{kerS}(s) = \{ r | \exists T \in G: |r| + L(T) = k(s) \}\\ \mathrm{kerT}(s) = \{ T | \exists r \in \Gamma: |r| + L(T) = k(s) \}$

我们当然期望这两个集合都只有一个元素，但一般而言这是未必的。而且，更糟糕的是，根据 Chaitin 不完备性，当 $s$ 足够长时，上述这两个集合甚至都是不可计算的。当然，这并不妨碍我们形式地研究它们。

假定 $r \Rightarrow_T s$ ，则有四类 $(r,T)$ 二元组最值得关注：

第一类 $\mathrm{S_1}(s)$

$l(s) = \min \left( \{ |r| | r \in \mathrm{expr}(s) \} \right)\phantom{wwwwwwwwwwwwww}\\ A(s) = \{ r | |r| = l(s) \}\phantom{wwwwwwwwwwwwwwwwwwwi}\\ B(s) = \bigcup_{r \in A(s)}\mathrm{conn}(r,s)\phantom{wwwwwwwwwwwwwwwwww}\\ m(s) = \min \left( \{ L(T) | T \in B(s) \} \right)\phantom{wwwwwwwwwwwww}\\ \mathrm{S_1}(s) = \{ (r, T) | T(r) = s \cup r \in A(s) \cup L(T) = m(s) \}$

第二类 $\mathrm{S_2}(s)$

$l(s) = \min \left( \{ L(T) | T \in \mathrm{in}(s) \} \right)\phantom{wwwwwwwwwwwwi}\\ A(s) = \{ T | L(T) = l(s) \}\phantom{wwwwwwwwwwwwwwwwi}\\ B(s) = \{ r | T \in A(s) \cup T(r) = s \}\phantom{wwwwwwwwwwwi}\\ m(s) = \min \left( \{ |r| | r \in B(s) \} \right)\phantom{wwwwwwwwwwwwww}\\ \mathrm{S_2}(s) = \{ (r, T) | T(r) = s \cup T \in A(s) \cup |r| = m(s) \}$

第三类 $\mathrm{S_3}(s)$

$l(s) = \min \left( \{ |r| | r \in \mathrm{kerS}(s) \} \right)\phantom{wwwwwwwwwwwwww}\\ A(s) = \{ r | |r| = l(s) \}\phantom{wwwwwwwwwwwwwwwwwwai}\\ B(s) = \bigcup_{r \in A(s)}\mathrm{conn}(r,s)\phantom{wwwwwwwwwwwwwwwwww}\\ m(s) = \min \left( \{ L(T) | T \in B(s) \} \right)\phantom{wwwwwwwwwwwww}\\ \mathrm{S_3}(s) = \{ (r, T) | T(r) = s \cup r \in A(s) \cup L(T) = m(s) \}$

第四类 $\mathrm{S_4}(s)$

$l(s) = \min \left( \{ L(T) | T \in \mathrm{kerT}(s) \} \right)\phantom{wwwwwwwwwww}\\ A(s) = \{ T | L(T) = l(s) \}\phantom{wwwwwwwwwwwwwwwwi}\\ B(s) = \{ r | T \in A(s) \cup T(r) = s \}\phantom{wwwwwwwwwwwi}\\ m(s) = \min \left( \{ |r| | r \in B(s) \} \right)\phantom{wwwwwwwwwwwwww}\\ \mathrm{S_4}(s) = \{ (r, T) | T(r) = s \cup T \in A(s) \cup |r| = m(s) \}$

每一类都有可能有不止一个元素。而且当 $G$ 包含无需输入就能输出目标字符串的特殊图灵机（同时显然也是常映射图灵机）时， $\mathrm{S1}(s)$ 显然就很特殊，因为其中的字符串为空，而其中的图灵机是这类常映射图灵机中最短的那个。

下面，我们就要来看这么一个乍看起来很无聊的问题：

字符串的信息到底在哪里？

字符串的信息到底在哪里？

这个问题看起来很无聊。

算法熵 $K(s)$ 同时也叫不可压缩长度，它代表能生成目标字符串的所有可能方法中最短（算法长度加上输入参数长度）的那个方法的长度，所以看起来是非常适合作为目标字符串 $s$ 的信息量的度量的。

但这个看法显然是错的，因为我们都知道任意毫无信息可言的白噪音 $b$ 的算法熵等于 $|b|$ ，也噪音的长度等于噪音的算法熵。因此，如果字符串的信息量等于它的不可压缩长度，那相等长度的字符串中真随机的噪音的信息量居然就变成“最大”的了，这显然不合理。

另一个想法，就是用 $|s| - K(s)$ 来表示目标字符串 $s$ 的信息量，这样噪音的信息量自然就是 0 了，看起来很合理，但一样经不起推敲：n 个相同的字符构成的字符串，与拥有 n 个字符的诗歌相比，前者的 $K(s)$ 显然可以更小，从而难道 n 个相同字符构成的字符串比 n 个字符构成的诗歌拥有更多的信息么？显然也不合理。

因此，我们需要新的方法来度量一个字符串的信息量，以及，可能还需要重新定义以下它的“熵”。

有必要把我们所面对的对象重新定义一下。

我们现在有一个字母表 $\Sigma$ ，一个由字母表构成的字符串所构成的集合 $\Gamma \subset \Sigma ^*$ ，还有一个建立在 $\Sigma$ 上的图灵机所构成的集合 $G_0$ ，它可以是全部图灵机构成的集合，也可以只是一部分图灵机构成的集合。

接着，我们定义 $G = \mathrm{MM}(G_0)$ 或 $G = \mathrm{SM}(G_0)$ ，也即上述图灵机集 $G_0$ 的最小最简集或最短最简集，并定义图灵空间为 $S = \left< \Gamma, G \right>$ ，其中 $G$ 称为该空间上的图灵结构， $\Gamma$ 为底空间。

在这个离散的图灵空间中，图灵结构中的元素能将 $\Gamma$ 的两个子集 $A$ 与 $B$ 映射起来，且不同的元素给出了不同的映射方式，不可能有两个元素彼此同构。

因此，很显然图灵空间是一张有向图，图灵结构是所有边的集合，底空间则给出了所有点，生成关系给出了一条链接两个点的有向边，而该有向图允许有环，链接两点的边也允许有不止一条。

所有，一个点的表达集，就是它的一阶入邻点集，生成集就是一阶出邻点集，表达链集是一阶入边集，生成链集是一阶出边集。我们可以定义路径为一个由首尾相连的边构成的有序集，那么链集就是链接给定首尾两点的所有路径的集合。

在图灵空间这张有向图中，我们有一个很自然的不等式：

$L(A \oplus B) \leq L(A) + L(B) + C_L$

所以，不妨将边长定义为：

$\mathrm{Arc}(T) = L(A) + C_L$

这样，两点之间的距离（上面定义过的 $D(r,s)$ ）就可以重定义为：

$D(r,s) = \begin{cases} 0\phantom{wwwwwwwwwwwwwwwwwwa}r = s\\ \min\left(\{\mathrm{Arc}(T) | T \in \mathrm{conn}(r,s)\}\right)\ \ \ \ r \not = s \end{cases}$

这样定义的距离函数其实并不能算是标准意义上的距离，因为一般而言并不满足对称性要求（ $D(r,s) = D(s,r)$ ），但却显然满足三角不等式，所以可以称之为“弱距离”。

在 Finsler 几何中，如果不要求 Finsler 度量函数具有强一致性，那就等于是放弃了对称性要求，此时的 Finsler 几何就被称为“弱 Finsler 几何”。

因此，现在图灵空间 $\left< \Gamma, G \right>$ 上可以说很自然地就有了一个弱度量结构，同时也是一张有向图。

我们下面来关注在任意给定点附近的结构——由于图灵空间是离散的，所以我们下面所谈论的只能算是小范围结构，而不能说是微观结构。

在 $\left< \Gamma, G \right>$ 上我们可以构造路径 $p = \{T_i\}$ ，它是一组有向边构成的序列，其每一条边的起点必须是上一条边的终点。这样，第一条边的起点就称为该路径的起点，最后一条边的终点就是该路径的终点，路径包含的边的数量被称为路径的跨度，记为 $|p|$ ；而路径所包含的边的长度（上一段定义的距离函数）之和，被称为该路径的弧长，记为 $\mathrm{Arc}(p)$ 。

对于空间中任意两个给定点 $r$ 与 $s$ ，可以构造集合 $\mathrm{Path}(r,s)$ 为所有从 $r$ 到 $s$ 的路径的集合。其中路径跨度的最小值被称为 $r$ 到 $s$ 的层距（ $L(r,s)$ ），相应的路径被称为“最短路径”（可能不止一条）；路径弧长的最小值被称为 $r$ 到 $s$ 的距离（ $D(r,s)$ ），相应的路径被称为“最近路径”（也可能不止一条）。某些一些情况下，两点之间的最短路径和最近路径可以不重合。我们把最短路径记为 $P_m (r,s)$ 而最近路径记为 $P_s (r,s)$ 。

这里与上一段定义的距离虽然看起来有一点小差异，但实际结果是一样的。

最短路径有一个很不错的性质，那就是路径中间任意一点到路径终点的最短路径，必然是这条最短路径的一部分；而从起点到任一点的最短路径，必然也是这条最短路径的一部分。对于最近路径也有类似的结论，只不过把“最短”都换成“最近”而已。

但，最近路径上各端的弧长，就没有这么美好的性质了。如果将计算最短路径上的点依次到终点的距离，我们会发现这个序列可能都不是单调不增的。

因此，我们可以独立使用最短路径或最近路径来构造一些重要的量，而不混合使用。

如果对于任意点 $s$ ，它的最短路径上的点到它的距离是单调减的，且它的最近路径上的点到它的层距也是单调减的，那我们就称这个图灵空间是良性的。
显然，并不是任意图灵空间都是良性的，良性图灵空间只是一小部分。

我们也将到 $s$ 的层数为 n 的节点构成的集合，称为 $s$ 的 n 阶入邻点集 $\mathcal{NI}_i(s)$ ，而从 $s$ 出发层数为 n 的节点构成的集合，称为 $s$ 的 n 阶出邻点集 $\mathcal{NO}_i(s)$ 。容易知道， $\mathcal{NI}_{i+1}(s)$ 中的节点必然是 $\mathcal{NI}_i(s)$ 中至少一个节点的 1 阶入邻点，对出邻也是如此。尤其，我们将一阶入邻点数记为 $N_I(s)$ 而一阶出邻点数记为 $N_O(s)$ 。

最后，我们为图灵空间引入一个很自然的“势能场”，它就是每个点对应的字符串的长度——这个标量场的引入很自然，不需要额外的附加结构。

因此，现在图灵空间上有度量结构、有势能场、是一张有向图。

现在，任意两个点 $r$ 与 $s$ 之间所有可能的路径构成了一个路径集，记为 $\mathrm{Path}(r,x)$ ，它的每一个元素都是一台特殊的图灵机，由一组不可分解的最简图灵机联合构成。

我们可以将路径 $P$ 记为一组图灵机的序列 $\{T_i\}$ ，从而 $P(r) = T_n ( T_{n-1}(...T_2 ( T_1(r))...))$ 。

假定 $P_1$ 从 $r$ 连到 $x$ ，而 $P_2$ 从 $x$ 连到 $s$ ，那 $Q = P_1 \oplus P_2$ 就是从 $r$ 先沿 $P_1$ 到 $x$ 再沿 $P_2$ 连到 $s$ 的路径。这样的操作就是路径的合并。

另一方面，路径是由起点、终点加上一组图灵机序列构成的，我们可以给出一个有序点列 $\mathrm{Route}(r,x,p)$ 与之对应：

$\mathrm{Route}(r,s,p) = (r, x_1...x_{n-1}, s)\\ x_i = T_i ( T_{i-1} ( ... T_1(r)...))$

因此，一条路径上可能存在这样的结构：它对应的有序点列种，存在两个不同顺位上的点是相同的，这意味着在这两个点之间存在一个环结构。我们可以将这部分图灵机扣除，等价于将所有环状结构都剪除。

经过上述剪除后，我们得到一组包含 $n + 1$ 个点得序列，接着我们可以使用连接第 $i$ 与 $i+1$ 个点的最近路径（按照路径的定义，这样得到的最近路劲必然是图灵结构中的元素）来作为新路径中的第 $i$ 个元素，从而得到一条新路径。

第三步，我们要求新的路径集中任意一条路径，它上面的点到终点的距离必须是单调减的，这样就可以排除大量在外面“徘徊”的无效路径。

经过上面三步操作后，我们就从路径 $p$ 得到了一条去掉环的最简路径 $q$ ，这个操作可以称为“正规化”： $q = \mathrm{NP}(p)$ 。而如果只进行前两步而不作最后一步，则成为“半正规化”： $q = \mathrm{SNP}(p)$ 。

因此，从 $r$ 到 $s$ 的路径集 $\mathrm{Path}(r,s)$ 可以被映射为正规化路径集 $\mathcal{NP}(r,s)$ 与半正规化路径集 $\mathcal{SNP}(r,s)$ 。

下面，我们可以来看点 $r$ 对点 $s$ 的“作用”是怎么样的。

我们可以取连接 $r$ 对 $s$ 的路径 $p$ 的作用量为：

$\mathrm{S}(p) = \exp \left[ - h D(p) \right]$

其中 $h$ 是一个全局常数。

而 $r$ 对 $s$ 的作用不依赖路径，所以我们要设法去掉这里路径的影响。方法有四种：

$\begin{cases} \mathrm{act}_K(r,s) = \mathrm{S}(r,s;P_s(r,s))\\ \mathrm{act}_A(r,s) = \sum_{p \in \mathrm{Path}(r,s)} \mathrm{S}(r,s;p)\\ \mathrm{act}_N(r,s) = \sum_{p \in \mathcal{NP}(r,s)} \mathrm{S}(r,s;p)\\ \mathrm{act}_S(r,s) = \sum_{p \in \mathcal{SNP}(r,s)} \mathrm{S}(r,s;p) \end{cases}$

由于对于最近路径存在三角不等式，且最近路径上的点能分解为两段最近路径，但任意路径上点依次到终点的层距一般不会是单调减的，所以我们有：

$\mathrm{act}_A(r,s) \geq \mathrm{act}_S(r,s) \geq \mathrm{act}_N(r,x) \geq \mathrm{act}_K(x,s)\ \ \ \ \forall x,s \in \Gamma\phantom{wwwwwwwi}\\ \mathrm{act}_A(r,s) = \sum_{x \in \mathcal{NI}_1(s)} \mathrm{act}_A(r,x) \mathrm{act}_A(x,s) = \sum_{x \in \mathcal{NO}_1(r)} \mathrm{act}_A(r,x) \mathrm{act}_A(x,s)\ \ \\ \mathrm{act}_N(r,s) = \sum_{x \in \mathcal{NI}_1(s)} \mathrm{act}_N(r,x) \mathrm{act}_N(x,s) = \sum_{x \in \mathcal{NO}_1(r)} \mathrm{act}_N(r,x) \mathrm{act}_N(x,s)$

这里值得注意的是，除非选定的图灵空间是良性的，否则上面两个等式的求和范围不能从 1 阶入邻点集推广到任意 n 阶入邻点集，因为在非良性图灵空间中，层距随距离不是单调减的，所以n阶入邻点集中的两个甚至多个不同点就有可能会出现在 $\mathcal{Path}$ 中的某些路径上，造成求和的时候这些路径被多次求和，造成等式右侧比左侧要多出来一些多次求和的路径的作用量。但对于 $\mathcal{Path}$ 中的路径，在 1 阶入邻点集上则没有这个问题，所以等式依然成立。

另一方面，只要常数 $h$ 非常大，此时非最近路径的作用量会快速衰减为 0，所以此时 $\mathrm{act}_A$ 与 $\mathrm{act}_K$ 可以认为相等，否则 $\mathrm{act}_A$ 比 $\mathrm{act}_K$ 大。

在进一步讨论信息与熵之前，我们需要进一步看看这组作用量之间的关系。

我们先来看 $\mathrm{act}_A$ 与 $\mathrm{act}_S$ 的关系。

两者之间的区别，就是后者将前者可能存在的环状结构都抹去了，且原本路径上相邻两点之间可能存在大量非最近连接，现在都被约化为最近连接。

我们可以作一个简化（虽然很不切实际）：每一点上可能存在的环状结构都是相同的（平均环假设）。

这个简化在环不长的时候几乎总是成立的，但随着环本身跨度的增加，这一简化很快就会失效。但我们先简化为这个条件是可以满足的。

在平均环条件下，我们假定所有能通过去环操作简化到路径 $p$ 的路径构成的集合为 $LP$ ，这样就可以给出后者的总作用与前者作用之间的关系：

$\mathrm{act}_{LP} = \mathrm{act}_p \times \left[ 1 + \sum_{l \in \mathrm{Loop}(p)} \mathrm{act}(l) \right]\\ \ \ \ \ \ \ \ \ \approx \mathrm{act}_p \times \left[ 1 + L(p) \times \mathrm{act}_{\mathrm{loop}} \right]$

这里 $\mathrm{Loop}(p)$ 表示路径 $p$ 上所有可能的环状路径，而在平均环假设下，每个点上所有环结构的作用可以用 $\mathrm{act}_{\mathrm{loop}}$ 表示。我们要注意， $\mathrm{act}_{\mathrm{loop}}$ 表示了所有可能的环，包括环上有环。所以对于环结构本身我们有：

$\mathrm{act}_{\mathrm{loop}} \approx \mathrm{act}_{\mathrm{loop}} \times \left[ 1 + \sum_{i = 1}^\infty i \times \mathrm{act}_{\mathrm{loop}} \right]$

可见，直接计算的结果显然是发散的，我们只能通过其它方式进行估算。

对于环结构的总作用，我们假定每个点上的最短环的长度为 $L_S$ （平均环假设），且长度为 $l$ 的所有图灵机中的环状结构对应的图灵机的概率为 $\rho_L(l)$ ，其上界为 $\rho_M$ ，即平均分布假设，则有：

$e^{- h L_S} < \mathrm{act}_{\mathrm{loop}} \approx e^{- h L_S} + \sum_{l = L_S + 1}^\infty \rho(l) \sigma^l e^{- h l} < e^{- h L_S} \left[ 1 + \rho_M \frac{\sigma^{L_S + 1}}{e^h - \sigma} \right]$

而 $\rho_M$ 可以估算为 $\rho_M \approx \sigma^{- L_S}$ ，然后假定空间中任意相邻两点之间的最近距离都差不多是相等的（平均间距假设），所以就有一个大致的估算：

$e^{- h L_S} < \mathrm{act}_{\mathrm{loop}} < e^{- h L_S} \frac{e^h}{e^h - \sigma}$

从这里可以看出，一条半正规路径越长，对应的所有常规路径的总作用量的综合也就越大，对应的也就是越长的路径具有越多的等价路径。

由此，我们可以大致估算 $\mathrm{act}_A(r,s)$ 与 $\mathrm{act}_S(r,s)$ 之间的关系：

$\mathrm{act}_A(r,s) \approx \mathrm{act}_S(r,s) \left[ 1 + \frac{L(r,s)}{D(r,s)} \frac{e^{- h (L_S - 1)}}{e^h - \sigma} \left( \frac{1}{h - \ln \sigma} + D(r,s) \right) \right]$

显然，两点之间距离越长， $\mathrm{act}_A$ 就比 $\mathrm{act}_S$ 大越多，因为能“夹塞”在其中的戴环的非半正规路径就越多，产生的影响自然也就越大。

当然，这只是在平均环假设下的一个很粗的估算。

下面，我们继续作一个估算，这次主要是看 $\mathrm{act}_K$ 与 $\mathrm{act}_S$ 及 $\mathrm{act}_N$ 之间的关系。

假定 $p$ 是连接 $r$ 到 $s$ 的最近路径，其跨度为 $L(p)$ 、长度为 $D(p)$ 。那么显然 $\mathrm{act}_K$ 就是 $p$ 的作用量：

$\mathrm{act}_K (r, s) = e^{- h D(p)}$

接着，我们来看跨度为 $T > L(p)$ 的所有路径及所有正规路径的总作用：

$\mathrm{act}_A (p, T) \approx \left[ N_O(r) N_I(s) \frac{T^2 - L(p)^2}{T^2} \right]^{\frac{T}{2}} \exp \left[ - h T \frac{D(p)}{L(p)} \right]\\ \mathrm{act}_N (p, T) \approx \left[ N_O(r) N_I(s) \frac{T^2 - L(p)^2}{4 T^2} \right]^{\frac{T}{2}} \exp \left[ - h T \frac{D(p)}{L(p)} \right]\\ \therefore \mathrm{act}_N (p, T) \approx 2^{-T} \mathrm{act}_A (p, T)$

进一步，我们可以估算出三种不同总作用量之间的关系：

$\mathrm{act}_A (r, s) = \mathrm{act}_K (r, s) + \sum_{T = L(r,s) + 1}^\infty \mathrm{act}_A (P_s (r,s), T)\phantom{wwwwwwwwwwwwwwwwwwww}\\ \approx \mathrm{act}_K (r, s) + \frac{\exp [ - \Delta_A L(p) ]}{\Delta_A} \left\{ 1 - \frac{\Delta_A L(p)^2 \mathrm{Ei} [ - \Delta_A L(p) ]}{2 \exp [ - \Delta_A L(p) ]} \right\}^{-1}\\ \Delta_A = h \frac{D(r, s)}{L(r, s)} - \frac{1}{2} \ln \left[ N_O(r) N_I(s) \right] \phantom{wwwwwwwwwwwwwwwwwwwwwwwwwwwwa}\\ \mathrm{act}_N (r, s) = \mathrm{act}_K (r, s) + \sum_{T = D(r,s) + 1}^\infty \mathrm{act}_N (P_s (r,s), T)\phantom{wwwwwwwwwwwwwwwwwwww}\\ \approx \mathrm{act}_K (r, s) + \frac{\exp [ - \Delta_N L(p) ]}{\Delta_N} \left\{ 1 - \frac{\Delta_N L(p)^2 \mathrm{Ei} [ - \Delta_N L(p) ]}{2 \exp [ - \Delta_N L(p) ]} \right\}^{-1}\\ \Delta_N = \Delta_A + \ln 2\phantom{wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww}$

这里 $\mathrm{Ei}(x) = - \int_x^\infty \frac{e^{-t}}{t} dt$ 是指数积分。该结果在 $\Delta_A > 0$ 与 $\Delta_N > 0$ 时成立，否则求和的结果就是无穷大。这就是说，如果 $N_O N_I$ 过大，那求和结果就是发散。而在这两个不等式都满足的情况下，上述结果中后面增加的部分将随着 $L(p)$ 的增加快速收敛为 0，但它与 $\mathrm{act}_K (r, s)$ 的比则随 $L(p)$ 的增加而快速增加，也就是它将远大于后者，两者的比接近：

$\lim_{L(p) \rightarrow \infty} \frac{\mathrm{act}_A (r, s)}{\mathrm{act}_K (r, s)} - 1 \approx \frac{1}{\Delta_A} \exp \left\{ \frac{1}{2} \left[ \ln N_O(r) + \ln N_I(s) - 1 \right] L(p) \right\}$

这就是说，当起点和终点距离很远，或者出邻点与入邻点足够多的时候， $\mathrm{act}_K$ 根本无法刻画两点之间的总作用， $\mathrm{act}_N$ 、 $\mathrm{act}_S$ 和 $\mathrm{act}_A$ 都比 $\mathrm{act}_K$ 大很多。

这还是在作了大量平均化的假设的情况下。在实际情况中计算会更加复杂，甚至不可计算。

下面，我们就可以来计算一下图灵空间中每个点的熵与信息了。

要定义熵和信息，我们先来构造一个动态的系统。

假定，在一个离散空间（图灵空间的底空间）中，每个离散的格子中都可以随机出现 $\sigma_0$ 个字符，且如果出现的连续若干字符正好构成图灵结构中的某台图灵机，那就可以执行该图灵机，并生成图灵机的计算结果。那么，目标字符串 $s$ 在这样一个随机空间中出现的概率 $P(s)$ 是多少？

很显然，现在我们有 $h = \ln \sigma_0$ ，而生成概率可以用作用量计算出来：

$P(s) = \sum_{r \in \Gamma} e^{- h |r|} \mathrm{act}_A(r,s)$

如果我们将从空字符串生成指定字符串的一类图灵机加入到图灵结构中，那其实上述结构就变成了：

$P(s) = \mathrm{act}_A(\varnothing,s)$

这样，结合上面得到的结果就有（一如既往， $K(s)$ 是 $s$ 的不可压缩长度，且跨度为 $L(s)$ ）：

$P(s) \approx e^{-h K(s)} + \frac{K(s) \exp [ - \Delta (s) ]}{\Delta (s)} \left\{ 1 - \frac{\Delta (s) K(s) \mathrm{Ei} [ - \Delta (s) ]}{2 \exp [ - \Delta (s) ]} \right\}^{-1}\\ \Delta (s) = \left\{ h \frac{K(s)}{L(s)} - \frac{1}{2} \ln \left[ N_O(\varnothing) N_I(s) \right] \right\} K(s) > 0$

前面提到过， $K(s)$ 越大，后面加上去的部分就越大，从而我们并不能简单地认为 $K(s)$ 越小概率 $P(s)$ 就越大。何况， $\Delta_A$ 中还包括平均化处理之后保留下来的 $s$ 周围入邻点数的信息，因此不同 $s$ 的概率并不只是和 $K(s)$ 相关。事实上， $K(s)$ 相等的情况下，入邻点数 $N_I(s)$ 越大 $P(s)$ 也会越大，两者在 $K(s)$ 足够大时差不多是 $P(s) \sim \frac{N_I(s)}{C - \ln N_I(s)}$ 的关系。

由于当 $h$ 不小时， $\frac{P(s)}{e^{-h K(s)}} - 1$ 随 $K(s)$ 的增长而快速下降，所以可以知道，只有当 $\Delta_A$ 略大于 0 时， $N_I(s)$ 的影响才会变得显著。

也就是说，现在有三种情况：

如果 $K(s)$ 足够小，则上述平均假设无法有效计算目标字符串 $s$ 的生成概率 $P(s)$ ，其与 $e^{- h K(s)}$ 的偏差将使得后者根本无法描述前者，全网链接结构共同决定了 $P(s)$ ；
当 $K(s)$ 充分大时， $P(s) \approx e^{- h K(s)}$ ；
在既不足够小又不充分大的情况下（在 $h$ 很大时，这个区间很小）， $K(s)$ 不足以决定 $P(s)$ ， $N_I(s)$ 对 $P(s)$ 一样很重要。

最后，既然我们已经有了在随机过程中生成目标字符串 $s$ 的概率 $P(s)$ ，那我们自然就可以计算它的熵了：

$S(s) = - P(s) \ln P(s)$

当然，我们也可以使用另一种概率：

$\rho(s) = \frac{P(s)}{\sum_{r \in \Gamma} P(r)}$

则同样可以定义一个分布熵：

$S_d(s) = - \rho(s) \ln \rho(s) = \frac{S(s)}{P_\Sigma} + \frac{P(s)}{P_\Sigma} \ln P_\Sigma$

当然，也要再次强调，上面都是建立在极不靠谱的很粗糙的平均假设上所作的估算，最多算是有一点定性的线索，距离实际情况还有很远。

下面，我们就要来看比熵更有趣的概念了——信息量。

信息量应该如何定义？

如果说熵度量了达到最终状态的可能路径的多少，也即一个宏观状态下包含的微观状态数，那和信息其实并没有非常直接的关联。

信息可以定义为能创造多少新数据的一个度量方式。

因此，我们可以定义信息量为：

$I(s) = \sum_{r \in \Gamma} \mathrm{act}_A (s, r)$

但很显然，通过字符串创造出更复杂的字符串理应有更高的信息量，所以我们可以将信息量调整为：

$I(s) = \sum_{r \in \Gamma} \mathrm{act}_A (s, r) K(r)$

令 $J(s)$ 为 $s$ 到离它最近的 $r$ 的距离，则信息量大致可以表述为： $I(s) = e^{- h J(s)} K(r)$ 。作为比较，在 $h$ 足够大时，熵可以表述为 $S(s) = h e^{- h K(s)} K(s)$ ，还是比较接近的。

通过这样的定义， $I(s)$ 实际上衡量了从目标字符串出发，所有能到达的点的势与作用量的综合，从而可以看作是目标字符串对全网的“贡献”大小。

当然，我们也可以取另外一种定义信息量的方式，比如：

取底空间 $\Gamma$ 上所有点的不可压缩长度的总和为 $K_\Gamma$ ，接着将目标字符串 $s$ 从 $\Gamma$ 中移除，这样构造的新的图灵空间中所有点的不可压缩长度的总和为 $K'_\Gamma$ ，从而我们可以定义 $s$ 的信息量为： $V(s) = K'_\Gamma - K_\Gamma$ 。

当然，这样定义的方式很繁琐，难以计算。

无论如何，我们都是从能创造多少数据的角度来衡量信息的——因为，如果信息不能创造东西，那它就不应该被称为“信息”。

另一方面，我们很自然就有如下关系（还记得上面提到的出邻点集上作用量的求和关系么？）：

$I(s) = \sum_{r \in N_O(s)} (I(r) + K(r)) \mathrm{act}_A (s, r)$

因此，如果 $s$ 的出邻点足够多，那 $s$ 的信息量会比其出邻点信息量要大，甚至可能比出邻点总信息量大。而如果 $s$ 的出邻点很少，那 $s$ 的信息量则很可能会比它任意一个出邻点的信息量都要小。但这两个关系都不是必然的，因为还有 $K(r)$ 的影响。

于是，我们和计算熵的时候一样，认为空字符串可以创造出一切别的字符串，从而上式可以推出：

$I(\varnothing) = \sum_{s \in \Gamma} (I(s) + K(s)) P(s)$

而同时，我们根据定义有：

$I(\varnothing) = \sum_{s \in \Gamma} K(s) P(s)$

因此我们可以知道 $I(\varnothing) = \infty$ ——这是一个很无聊的结论。出现这种情况是因为 $\mathrm{act}_A$ 的直接计算中会出现无穷大项（之前我们已经看到过环状结构可以无限叠加从而导致发散），在合理正规化之前概率与信息出现无限大是很自然的。而如果我们不用可能包含无穷大项的作用量，而采用最近路径对应的作用量 $\mathrm{act}_K$ ，那上面的关系就不再能精确存在。此时我们可以认为近似关系为：

$I(\varnothing) = \lambda \sum_{s \in \Gamma} (I(s) + K(s)) P(s)$

所以大致有的关系是 $I(s)$ 随 $K(s)$ 的增加而减少。当然，这个结论非常非常粗糙。

但从上述分析还是可以得到一些定性的结论。比如对于可压缩字符串而言，其不可压缩表达的信息量往往比它本身要低。而一个字符串能被作为图灵机输入的场合越多，信息量也就越大，相应的能生成它的字符串的信息量也大。

总结而言，熵度量了字符串被创造的可能性，而信息则度量了字符串能创造多少字符串的能力。

当然，上述方法在任意有向图上都能用，只要能定义节点的势、有向边的作用量，即可。

下面我们来看一个简单的例子。

我们假定，系统中可用字符只有两个：o 和 x

其作用为：

不同数量的 o 代表不同的自然数，其值为 o 的数量
x 代表自然数字符串结束
规则：如果两个数一前一后写在一起，则等于一台图灵机，运行结果为两者的乘积；且系统最大能表达的数字不超过 $N$

这样构造的图灵机当然不是图灵完备的，但不妨作为一个示例来用。

下面，图灵结构中包括所有能表达素数的字符串。

现在，我们就有了一个图灵空间。

任意自然数 $n$ 可以写为一组素数的乘积： $n = \prod_{i=1} p_i^{c_i}$ 。它本身的长度为 $n + 1$ ，而其最短长度为 $\sum_{i = 0} c_i (p_i + 1)$ 。

下面我们可以列出前 20 个自然数的熵和信息量（取 $h = \ln(100)$ 、 $N = 200$ ）：

n	不可压缩长度	入邻点数	熵	信息量
1	2	1	0.00009999999999999991	0.00020304051121243537
2	3	1	9.999999999999987e-7	0.00020304051121243537
3	4	1	9.999999999999982e-9	0.00020304051121243537
4	5	2	1.009999999999996e-10	0.00020304051121243537
5	6	1	9.999999999999974e-13	0.00020304051121243537
6	7	3	2.999999999999996e-14	0.00020304051121243537
7	8	1	9.999999999999965e-17	0.00020304051121243537
8	8	2	1.0099999999999964e-16	0.00020304051121243537
9	8	1	9.999999999999965e-17	0.00020304051121243537
10	9	2	1.9999999999999886e-18	0.00020304051121243537
11	12	1	9.999999999999948e-25	0.00020304051121243537
12	9	5	1.0399999999999939e-18	0.00020304051121243537
13	14	1	9.999999999999975e-29	0.00020304051121243537
14	11	2	1.999999999999994e-22	0.00020304051121243518
15	10	2	1.9999999999999842e-20	0.00020304051121243518
16	11	2	1.0099999999999969e-22	0.00020304051121243518
17	18	1	9.999999999999886e-37	0.00020304051121242583
18	11	4	3.999999999999988e-22	0.00020304051121242583
19	20	1	9.999999999999842e-41	0.00020304051121242583
20	11	4	1.0299999999999968e-22	0.00020304051121242583
30	13	7	6.999999999999948e-26	0.00020304051120999982
40	14	6	2.0399999999999946e-28	0.0002030405109999998
50	15	3	2.9999999999999645e-30	0.0002030405049999998
60	15	16	2.1399999999999754e-30	0.00020303999999999982
80	17	8	3.049999999999993e-34	0.0002029999999999998
100	17	7	1.0599999999999973e-34	0.0002029999999999998
120	18	29	6.229999999999929e-36	0.00019999999999999982
150	19	13	1.2999999999999913e-37	0.00019999999999999982
200	20	13	3.0999999999999516e-40	0.00019999999999999982

这么看还不够直观，我们列举 200 以内熵最高的一组数字：

n	不可压缩长度	入邻点数	熵	信息量
1	2	1	0.00009999999999999991	0.00020304051121243537
2	3	1	9.999999999999987e-7	0.00020304051121243537
3	4	1	9.999999999999982e-9	0.00020304051121243537
4	5	2	1.009999999999996e-10	0.00020304051121243537
5	6	1	9.999999999999974e-13	0.00020304051121243537
6	7	3	2.999999999999996e-14	0.00020304051121243537
8	8	2	1.0099999999999964e-16	0.00020304051121243537
7	8	1	9.999999999999965e-17	0.00020304051121243537
9	8	1	9.999999999999965e-17	0.00020304051121243537
10	9	2	1.9999999999999886e-18	0.00020304051121243537
12	9	5	1.0399999999999939e-18	0.00020304051121243537
15	10	2	1.9999999999999842e-20	0.00020304051121243518
18	11	4	3.999999999999988e-22	0.00020304051121242583
14	11	2	1.999999999999994e-22	0.00020304051121243518
20	11	4	1.0299999999999968e-22	0.00020304051121242583
16	11	2	1.0099999999999969e-22	0.00020304051121243518
24	12	7	2.0499999999999894e-24	0.00020304051121160783
21	12	2	1.9999999999999896e-24	0.00020304051121240784
11	12	1	9.999999999999948e-25	0.00020304051121243537
25	12	1	9.999999999999948e-25	0.00020304051121160783
27	12	1	9.999999999999948e-25	0.00020304051121079983
30	13	7	6.999999999999948e-26	0.00020304051120999982
36	13	9	1.0799999999999924e-26	0.0002030405109999998
28	13	4	1.0299999999999925e-26	0.00020304051121079983
45	14	3	2.9999999999999924e-28	0.0002030405049999998
40	14	6	2.0399999999999946e-28	0.0002030405109999998
35	14	2	1.999999999999995e-28	0.0002030405109999998
32	14	2	1.0099999999999973e-28	0.00020304051120999982
13	14	1	9.999999999999975e-29	0.00020304051121243537

从这些数据可以看出， $K(s)$ 的确并不是决定 $S(s)$ 的唯一因素，入邻点数也很重要——当然，在这个例子中由于 $h$ 很大，所以实际上是 $K(s)$ 对应的不可压缩表示的数量，比如有多个字符串到 $s$ 的作用都等于 $K(s)$ 。

而另一方面，信息量则几乎可以说是随着 $K(s)$ 的增加而减少的，但减少的量非常小。总体而言，和之前的估算在大趋势上还是吻合的。

最后，总结一下。

我们可以认为，熵就是衡量一个图灵空间中在完全随机过程中出现目标字符串的概率 $P(s)$ 的函数，衡量了产生一个字符串的难易程度，或者说一个字符串可以被多少种方式创造出来。

而另一方面，信息则衡量了目标字符串可以创造多少新的字符串。这是和传统将信息与熵直接挂钩不同的地方。

它们一个衡量“被创造”，一个衡量“创造力”。

本文遵守创作共享CC BY-NC-SA 4.0协议

通过本协议，您可以分享并修改本文内容，只要你遵守以下授权条款规定：姓名标示 、非商业性、相同方式分享。
具体内容请查阅上述协议声明。
纸媒与网络平台如需转载必须与本人联系确认。

AIT 中的信息与熵

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

理科生的果壳

有意思的文章