理论空间的结构

本文原始地址：https://lostabaddon.github.io/#/view?f=science/AIT/structureoftheoreticalspace.mu

图灵机，无限图灵机，拓展图灵机

从功能的角度来说，一台图灵机就是将几个有限长字符串映射为一个字符串的、能由有限多个字符编码表达的映射函数。

由于构成字符串的字符只有有限个，字符串的长度是可数的，返回状态无论是接受、拒绝还是不停机，总共也只有有限种可能，所以图灵机可以视为一类将自然数映射到自然数的函数。

但所有将自然数映射到自然数的函数构成的集合明显是比所有图灵机要多的，因为前者的数量是$\aleph_1$而后者只有$\aleph_0$，所以图灵机集与自然数到自身的映射函数的集相比是非常稀疏的。

换一个角度来想，图灵机本身也是可以被编码到自然数的，事实上两者可以很简单地构造出一一映射。但自然数到自身的映射函数则可以被编码到$[0, 1)$内的实数，方法是从“功能”的角度来看，一个上述函数$f$可以将自然数$n$映射到自然数$f(n)$，所以它就可以映射为如下实数：

$$
N(f) = \sum_{i = 1}^{\infty} 2^{- \sum_{j = 1}^{i - 1} f(j)} \left[ 1 - 2^{1 - f(i)} \right]
$$

该函数可以将自然数到自然数的映射函数映射到一个不小于0且不大约1的实数，进而可以映射到整个实数域。反过来，任何一个实数也都可以逆变换为一个上述映射函数，因此实数域和上述映射函数集是一一对应的。

所以，虽然图灵机可以视为将自然数映射到自然数的函数，但由于自然数到自然数的映射远多于图灵机，所以很多功能是图灵机所无法完成的，比如停机判定机、K氏复杂度计算机等，它们都可以将自然数映射到自然数，但本身无法被编码为自然数，所以这些功能是无法用图灵机来实现的。

这里要强调的是，我们是从“功能”的角度来看图灵机的，而所谓功能就是对输入能给出什么样的输出，它是输入到输出的映射。可以有两台具体代码截然不同的图灵机，但它们在功能上是完全一样的。
这里也不考虑输出到底是接受还是拒绝还是不停机，这三者的差异仅仅体现为输出结果编码成的自然数的具体值的不同。所以从功能的角度我们或许是无法不加限定地讨论注入遍历、枚举、遍历可枚举这些传统讨论主题的。

而从另一个角度来看，这似乎也表明所有不能表达为图灵机的自然数到自身的映射函数如果硬要用图灵机的方式来编码的话，那它的长度就必须是无限大（$\aleph_0$），因为这样这些无限长图灵机的数量才能够得上$\aleph_1$。

很显然的一点便是将任意有限长字符串映射到任意有限长字符串的映射和将任意字符串映射到任意字符串的映射也还是不同的，前者等给予将自然数映射到自然数，而后者等价于将实数映射到实数，所以后者的数量为$\aleph_2$，更多。

所以，我们不妨将所有不能表达为图灵机的自然数到自然数的映射函数称为无限图灵机。

图灵机和无限图灵机都只能对图灵机进行操作而不能对无限图灵机操作，因为无限图灵机对应实数，而图灵机和无限图灵机的输入只能是自然数。能将无限图灵机作为输入来操作的映射机显然只有无限接近0的概率依然是无限图灵机，因为能将实数映射到实数的函数的数量是$\aleph_2$。

事实上，从一个集合$\mathfrak{F}$映射到$\mathfrak{F}$自身的所有函数构成的集合$\mathfrak{F}'$的势必然是大于$\mathfrak{F}$的，因为从集合A到集合B的所有映射构成的集合的大小/势为$|B|^{|A|}$，所以$\left| \mathfrak{F}' \right| = \left| \mathfrak{F} \right|^{\left| \mathfrak{F} \right|}$。这样我们可以不断地用这种方式构造越来越复杂与强大的映射机，且图灵机在这些映射机中的占比一层比一层接近0。

我们将所有图灵机和无限图灵机统称为拓展图灵机，下面我们主要讨论的就是拓展图灵机。

拓展图灵机的无穷小领域

拓展图灵机空间既然是和实数集等价的，那么我们自然会问一个问题：拓展图灵机空间中是否可以定义一台拓展图灵机的“无穷小领域”？

如果我们还是以代码的形式来看到拓展图灵机的话，那显然不存在“无穷小领域”一说。所以我们首先就要确定好编码方式。这里我们继续使用上面所给的那套编码方案。

在这个编码方案下，无穷小领域只能发生在求和项的指数$i \rightarrow \infty$的时候，因此一个拓展图灵机$T$的无穷小领域$B(T)$中的拓展图灵机$T'$就是和$T$对任意有限长字符串输入（即对任意有限大自然数）的处理结果始终保持相同，但当字符串被编码成的自然数为无限大时却会发生不同，这个听起来很拗口。

既然$B(T)$中的所有拓展图灵机对任意有限自然数的出列结果都和$T$相同，它们的差体现在无限的部分，所以也就是说必然存在一台图灵机，至少对任意有限的输入都能和该无穷小领域中任意一台拓展图灵机的功能相同，这台图灵机就被称为计算主部。

预言机与拓展字符

我们可以为图灵机集添加预言机，从而将它扩展为更大的超集。

如果一台预言机是无法通过图灵机来实现的，比如停机判定或者计算K氏复杂度，那么它显然就是无限图灵机的一份子了（我们这里不考虑能处理无限图灵机的更高阶映射机）。而由于这样一台预言机的计算主部必然还是一台图灵机，因此可以说它是为实数轴上代表图灵机的点集增加了无穷小领域上的细节调整。

注意，这不是说预言机的引入后，任意一台图灵机接上预言机后结果只有小变化，而是说从整个图灵机构成的集合来看，预言机的引入带来的调整所产生的新集合与原集合相比，改变是“小”的。

和预言机一样，我们也可以在拓展图灵机中添加一些“拓展字符”，来代表那些无法用图灵机来表达的字符。比如在$\lambda$演算可以自然地表达有理数，而类似$\sqrt 2$和$\pi$这样的数可以作为拓展字符引入到这个系统中，它们就是拓展字符。拓展字符可以被“正常”处理，但并不需要将它们完整地“表达”出来。

复合与拼接

因此，拓展字符是一种弱化了的预言机。

由于拓展图灵机是将自然数映射到自然数的函数，所以我们自然可以定义两个拓展图灵机的复合作用了：

$$
(f_A \otimes f_B)(n) = f_A \left( f_B (n) \right)
$$

因此，复合可以将两个代表拓展图灵机的实数映射到另一个代表拓展图灵机的实数上。

很显然，复合是封闭的，而且也满足结合律：

$$
(f_A \otimes f_B) \otimes f_C = f_A \otimes (f_B \otimes f_C)
$$

而且自然也存在单位元，那就是将自然数映射到自身的不动映射$f_e$。

但复合却不是所有拓展图灵机都有逆元的，且显然也不满足对易性，所以$\left< \{T\}, \otimes \right>$只能构成非对易幺半群而不能构成群。当然，如果我们将映射限定为可逆映射，即不存在两个自然数映射到同一个自然数的情况，那么它实际上构成了自然数上的无限矩阵群。

下面我们考虑一个拓展图灵机$T$的单位变换：

$$
\begin{align}
T'(i) &= \begin{cases}
T(i) & i \neq n\\
t' & i = n
\end{cases}\\
T(n) &= t
\end{align}
$$

在上述（到$[0, 1)$的）编码规则下，不难有：

$$
\begin{align}
N(T') - N(T) &= \left( 1 - 2^{t - t'}\right) 2^{- S(n)} \left( 2 - N_r \right)\\
S(i) &= \sum_{j = 1}^i T(j)\\
N_r &= \sum_{i = n + 1}^\infty 2^{S(n) - S(i - 1)} \left[ 1 - 2^{1 - T(i)} \right]
\end{align}
$$

事实上，如果$f'(i) = f(i + n)$，则很自然有$N(f) = 2^{- \sum_{j = 1}^{n - 1} f(j)} N(f') + \sum_{i = 1}^{n - 1} 2^{- \sum_{j = 1}^{i - 1} f(j)} \left[ 1 - 2^{1 - f(i)} \right]$，其中第二项是前$n$项的编码，第一项是$f'$编码乘上一个位移因子。所以在发生单位字符改变时，情况会相对较容易分析。

当$n \rightarrow \infty$时上述单位变换在编码后就是无穷小变换。

然后我们可以考虑下面这个左乘和右乘：

$$
T \otimes X \phantom{wwwww} X \otimes T
$$

当$T$变换为$T' $后，相应的乘积的编码将发生改变：

$$
\begin{align}
\Delta N(T \otimes X) &= \left[ 1 - 2^{X(t) - X(t')} \right] 2^{- S_{T \otimes X}(n)} \left[ 2 - N_{r, T \otimes X} (n) \right]\\
\Delta N(X \otimes T) &\approx \left( 1 - 2^{t - t'} \right) 2^{- S_{X \otimes T}(\hat n)} \left[ 2 - N_{r, X \otimes T} (\hat n) \right]\\
X(\hat n) &= n
\end{align}
$$

右乘时之所以是约等于，因为可能存在多个$\hat n$使最后一个等式成立，这里只考虑能使第三式成立的最小自然数，但当存在重根时就会和这个结果发生小偏差。

这样我们就能得到由$T$的无穷小改变而引起的复合的无穷小改变：

$$
\begin{align}
\frac{d T \otimes X}{d T} &= \lim_{n \rightarrow \infty} \frac{\left[ 1 - 2^{X(t) - X(t')} \right] \left[ 2 - N_{r, T \otimes X} (n) \right]}{\left( 1 - 2^{t - t'}\right) \left[ 2 - N_{r, T} (n) \right]} 2^{S_T (n) - S_{T \otimes X}(n)}\\
\frac{d X \otimes T}{d T} &= \lim_{n \rightarrow \infty} \frac{\left[ 2 - N_{r, X \otimes T} (\hat n) \right]}{\left[ 2 - N_{r, T} (n) \right]} 2^{S_T (n) - S_{X \otimes T}(\hat n)}
\end{align}
$$

当$n \rightarrow \infty$时，上述结果中右乘只和$T$及$X$相关，而左乘却还与发生的具体改变相关。但当$n \rightarrow \infty$时$N_{r, T} (n)$与$N_{r, T \otimes X} (n)$、$N_{r, X \otimes T} (n)$都没有很好的定义，且$S_T (n) - S_{X \otimes T}(\hat n)$与$S_T (n) - S_{T \otimes X}(\hat n)$也很可能是发散值，正负无穷大都有可能，有限的结果反而很让人意外，因此我们几乎可以确定，如此编码下的左右乘在无限小变换下都是不连续的。

而当$n$有限时，即便只是进行了有限小变换时，此时右乘结果的三个项都是大于零的（余项编码值$N_r$显然是在$[0, 1)$这个范围内的），所以右乘结果的正负性与有限变换的正负性相同。但左乘的情况却不同，除了要看有限改变的正负性，值被X作用的前后改变情况也要考虑，所以情况比右乘时更复杂。

除了复合，拼接也是一个比较有用的操作。

假定我们现在有字符串$s_1$与$s_2$，那么字符串的拼接操作为：$s = C(s_1, s_2) = s_1 \oplus b \oplus s_2$，这里符号$\oplus$代表将两个字符串写在一起，$b$表示由单独一个分隔符组成的字符串。

记$E(s)$与$D(n)$是将字符串编码到自然数的编码函数及其逆，那么拓展图灵机的拼接韩束可以表达为：

$$
(T_1 \oplus T_2)(n) = E (C \left( T_1 (D(n)), T_2 (D(n)) \right))
$$

拼接函数满足封闭性与结合律但没有对易性，也没有单位元与逆，所以也是只能构成半群而不能构成群。

由于在正常字符串编码规则下，我们显然有$E(C(s_1, s_2)) \geq E(s_1)$，所以显然有$N(T_1 \oplus T_2) \geq N(T_1)$，等号成立于分隔符编码为0且$T_2$的输出恒为0时。

构造与层级

前面我们主要考虑的是将所有可能出现的拓展图灵机所构成的一个整体$XT$，下面我们来换一个思路：我们从一个子集开始，构造出一个更大的集。

令$B$是由若干拓展图灵机构成的集合，然后通过复合$\otimes$与拼接$\oplus$这两个二元运算，我们可以构造出一个更大的集：

$$
B_1 = B \cup B \otimes B \cup B \oplus B
$$

其中$B \otimes B$与$B \oplus B$是$B$中任意两个元素复合与拼接后构成的集。

事实上，我们可以构造如下这样的集合序列：

$$
B_n = B_{n - 1} \cup B_{n - 1} \otimes B \cup B \otimes B_{n - 1} \cup B_{n - 1} \oplus B \cup B \oplus B_{n - 1}
$$

一次上述操作称为一次扩张，而如果$B_n = B_{n + 1}$，则称$B_n$是$B$所张的，$B$是$B_n$的基，$n$为$B$在$XT$中的深度。显然，如果$B$本身是有限或者可数的，那么通过有限次拓展后它是不可能得到全集$XT$的，因为前者的大小是有限值或可数无穷大，而后者的大小是不可数无穷大。

反过来，我们也可以讨论对于已知集合$T$，它可以由一些基张出来，其中深度最深的基与元素最少的基将对刻画$T$的性质具有很重要的帮助，前者称为“根”而后者被称为“核”。一般而言，根与核未必是重合的。

现在，假定集合$T $是由集合$B$张出的，那么我们可以为$T$中元素进行分层：

$$
O_n = B_n \cap \bar B_{n - 1}; O_0 = B_0 = B
$$

其中$\bar B_{n}$是$B_n$在$XT$中的补，$O_n$称为$B$的第$n$层。

这样，$T$中元素$t$都可以被映射到一个非负整数，即它所在的层的指数，称为$t$的高，记为$h(t)$。换言之，$T$中任意一台拓展图灵机都可以表示为$h(t)$个$B$中拓展图灵机通过拼接与复合来构造出来的。

我们可以类比自然数的计算：$B$是单元数集$ {1} $，拼接是加法，复合是乘法，那么整个自然数集就都可以用$B$张出来。

而，由于逻辑运算当然可以表达为拓展图灵机，所以拓展图灵机之间的各种逻辑组合都可以从一组包含逻辑运算的基中张出来。如果再引入各种表征用的拓展字符，那么理论上我们可以用上述方法将任意理论体系从一个极小的核开始给张出来。

表达的深度与广度

现在，我们依然令$T$是$B$所张成的拓展图灵机集，是所讨论问题的全集。我们将$B$中的拓展图灵机称为基元素，而拼接与复合统称为算符。

这样，任意一台拓展图灵机都可以从$B$中的若干接点开始，经过一系列拼接与复合来构成，而且这样的构造方式可能是非唯一的，比如如下情况：

$$
t = b_1 \oplus b_2 \oplus b_3 = b_4 \otimes b_4 \oplus (b_4 \otimes b_4)
$$

我们将能给出目标元素$t$的上述形式的式称为$t$的表达式，记为$A \Rightarrow t$，而$t$的所有表达式被称为$t$的表达族$\mathrm{Rep}(t)$。那么显然上面的例子中$t$有两条表达式，而它的高度是有最短表达式，也即用到算符最少的表达式所给出的。但另一方面，我们注意到第二个表达式中，我们实际上只用了一个基元素，而在最短表达式中我们用了三个基元素，所以第二个表达式虽然更长，但却未必能说更复杂。我们将表达式$A$中算符的数量称为表达式的深度$D(A)$，而不同基元素的数量称为表达式的广度$B(A)$。由此，我们可以知道$t $的所有表达式的深度最小值是它的高度，而它的广度就是所有表达式的广度最小值：

$$
\begin{align}
D(t) = \min_{A \in \mathrm{Rep}(t)} D(A)\\
B(t) = \min_{A \in \mathrm{Rep}(t)} B(A)
\end{align}
$$

由于一个元素$x$在一个表达$A$中出现的次数可能是不同的，所以我们可以用$r(x, A)$来表示它在这个表达中出现或者说使用的次数。

有向超图及其相关性质

用$U(A)$表示表达式$A$中用到的所有元素的集合，这些元素不用都是基元素。从而对于任意表达路径$A$我们有：

$$
D(A) + 1 = \sum_{x \in U(A)} r(x, A)
$$

如果$A \Rightarrow t \land U(A) \subseteq X$，则称$t$可以被集合$X$表达，记为$X \models t$。

如果我们将一条路径$A$中某一个位置的元素替换为表达该元素的表达路径$B$从而得到一条新的表达路径$A'$，那么显然有如下两条关系：

$$
\begin{align}
D(A') &= D(A) + D(B)\\
r(x, A') &= r(x, A) + r(x, B)
\end{align}
$$

这里$x$是有别于被替换位置元素的其它元素。

如果我们将$A$中所有指定元素都被替换为一条相同的表达路径，那么情况就变成这样的：

$$
\begin{align}
D(A') &= D(A) + r(e, A) D(B)\\
r(x, A') &= r(x, A) + r(e, A) r(x, B)
\end{align}
$$

这里$e$是被替换的元素，$x$是与$e$不同的其它元素。

下面，我们选择$T$中的一个子集$V$，并要求$B \subseteq V$，这样对$V \cap \bar B$中任意元素$v $，显然有$V \models v$。我们取$\{ \{A, \{v\}\} | v \in V \land A \Rightarrow v \land U(A) \subseteq V \}$为有向超边集$E$，所以就可以构造有向超图$H(V, E)$，我们称$H$是拓展图灵机集$V$的伴随有向超图，或者简称为伴随图。

显然，这样的超图很可能是非单纯的，因为连接同一组起点集与终点的有向超边可能有不止一条。比如$4 = 2 + 2 = 2 \times 2$，所以从$\{2\}$到$\{4\}$的有向超边就有不同的两条。

此外，这样的超图也很可能存在环，即起点集等于终点集的有限超边。所以这样得到的超图是非单纯的（non-simple，或者也可以说是multiple的）。

当我们将$\bar V$中元素移入$V$时，实际上也自动将所有相关的有向超边都添加进了超图$H $。

当然，一个更广泛的情况是$V$的伴随超图的部分超图（partial hypergraph），所以我们下面的讨论就是基于这种伴随部分超图来讨论的。

部分超图$P$是指保留超图$H$的顶点集而只取超边集的真子集而构成的超图。而子超图（subhypergraph）$S$指去掉$H$的部分顶点，同时保留$H$中那些去掉这些被去除的顶点后起点集与终点集都非空的超边，而得到的超图。

因此，$H$（现在是上面所说的伴随部分超图了）的扩展就有两种方式：

1. 添加节点（所以原超图是新超图的子超图）

2. 添加超边（所以原超图是新超图的部分超图）

在这张超图中，传统的诸如直径、截面等概念的作用并不大，比较有用的是超图的连通性、层级性与圈结构。

令$a$和$b$是$H$中的两个节点，且至少存在一组有向超边$\{ L_1 , L_2, ... , L_n \}$，且$a$是$L_1$的起点集中元素，$b$是$L_n$的终点集中元素，$L_{i - 1}$的终点集是$L_i$的起点集的子集，则称存在从$a$到$b$的通路。显然，存在从$a$到$b$的通路并不表示也存在从$b$到$a$的通路。如果两个节点之间彼此存在到对方的通路，则称这两个节点是相连的，如果只存在一个方向的通路，则称彼此之间是偏连的，如果连一个方向的通路都不存在，则称为彼此分离的。

如果$H$中任意两个节点之间都存在通路（当然必须注意逆通路也存在），那就说$H$是单连通的，否则就是复连通的。由于$H$的节点集包含了基集，所以总是存在从基元素到其它任意节点的通路，但反过来则不一定，也因此基集之外的部分可以根据连通性分解为若干叶，每一叶之间都存在一些节点是偏连甚至分离。

当然，还可能存在另外一种情况，即：

$$
O \cup T_i \models T_{i + 1}\\
O \cup T_{i + 1} \not \models T_{i}
$$

也即，一组节点$T_i$搭配上一组公共节点$O$后可以表达下一组节点$T_{i + 1}$中的每一个元素，但反过来却不行。比这个约束更强的是存在从上一组到下一组的通路，但不存在逆通路。但我们暂时用不到这么强的分层要求。

因此，上述条件实际上为超图提供了另一种分层方式，是从有向超边的角度来给出分层，而不是和之前那样从最短表达的长度的角度来给出分层。

除了连通性，圈结构也是很有趣的一个性质。

无向超图中的圈定理告诉我们，如果一组首尾相连的超边，相邻两条超边的交集非空，且所有相邻超边的交集的并集不是该超图的超边，那么这组超边就构成了一个圈。
在有向超图中，我们要求一组有向超边序列中任意一条超边的终点集与其后续超边的起点集的交集非空，且不存在一条该超图的有向超边，使得这些交集中任意几个的并等于其起点集而其余交集的并等于其终点集。

圈结构的存在表示这张超图中存在可能的冗余，要找出真正的冗余，我们需要使用等价集：

假定集合$A$与$B$满足：

$$
\forall t \in A : B \models t\\
\forall t \in B : A \models t
$$

即两个集合中的每个元素都可以被另一个集合表达，这样的两个集合就是一对等价集，记为$A \Leftrightarrow B$。显然等价集是可以传递的。

等价集其实是一簇特殊的圈（事实上，由于圈通路所用到的所有节点都在这两个集合中，所以我们也可以称这两个等价集构成了一个封闭有向圈簇），且它表明，这两个集合并不需要同时存在，只要保留其中任意一个就足够了——当然，保留哪一个可能会在更深层次上存在一定的差异，这个我们后面再说。

当然，更常用的可能是一个比等价集弱的概念，即由集合$O$支持的弱等价集：

$$
\forall t \in A : O \cup B \models t\\
\forall t \in B : O \cup A \models t
$$

显然$A$和$B$如果是弱等价的，记为$A \dot \Leftrightarrow_O B$，并不能得出$O \cup A$与$O \cup B$是等价的这样的结论，但反过来却是成立的。

由于逻辑推理等和理论都可以表达成拓展图灵机，所以实际上就可以利用弱等价集来代表所有彼此之间相互等价的定理——当然，很显然，支持集$O$代表的就是推理用的逻辑系统（比如模态逻辑中的T、D4、D5这些系统）加上公理。

而连通性给出的分叶结构实际上给出了一个基础理论在几个不同领域中的高层应用，而分层结构则给出了不同理论之间的推导关系，比如，物理理论（理论上）可以给出所有化学原理，但反过来却不行。

因此，原则上说，上述这套拓展图灵-有向超图工具为我们分析理论的结构提供了一种有力的数学工具。

当然，有趣的事还可以有更多。

赋值与权重

我们下面考虑这么一个问题：要如何表征一个节点在整个系统中的“重要性”呢？

我们先从最简单的问题来看起。

假定$A \Rightarrow t$，且我们为$t$元素本身赋值为1，那么一个很自然的问题就是这个赋值应该可以通过表达路径的形式传递给它的源头们：$U(t) = \bigcup_{A \in \mathrm{Rep}(t)} U(A)$。一个很直观的想法，是认为每条表达路径$A$有一个配分权重$W(A)$，从而$U(t)$中的节点可以通过如下方式来获得赋值：

$$
W(x, t) = \lambda(t) \sum_{x \in U(A) \land A \in \mathrm{Rep}(t)} \frac{r(x, A)}{D(A) + 1} W(A)
$$

这样$U(t)$中所有元素的总赋值就是：

$$
\sum_{x \in U(t)} W(x, t) = \lambda(t) \sum_{A \in \mathrm{Rep}(t)} W(A)
$$

我们可以要求这个总赋值为1，从而就有：

$$
\lambda(t) = \left[ \sum_{A \in \mathrm{Rep}(t)} W(A) \right]^{-1}
$$

另一方面，我们也当然会希望越短的表达路径获得的权重越高，所以可以给出如下形式的配分权重：

$$
W(A) = e^{- D(A)}
$$

这样我们就有了最终结果：

$$
\begin{align}
Z(A) &= e^{-D (A)}\\
Z(t) &= \sum_{A \in \mathrm{Rep}(t)} Z(A)\\
W(x, t) &= Z(t)^{-1} \sum_{x \in U(A) \land A \in \mathrm{Rep}(t)} \frac{r(x, A)}{D(A) + 1} Z(A)
\end{align}
$$

从形式上看，它和我们在很多统计系统中所看到的配分函数是非常类似的。

显然，$W(x,t)$越小，则表示要么从$x$到$t$的表达路径更小，要么能从$x$到$t$的表达路径更多（指数级地多）。根据Levin编码定理，我们基本上可以认定后一种情况几乎不可能出现，所以$W(x, t)$越小几乎就必然地指向这两个节点之间的距离越近。

Levin编码定理基本上可以理解为函数$f$的算法概率$P(f)$越大，基本上等价于K氏复杂度$K(f)$越小。
这里算法概率$P(f) = \lim_{n \rightarrow \infty} P_n (f)$，而$P_n(f)$表示的是在编码为自然数后的前$n$个图灵机中能实现函数$f$的功能的图灵机的数量占比。
由于在超图$H$中任意有限长表达路径都可以等价于一类特殊的$\lambda$演算的表达式，从而等价于一台（添加了预言机的）图灵机，所以Levin编码定理在这里一样可以使用。
当然，该定理实际上划出了一个范围：$- K(f) + O(1) > \ln P(f) > - K(f) - O(1)$，所以它并不能将这两者完全绑定，但一般相信在这么一个范围中这两者基本上是匹配在一起的，即$P(f)$越大意味着$K(f)$越小。

当然，我们可以将这个计算略作简化。

假如一条表达路径可以表达为另一条表达路径中将若干个元素替换为它们各自的表达的形式来得到，那我们就说这条表达路径是可分解的，反之则称为不可分解的。元素$t$的所有不可分解表达路径构成的集合记为$\mathrm{UDR}(t)$，显然有$\mathrm{UDR}(t) \subset \mathrm{Rep}(t)$。我们可以形象地将$\bigcup_{A \in \mathrm{UDR}(t)} U(A) $理解为紧紧包裹着$t$的一层最近的“球壳”。

这样，我们可以将上述计算中所有对$\mathrm{Rep}(t)$求和的部分都替换为对$\mathrm{UDR}(t)$求和，这将为计算简化很多。

因此，如果我们有了一批源点$t_i$，以及每个源点的赋值$V_i$，那么我们就可以利用上面得到的配分权重函数$W(x, t)$来计算出$T$中每个节点的权重值（除非源点有环，否则源点自身不会获得权重值）：$V(x) = \sum_i W(x, t_i) V_i$。

注意，我们现在讨论的其实是由基集$B$所张出的拓展图灵机集$T$的子集$V$，以及由$V$中所有表达路径集$R$的子集$E$所构成的超图$(T, \mathrm{Rep}(T))$的子超图$(V, E)$，放在理论结构的问题上，就是所有命题构成的庞大网络中的很小一部分，所以随着理论的发展，这张超图实际上是在不断拓展的。

所以，下面的问题就是要如何确定源点的值$V_i$了。

这些值一般都是从外部来获得的，比如当我们考虑科学理论时，这些值可以是它们在实验上被证实的程度，而这些源点本身就是理论做出的预言。这样从对预言的实验验证情况及其置信程度就可以得到所有基础命题的权重值了。

当然，这样的赋值并不意味着每个节点的置信度就是这个值了，这是两码事。

这样，我们就可以回头来看弱等价集的问题了。

假定集$A$和$B$弱等价，这两个集合中的每个节点都通过实验被赋予了原始值，而后通过上述方式可以计算它们为整张超图$H$中所有节点所赋予的值（当然，支持集$O$并不作为源点来看），我们现在关注的是$A$为$B$中节点的赋值情况，以及反过来的$B$为$A$中节点的赋值情况。

我们令$V_B(A) = \sum_{x \in A} V_B(x)$，即用$B$来为$A$中节点提供的总赋值，反之亦然。

由于赋值越大基本意味着表达越短，从而也就基本可以意味着表达的难度越小，所以如果$V_B (A) > V_A (B)$，那基本上就意味着用$A$来表达整个$B$的难度更小（因为$V_B(x)$意味着表达$B$中元素所用的所有用到$x$的表达路径所提供的总权值，所以$V_B(A)$其实反应的是用$A$来表达$B$的情况）

在这种情况下，我们将会倾向于选择继续使用$A$来作为更重要的点集，而将$B$视为由$A$表达出来的“次要”子集。

当然，在实际计算的时候，使用完整的定义可能会面临无法计算的问题，而使用$\mathrm{UDR}$来计算则可能会出现漏值的情况，所以我们可以考虑另一种简化方式——

记$C(x; A)$使用$A$与支持集$O$中元素来表达$x$的最短表达式，所以我们来构造如下值：

$$
\tilde V_B (A) = \frac{1}{|B|} \sum_{x \in A} \left[ \frac{1}{D(C(x; B))^2} \sum_{y \in U(C(x; B)) \cap B} V(y) \right]
$$

这里$V(x)$当然就是作为源点的$x$通过外部得到的赋值。和之前的定义不同，这个定义实际上是“反向”了，$\tilde V_B (A)$给出了用$B$（以及支持集$O$）来表达$A$的“难度”。

范式转移

我们下面从超图$H$中选择一个点集$K$，它被称为$H$的表示集，赋值时的源点只能是表示集中的点。

接着，两张超图$H_1$和$H_2$的表示集是相同的，我们就成这两张超图是表示集$K$的两个不同的模。

下面，如果存在一组拓展图灵机$C$，使得$H_1$中能表达$K$中每一个节点$k$的所有表达$\mathrm{Rep}(k)$中存在一条表达路径$L_k$，其$U(L_k)$中的每一个节点都可以存在$H_2$中的节点通过$C$中元素映射到，就称$H_2$可以被$C$翻译为$H_1$，或者简单称为$H_2$可翻译为$H_1$，记为$H_2 \hookrightarrow H_1$，$C$被称为从$H_2$到$H_1$的翻译机。

$$
\forall k \in K : \exists L_k \in \mathrm{Rep}(k) \subset H_1 : \exists S \subset H_2 : C(S) = U(L_k)
$$

显然，$H_1$可翻译为$H_2$并不能保证$H_2$也可以翻译为$H_1$，如果两张超图可以彼此翻译，那事实上它们就是等价的。比如量子理论中的波动力学与矩阵力学这两套理论就是彼此等价的，可以相互翻译。

因此，超图也可以通过被翻译的方式被当做更大的超图的一部分而被扩张。

事实上，我们更希望看到的是原本两张彼此时间无法被翻译的超图$H_1$和$H_2$，结果可以被另一张超图$H_3$同时翻译。这样的扩展显然是更加喜闻乐见的。

比如麦克斯韦的电磁学理论便将电学和磁学这两个原本认为无关的领域被统一在了一起，而爱因斯坦的狭义相对论则将时间和空间被统一在了一起，广义相对论将运动学和引力结合在了一起。

由于翻译的存在，所以原本的基集在拓张后的超图中可能就不再是基集了，当这种改变的程度足够大时，就可以认为发生了一次基础替换——基础替换还不是范式转移。

超图的扩张并不是只有范式转移这一种方式。我们之前说过，超图中可能会存在两个点集，彼此之间没有超边连接，所以它们是彼此分离的。但可能会随着新的节点与相关超边的引入而将它们连在一起，这样同样是一种很常见的超图扩张，而这些扩张都不会严重地改变基集。

但，翻译的要求很严格，所以更可能出现的是部分翻译：

$$
\exists k \in K : \exists L_k \in \mathrm{Rep}(k) \subset H_1 : \exists S \subset H_2 : C(S) = U(L_k)
$$

即，只要能将部分$K$中的元素实现翻译即可，记为$H_2 \dot \hookrightarrow H_1$。如果$H_2$可以翻译为$H_1$，那其实只是拓张了功能，但并没有更换功能。而如果$H_2$可以部分翻译为$H_1$，那就是说后者中有些功能是前者不具备的，而前者的部分功能是后者不具备的，此时我们需要查看这两张超图在表示集上各自被外界赋的值，更大的就有更高的置信度被继续采纳，这点就和两个弱等价集之间做选择的时候是一样的。

前面我们提到，当通过翻译关系来进行超图扩张时，很可能会发生基础替换，但基础替换并不是范式转移。

而另一方面，我们注意到翻译机不仅仅可以连接两张不同的超图，也可能是连接同一张超图，从而实现一种到自身的翻译。事实上，翻译机本身就是一台拓展图灵机。不但如此，表达路径本身也是一台拓展图灵机（表达式的工作流程和$\lambda$演算是一致的），所以翻译机与超图的超边本身也是一张超图中的点——当然，这里当然不是在说原超图的对偶超图。

因此，一张超图上的可能会存在自翻译机集$\{C_i\} $，它将超图的不同部分映射到一起，然后交给同一组拓展图灵机$\{T_i\}$处理，得到的结果再被翻译回原来的部分中。这样我们就可以将$\left( \{C_i\}, \{T_i\} \right)$视为一个范式（paradigm）。

一个范式的存在就意味着一张超图上存在许多部分是彼此相似的，存在一种自相似性，它们在表达路径上具有相同的结构，我们总可以对一个表达式中的所有元素做逐个变换来得到另一根表达路径。

因此，如果扩张后的超图能改变原超图的范式，那我们才能说是完成了一次范式转移，否则可能只是增补了新的节点、路径，或者只是对节点做了映射变化，那从本质上来说并没有改变整体结构。