数学联邦政治世界观
超小超大

数学论文(无限时间图灵机) (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),接着再看更方便。

相关小说

快乐修仙队 连载中
快乐修仙队
星落凝成精
女仙帝带着凡间大部分女生和小部分男生修仙,成为有名的灵安宗,妹子们练成后也会来帮助凡间女子脱离哭海
2.2万字9个月前
白真折颜 连载中
白真折颜
紫霞宝贝
这篇小说主要讲的是什么呢?我先不告诉你,你们慢慢看吧,反正是跟白真折颜暮芸有关系的
0.6万字9个月前
猫王殿下:爱妃,你好甜! 连载中
猫王殿下:爱妃,你好甜!
叶小馨
慕安妮意外救了一只公猫咪,好好照顾它,可没想到,这只猫居然是只色.猫,半夜爬上她的床,往这亲亲,那蹭蹭。更没想到成人形的它更可恶。  “你…......
10.4万字9个月前
烽烟背后,情缘难了 连载中
烽烟背后,情缘难了
沦陷月殇
在阴阳逆转的背后,在困难风浪的尖端,有你一直陪着我。我爱你,永远爱你。
9.4万字9个月前
拐个妖王做对象 连载中
拐个妖王做对象
冷殇~东方明珠
一次醒来竟然无意中穿成了月影山中的无名小妖?还成天被欺负?看我成为月影山的逆天存在着,顺便拐个妖王做对象![该作品4月30日已经完成签约,禁......
9.8万字9个月前
海棠无香之明镜高悬 连载中
海棠无香之明镜高悬
Bandy
月色撩人不及昀离昀离之逝不若星陨明镜高悬繁星涅槃
6.5万字9个月前