数学论文（无限时间图灵机） (7-1)

注：本章（2/2）！

问题5. 每一个具有无限时间可计算商表示的结构都有一个无限时间可计算表示？

在有限时间理论中，或者对于N上的结构，答案当然是肯定的。但在R上结构的完全无限时间上下文，答案取决于集合论背景

定理6. 问题5的答案与ZFC无关。明确地

（1） 与ZFC相对一致的是，具有无限时间的每个结构都是可计算的商表示具有无限时间的可计算表示。

（2） 与ZFC相对一致的是，有一个结构具有无限时间可计算的商表示，但没有无限时间可可计算的表示。

让我们简要概述一下证据中出现的一些想法。为了建造结构的无限时间可计算表示，给定可计算商表示，我们想以某种方式从每个等价类中选择一个代表，在计算有效的方式，并在这些代表的基础上构建一个结构。在下面集合论假设V=L，我们可以附加到每个等价的L-东成员真正的A级护卫，其力量足以表明它是其L东部成员类，并用这些被护送的实数对构建一个可计算的表示。（特别是，新的演示文稿不仅仅是由原始类别的代表构建的，因为这些real可能太弱；他们需要护送人员的帮助。）因此，如果V＝L，那么每个具有可计算商表示的结构都具有可计算表示。

在独立性的另一方面，我们用强迫的方法证明了陈述2。

结构hω1，＜i总是有一个由实数编码的良好阶建立的可计算商表示，但存在没有无限时间可计算集的强迫扩展在描述性集合论的基础上，大小为ω1。因此，在这些扩展中，hω1，＜i具有可计算的商表示，但没有可计算的表示。

让我们也简要讨论一些有序计算的替代模型这是无限时间图灵机所产生的。Peter Koepke[Koe05]介绍了序图灵机，它通过扩展来推广无限时间图灵机胶带超限序数长度。相应地调整了限额规则，以便这台机器可以利用这个额外的空间。具体来说，而不是使用特殊的极限状态，序数图灵机在它们的（有限多个）上有一个固定的阶状态，并且在任何极限阶段，该状态被定义为先前状态的lim-inf。这个然后将磁头位置定义为机器运行时磁头位置的lim-inf之前处于所产生的极限状态。为了一致性，Koepke定义磁带的单元使用先前单元值的lim-inf（而不是使用无限时间图灵机）。如果头部在极限位置从单元格向左移动，则它一直出现在第一个单元格的左侧。

因此，这些机器为序数上的函数提供了计算模型，以及序数类的可判定性概念。主要定理是的幂这些机器本质上与G模型的可构建宇宙的机器相同。

定理7（Koepke）. 序数图灵机可判定的序数集，具有有限许多序数参数正是G模型的可构造宇宙L中的序数集。

其他几种序数计算的无限模型都是基于序数寄存器的概念，并产生了丰富的理论。参见[Koe05]、[KS06]、[KK06]、[CS09]，[CFK+10]、[HM07]、[HM09]和[HLM07]。

3.无限时间可计算等价关系理论

最近，我们介绍了Borel等价关系理论的自然相似性。其中将无限时间可判定关系与无限时间可计算归约函数进行比较。这在一定程度上是由于研究中的偶尔需要Borel等价关系超越了Borel。事实上，一个更强大的可约性概念可能能够准确地比较更复杂的关系。特别是，我们将能够考虑由于无限的时间复杂性而产生的新关系类。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。