编号、随机性与格理论概念的计算强度

### 编号、随机性与格理论概念的计算强度 在计算理论和格理论的研究中，编号和随机性的概念以及格理论中的一些关键概念，如完备性和紧致性，有着重要的地位。本文将深入探讨这些概念，包括有效编号的存在性、Friedberg编号，以及格理论概念的计算强度。 #### 编号与随机性相关概念 首先来看一些关于编号和随机性的基本概念和结论。 有观点认为可以证明存在 $R[c + 1, \infty)$ 的Friedberg编号，其思路是对 $L1$ 进行修改，用 $1^{d_c + n}$ （$d_c$ 足够大）替换字符串 $1^n$。 定理6和7表明，$\Sigma_0^2$ 类中的左c.e.成员通常比 $\Pi_0^1$ 类中的左c.e.成员更容易枚举，这可能是由于左c.e.实数的 “$\Sigma_0^n$ 性质”（$n = 1$）。 以下是不同集合族的有效编号和Friedberg编号的存在情况： | 集合族 | 有效编号 | Friedberg编号 | | --- | --- | --- | | 所有 $\Pi_0^1$ 类 | 是（由定理10） | - | | 所有左c.e.实数 | 是（由定理4） | - | | $\Pi_0^1$ 类 $C$，$\mu C > 0$ | 是（由定理10） | - | | MLR中的左c.e.实数 | 是（由定理5） | - | | $\subseteq A[0, c]$ 的 $\Pi_0^1$ 类 | 是（由命题2） | - | | $\subseteq MLR$ 的 $\Pi_0^1$ 类 | 否（由定理8） | - | | $A[0, c]$ 中的左c.e.实数 | 否（由定理6） | - | 这里 $MLR = \bigcup_{c \in \omega} A[0, c]$，并且集合 $A[c_1, c_2]$（$0 \leq c_1 \leq c_2 < \infty$）是否为空似乎取决于Kolmogorov复杂度所基于的通用前缀机。由此引出一个问题：是否存在 $0 \leq c_1 \leq c_2 < \infty$ 以及Kolmogorov复杂度所基于的通用机的一种选择，使得 $A[c_1, c_2]$ 没有有效枚举？ 对于 $\Pi_0^1$ 类的族，有如下定义： - 设 $C$ 是 $2^\omega$ 的闭子集族。如果存在一个一致可计算的树族 $\{T_e\}_{e \in \omega}$（即 $\{\langle\sigma, e\rangle: \sigma \in T_e\}$ 是可计算的，且 $\sigma^\frown\tau \in T_e$ 意味着 $\sigma \in T_e$），使得 $C = \{[T_e] : e \in \omega\}$，则称 $C$ 有一个可计算枚举。 - 设 $C$ 是 $2^\omega$ 的闭子集族。如果存在一个 $\Pi_0^1$ 集 $S \subseteq 2^\omega \times \omega$，使得 $C = \{\{X : (X, e) \in S\} : e \in \omega\}$，则称 $C$ 有一个有效枚举。 并且可以证明，对于 $2^\omega$ 的闭子集族 $C$，有可计算枚举和有有效枚举这两个条件是等价的。 #### 有效编号的存在性 接下来探讨有效编号的存在性问题。 设 $P \subseteq 2^\omega$，$C_P$ 是包含在 $P$ 中的所有 $\Pi_0^1$ 类的集合，$N_P$ 是包含在 $P$ 中的所有非空 $\Pi_0^1$ 类的集合。如果 $P$ 满足以下性质： - $P$ 是余稠密的：没有锥 $[\sigma]$（$\sigma \in 2^{<\omega}$）包含在 $P$ 中。 - $P$ 在移位下是封闭的：如果 $x \in P$，那么 $\sigma^\frown x \in P$。 - $N_P \neq \varnothing$。 那么 $C_P$ 或 $N_P$ 都没有有效编号。这是因为如果 $N_P$ 有编号，那么 $C_P$ 也有编号（因为若 $\varnothing \in C_P$，可以简单地将 $\varnothing$ 的索引添加到