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

注：本章共划分（1/2）！

摘要：我们描述了无限时间图灵机的基本理论和最近的一些发展，包括无限时间度理论，无限时间复杂性理论，以及无限时间可计算模型理论。我们特别关注的是无限时间图灵机上等价关系的层次分析reals，类似于由Borel可约性产生的理论。我们定义了一个概念具有无限的时间可约性，这将Borel理论的大部分提升到∆类∼1.2.在一个令人满意的方式。

无限时间图灵机卓有成效地扩展了普通图灵机的运算到超限有序时间，并通过这样做提供了关于的可计算性的鲁棒理论reals。集合论、描述性集合论和在可计算性理论中，该方法在实数上提供了无限的可计算性和可判定性概念，这些概念以非平凡的方式攀升到描述性集合论层次（∆1.2.)同时保持强计算性质。无限的时间图灵机，我们有无数经典概念的无限类似物，包括无限时间图灵度，无限时间复杂性理论，无限时间可计算模型理论，现在也是Borel等价理论的无限时间模拟Borel可约性下的关系。

在这篇文章中，我们将简要回顾机器及其基本理论，以及然后更详细地解释我们最近将无限时间可计算性应用于Borel等价关系理论的相似性，在[CH11]中给出了对其的完整描述。

这个应用程序的基本思想是通常取代Borel可约性的概念在该理论中使用了具有无限时间可计算可约性形式，并研究了伴随的等价关系层次。这种方法保留了大部分Borel分析和结果，同时也阐明了似乎超出Borel理论范围的等价关系层次的一部分，包括许多高度规范的等价关系无限时间可计算但不是Borel的等价关系，例如可数结构的不同类的同构关系。

本文的主要部分改编自调查[Ham07]和[Ham05]以及来自我们关于无限时间可计算等价关系的文章[CH11]。无限的时间Hamkins和Kidder于1989年首次研究了图灵机，Hamkins和Lewis提供了核心介绍[HL00]。这一理论现在已经得到了扩展许多其他人，包括Philip Welch、Peter Koepke、Benedikt L¨owe、Daniel Seabold，拉尔夫·辛德勒、维奈·德奥拉利卡、拉塞尔·米勒、史蒂夫·华纳、贾科莫·伦齐、埃里希·蒙特里昂、塞缪尔·科斯基等人。该理论的许多前身包括BlumShub-Smale机器（20世纪80年代）、Büuchi机器（60年代）及其伴随的发展，Barry Burd的极限“模糊”图灵机模型（1970年代），α-递归和E递归理论的广泛发展，高等递归理论的一部分（自20世纪70年代）、Jack Copeland的加速图灵机（20世纪90年代）、Ryan Bissell Siders的序数机（90年代），以及最近的Peter Koepke的序数图灵机和序数寄存器机（2000年代）。涉及无限时间图灵的扩展文学机器包括[HL00]、[Wel99]、[Wel00a]、[Wel00b]、[L¨01]、[HS01]、[HL02]、[Sch03]，[HW03]、[Ham02]、[Ham04]、[LM04]、[DHS05]、[HMSW07]、[Ham05]、[Wel]、[Wel05]、[Coe05]，[Ham07]、[HM09]、[HM07]和其他。

1.无限时间图灵机综述

无限时间图灵机的硬件与它们的经典有限时间机完全相同时间对应物，头在半无限长的纸带上来回移动，根据有限多个有限程序的严格指令写0和1州。关于无限时间图灵机的新之处在于，它们的运算被扩展到超限有序时间。为了方便起见，这些机器采用三磁带模型，具有用于输入、暂存和输出的独立磁带。机器

q

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