关于序数可计算性

作者: XyanXcllet | 来源:发表于2020-01-31 23:35 被阅读0次

本文依照目前最新的有关于超计算（Hypercomputation）的书籍：Merlin Carl 的序数可计算性编写。

相比与 Apostolos Syropoulos 的超计算（Hypercomputation）。Merlin Carl 的这一本专注于超计算内部的其中一个分支。所使用的数学工具更多。范围更广。具有相当的难度。非常“硬核”。

在超计算内，通常比较不同的 Oracle Machines 的计算能力会使用诸如算术层级，分析层级来进行对比。不过 Merlin Carl 采用了截然不同的方法：使用了哥德尔的可构造宇宙 $L$ 来表示。不同的序数性 Oracle Machines 会占据哥德尔可构造宇宙内的不同的层级。

首先注意： $\alpha\in \text{Ord}$ 为机器的带子的长度。 $\beta \in \text{Ord}$ 为机器的计算时间。

ordinal register machine：等价于一个 weak Infinite Time $\alpha$ - Register Machines 其中 $\alpha = \text{Ord}.$ 计算能力有：

- 若一个集合 $x$ 是 ordinal register machine 可计算的当且仅当 $x \in L.$

- ordinal register machine 限定在 $\alpha \in \text{Ord}.$ 有 $\alpha$ - register machine。可判定集合 $x$ 当且仅当 $x \in L_{\alpha } .$

- 若 $\alpha \in \omega$ 那么是 weak Infinite Time Register Machines。可判定集合 $x$ 当且仅当 $x \in L_{\omega _{1}^\text{CK} } =\Delta _{1}^1$

$\alpha$ - Infinite Time Register Machines 计算能力有：

- 可判定集合 $x$ 当且仅当 $x \in \mathcal{P}(\alpha )\cap L_{\beta } .$ 其中 $L_{\beta }$ 为 $\alpha$ - ITRM 的一个可计算编码。若 $\alpha \in \omega$ 则可判定集合 $x$ 当且仅当 $x \in L_{\omega _{\omega }^\text{CK} } .$

- 若是对于一个无限基数 $\kappa$ 那么 $\kappa$ - ITRM 可判定集合 $x \in L_{\kappa+1 } .$

对于序数拓展的图灵机而言，这个机器家族极其庞大，一共会存在 $\text{Ord}\times \text{Ord}$ 多个分支：

- $(\alpha ,\beta )$ - Turing machine。

- $\alpha$ - Turing machine 其中 . $\alpha =\beta.$ 则可判定集合 $x \in \mathbf{\Delta }_{1} (L_{\alpha }).$

- 普通的无限时间图灵机，则可判定集合 $x \in \mathcal{P}(\omega )\cap L _{\lambda} .$

- 若无限时间图灵机的 scratch tape 只可以写入有限多个 1 （等价于 0）则可判定集合 $x \in L_{\omega _{1}^\text{CK} }.$

- $\alpha$ - 无限时间图灵机其中 $\alpha \in \text{Ord},\beta = \text{Ord}.$ 则可判定集合 $x \in \mathcal{P}(\alpha )\cap L _{\lambda (\alpha )} .$ 其中 $\lambda (\alpha )$ 表示为在一个谕示 $x \subseteq\alpha \in \text{Ord}$ 内的 $\alpha$ - writable ordinals 的上确界。

- Ordinal Turing Machines 目前最强的机器。 $\alpha = \text{Ord},\beta = \text{Ord}.$ 则可判定集合 $x \in \mathcal{P}(\omega )\cap L .$

- infinite Ordinal Turing Machines 其内部状态的 index 可以是超限序数。那么可判定集合 $\forall x(V=L).$

在 Chapter 4 的 Recognizability 内，给出了最强的 Ordinal Turing Machines 的最新计算强度。若现在一个 $X\subseteq \mathcal{P}(\omega )$ 那么定义 $\text{rcl}(X)$ 作为 recognizable closure 且对于 OTM。最终有 $\text{RCL}=\text{rcl}(\emptyset).$

- 在 $V=L$ 的框架下： $\text{RCL} =\mathcal{P}^L(\omega ).$

- 若大基数 $0^\sharp$ 存在那么 $0^\sharp\in \text{RCL} .$

- Finally if $\exists M\models \text{Woodin}$ then $M\in \text{RCL} .$

奇葩的模型：无限时间 BSS Machine。把 BSS Machine 嵌入至序数内：

- 可判定集合 $x \in \mathcal{P}(\omega )\cap L _{\omega ^\omega } .$

后面几个章节介绍了这些序数性 Oracle Machines 所各自对应的复杂度，不可解度。各自的 $\text{P vs NP}$ 以及无限计算的哲学探讨等等。

关于哥德尔可构造宇宙 $L$ ：

$\begin{align} L_0& = \emptyset \\ L_{\alpha+1}& = \mathcal{P}_{\operatorname{Def}}\left(L_{\alpha}\right)\\ L_\alpha&=\bigcup_{\beta<\alpha} L_{\beta }\text{ for limit }\alpha\\ L&=\bigcup_{\alpha\in \text{Ord}}L_\alpha\alpha\\ \end{align}\\$

其中 $\text{def}(x)=\left\{ y\subseteq x |y \text{ is definable over }\left \langle x,\in \right \rangle\right\}$

关于序数可计算性

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读