摘要：我們描述了無限時間圖靈機的基本理論和最近的一些發(fā)展，包括無限時間度理論，無限時間復雜性理論，以及無限時間可計算模型理論。我們特別關(guān)注的是無限時間圖靈機上等價關(guān)系的層次分析reals，類似于由Borel可約性產(chǎn)生的理論。我們定義了一個概念具有無限的時間可約性，這將Borel理論的大部分提升到?類～1.2.在一個令人滿意的方式。
無限時間圖靈機卓有成效地擴展了普通圖靈機的運算到超限有序時間，并通過這樣做提供了關(guān)于的可計算性的魯棒理論reals。集合論、描述性集合論和在可計算性理論中，該方法在實數(shù)上提供了無限的可計算性和可判定性概念，這些概念以非平凡的方式攀升到描述性集合論層次（?1.2.)同時保持強計算性質(zhì)。無限的時間圖靈機，我們有無數(shù)經(jīng)典概念的無限類似物，包括無限時間圖靈度，無限時間復雜性理論，無限時間可計算模型理論，現(xiàn)在也是Borel等價理論的無限時間模擬Borel可約性下的關(guān)系。
在這篇文章中，我們將簡要回顧機器及其基本理論，以及然后更詳細地解釋我們最近將無限時間可計算性應用于Borel等價關(guān)系理論的相似性，在[CH11]中給出了對其的完整描述。
這個應用程序的基本思想是通常取代Borel可約性的概念在該理論中使用了具有無限時間可計算可約性形式，并研究了伴隨的等價關(guān)系層次。這種方法保留了大部分Borel分析和結(jié)果，同時也闡明了似乎超出Borel理論范圍的等價關(guān)系層次的一部分，包括許多高度規(guī)范的等價關(guān)系無限時間可計算但不是Borel的等價關(guān)系，例如可數(shù)結(jié)構(gòu)的不同類的同構(gòu)關(guān)系。
本文的主要部分改編自調(diào)查[Ham07]和[Ham05]以及來自我們關(guān)于無限時間可計算等價關(guān)系的文章[CH11]。無限的時間Hamkins和Kidder于1989年首次研究了圖靈機，Hamkins和Lewis提供了核心介紹[HL00]。這一理論現(xiàn)在已經(jīng)得到了擴展許多其他人，包括Philip Welch、Peter Koepke、Benedikt L¨owe、Daniel Seabold，拉爾夫·辛德勒、維奈·德奧拉利卡、拉塞爾·米勒、史蒂夫·華納、賈科莫·倫齊、埃里希·蒙特里昂、塞繆爾·科斯基等人。該理論的許多前身包括BlumShub-Smale機器（20世紀80年代）、Büuchi機器（60年代）及其伴隨的發(fā)展，Barry Burd的極限“模糊”圖靈機模型（1970年代），α-遞歸和E遞歸理論的廣泛發(fā)展，高等遞歸理論的一部分（自20世紀70年代）、Jack Copeland的加速圖靈機（20世紀90年代）、Ryan Bissell Siders的序數(shù)機（90年代），以及最近的Peter Koepke的序數(shù)圖靈機和序數(shù)寄存器機（2000年代）。涉及無限時間圖靈的擴展文學機器包括[HL00]、[Wel99]、[Wel00a]、[Wel00b]、[L¨01]、[HS01]、[HL02]、[Sch03]，[HW03]、[Ham02]、[Ham04]、[LM04]、[DHS05]、[HMSW07]、[Ham05]、[Wel]、[Wel05]、[Coe05]，[Ham07]、[HM09]、[HM07]和其他。
1.無限時間圖靈機綜述
無限時間圖靈機的硬件與它們的經(jīng)典有限時間機完全相同時間對應物，頭在半無限長的紙帶上來回移動，根據(jù)有限多個有限程序的嚴格指令寫0和1州。關(guān)于無限時間圖靈機的新之處在于，它們的運算被擴展到超限有序時間。為了方便起見，這些機器采用三磁帶模型，具有用于輸入、暫存和輸出的獨立磁帶。機器
q
input：0 0 1 1 1 1 0 0 ...
scrαtch：1 1 0 1 0 0 1 0 ...
output：0 0 1 0 1 0 1 1 ...
根據(jù)到程序指令。計算被簡單地擴展到限制有序階段定義機器的極限配置。其想法是盡可能多地保留計算到那個階段為止一直在創(chuàng)建的信息，將其保留在極限配置中，作為早期配置的一種極限。明確地在任何極限有序階段ξ，機器進入我們所說的極限狀態(tài)，其中一個區(qū)分狀態(tài)以及開始狀態(tài)和停止狀態(tài)；磁頭被重置為第一個單元在左邊；并且磁帶的每個單元都用先前值的limsup更新顯示在該單元格中。已經(jīng)指定了機器的完整配置在階段ξ，計算現(xiàn)在可以繼續(xù)到階段ξ+1，以此類推只有當機器明確進入停止狀態(tài)時才會給出輸出，并且計算當這種情況發(fā)生時停止。
由于磁帶自然地容納了無限的二進制字符串——而且有很多頭檢查每個單元格的時間——輸入和輸出到的自然上下文機器是Cantor空間2ω，我們用R表示它，并稱之為實數(shù)。因此機器提供了實數(shù)上可計算性的無限概念。一個程序p計算偏函數(shù)ξp。
.R→ R、如果程序p在輸入x上，則由ξp（x）=y定義產(chǎn)生輸出y，其中計算的輸出是輸出磁帶的內(nèi)容，當機器進入停止狀態(tài)。子集A?R是無限時間可判定的，如果A的特征函數(shù)是無限時間可以計算的。集合A是無限時間半可判定的，如果常偏函數(shù)1? A是可計算的。這相當于A是域的無限時間可計算函數(shù)（但不一定等同于A是這樣的函數(shù)的范圍）。[HL00]中的初步結(jié)果表明，算術(shù)集是正是那些在時間上可判定的一致小于ω2和超算術(shù)的集合是那些在時間上比某些遞歸序數(shù)更短的可判定集合。的力量。
然而，機器在描述集合論中達到了比這高得多的水平等級制度。
例如，每個π11.和∑11.集合是無限時間可判定的。要看到這一點，只需表明完整的π11.集合WO由編碼ω上的良序關(guān)系的實數(shù)組成，是無限時間可計算的。這是通過[HL00，定理2.2]，我們想在這里畫一下。給定一個實數(shù)x，我們將其視為編碼ω上的關(guān)系式，其中n?m當且僅當x的h n，mi位為1。斷言?是一個線性階是x中的算術(shù)，因此很容易由機器確定。
之后，機器將通過計數(shù)來檢查基礎(chǔ)是否良好順序，這取決于計算步驟本身是有序的。
具體來說，機器將當前最小元素的初始猜測放在關(guān)系?，在遇到它們時用更好的猜測進行更新。在每次修訂時機器會閃爍某個主標志，這樣在極限階段，機器就可以知道猜測被無限頻繁地更改，表明基礎(chǔ)不健全（機器應該重置在極限級的極限處的主標志）。否則，真實的電流最小元素已經(jīng)找到，因此機器可以從的字段中刪除所有提及它的內(nèi)容由x編碼的關(guān)系。重復此操作，算法實際上系統(tǒng)地擦除由輸入實數(shù)編碼的關(guān)系的有根據(jù)的初始段，直到要么什么都沒有發(fā)現(xiàn)了左或無根據(jù)的部分，這兩者都可以確定。通過這種方式，WO的成員資格是無限時間可決定的。由此可知，每個π11.和∑11.集合是無限的。
時間是決定性的，因此機器正確地爬升到?1.2.。同時，的類無限時間可判定集很容易被觀察到包含在?中1.2.，實際上是?類1.2.在無限時間跳躍運算下是封閉的，因此由一個顯著的無限時間圖靈度的一部分。
盡管超限，但計算本質(zhì)上是可數(shù)的，因為共最終性論證證明，每一次計算要么暫停，要么重復一些可數(shù)序數(shù)階段。如果存在計算，則序數(shù)α被認為是可計時的恰好停在α上第th步。如果實數(shù)x是計算的輸出ξp（0），則實數(shù)x是可寫的，而序數(shù)是可寫的，如果它是由這樣的實數(shù)編碼的。因為只有可計數(shù)的在許多程序中，因此只有可計數(shù)的多個可計時和可寫的序數(shù)?？捎嫊r和可寫的序數(shù)擴展到所有遞歸序數(shù)和遠遠超出；它們的上確界是遞歸不可訪問的等等?？蓪懙男驍?shù)形成序數(shù)的初始段，因為每當一個序數(shù)是可寫的，那么編寫它的算法就可以很容易地修改為任何較小的序數(shù)編寫代碼。但是對于可計時的序數(shù)來說，情況并非如此；在可計時的序數(shù)中，有無（無參數(shù)）無限時間圖靈的越來越復雜的禁區(qū)機器可能會停下來。
讓我們快速勾勒出這樣一個論點，即可計時序數(shù)中存在這樣的差距，因為這是有序反射中一個有趣的練習，它構(gòu)成了許多方法的基本方法后來的理論建構(gòu)?？紤]模擬上所有程序的算法同時輸入0，通過一些保留和管理sufi的記賬方法-每個程序都有足夠的獨立空間，模擬ω每個程序的許多計算步驟在每個ω實際計算的許多步驟中。我們的算法可能會仔細跟蹤哪些程序已經(jīng)停止，并注意找到?jīng)]有程序停止的階段。由于這樣一個階段存在于所有可計時序數(shù)的上確界之上，我們最終一定會找到這樣的舞臺。由于我們的算法可以識別第一個在這樣的階段，我們可以安排它在這一發(fā)現(xiàn)后立即停止。因此，我們描述了一種計算過程，它將在比沒有計算停止的階段，因此在可計時的序數(shù)中存在間隙，如渴望的對該算法的仔細分析表明，任何可計時序數(shù)之后的第一個間隙都具有階型ω，本質(zhì)上是因為ω需要許多額外的步驟才能實現(xiàn)已經(jīng)達到了一個缺口。改進的算法搜索更長的間隙，并表明必須是在越來越復雜的可容許極限階段越來越復雜任何可計時或可寫的序數(shù)α，都存在大小至少為α的間隙。這些的結(jié)構(gòu)gap表現(xiàn)出與無限時間停頓問題相同的復雜性。
盡管在[HL00]中已經(jīng)確定了可計時和可寫的序數(shù)同樣的訂單類型，也許該論文中留下的主要問題是這些序數(shù)的上確界是相同的。這件事得到了菲利普的肯定Welch在[Wel00b]。另一種描述結(jié)果的方式是，每當程序打開輸入x產(chǎn)生一個停止的計算，然后有另一個計算寫出該計算的證書，整個計算歷史的真實編碼，包括有序關(guān)系，其順序類型是計算的長度。這很重要事實遠非顯而易見，它依賴于對最終可寫性的微妙處理，并構(gòu)成這是該理論許多進一步發(fā)展的基礎(chǔ)，包括我們的應用在本文中提及。
上述計數(shù)論證的反映方面包括觀察到可能遇到的實數(shù)的任何可判定性質(zhì)在計算過程中，必須持有一個可寫的實數(shù)，因為我們可以開始計算搜索以找到這樣的見證并在找到時輸出它。這個想法極大地推廣了Philip Welch的λ-ζ-∑定理。具體而言，[HL00]定義如果存在x出現(xiàn)在從上的某個點輸出磁帶（即使計算沒有停止），并且如果x在計算期間的任何階段出現(xiàn)在任何磁帶上，則它是意外可寫的。通過用實數(shù)編碼序數(shù)，我們得到了最終可寫和意外可寫的概念序數(shù)。如果λ是可計時或可寫序數(shù)的上確界，則ζ是最終可寫序數(shù)，∑是意外可寫序數(shù)的上確界，則[HL00]建立λ＜ζ＜∑。Welch[Wel00a]斷言的λ-ζ-∑定理。
此外，Lλ?∑1Lζ圖案這個結(jié)果準確地表達了算法可能會下降的意義見證人從意外可寫領(lǐng)域進入最終可寫或可寫領(lǐng)域王國。證明和結(jié)果的核心是每一次計算都是重復的∑階段的ζ配置。
經(jīng)典有限時間可計算性理論的許多基本構(gòu)造延續(xù)到無限的時間語境。例如，我們可以證明smn定理的無限時間相似性、遞歸定理和無窮大的不可判定性時間停滯問題，本質(zhì)上是經(jīng)典論點。其他一些經(jīng)典事實，但是，不要直接一概而論。例如，在無限時間的情況下，這是不正確的。如果函數(shù)f的圖是半可判定的，那么該函數(shù)是可計算的。這是以下情況的結(jié)果：
定理1（損失旋律定理）。存在一個實c，使得{c}是無限時間可判定的，但是c是不可寫的。
真正的c，一首丟失的旋律，你不能自己唱，盡管你能認出。當有人唱給你聽時，它是或否，表現(xiàn)出足夠的內(nèi)部結(jié)構(gòu)，{c}是可決定，但本身太復雜，無法寫入。也就是說，我們可以識別給定實數(shù)y是否為c，但我們不能從無到有產(chǎn)生c。函數(shù)f（x）=c
因此，常數(shù)值c是不可計算的，因為c不可寫，但圖是可判定的，因為我們可以識別一對是否具有形式（x，c）。
停頓問題的無限時間模擬分為黑體和黑體版本，h={p|ξp（p）↓}并且H＝{（p，x）|ξp（x）↓}，分別地這都是半可判定和不可判定，但在無限上下文中，它們不是可計算的相等的預言計算的概念上升到無限的上下文中，并產(chǎn)生了一個理論相對可計算性和豐富的學位結(jié)構(gòu)。與經(jīng)典理論相反。
然而，在N上，在無限時間的上下文中，我們有兩種自然的神諭可供使用在oracle計算中，對應著二階性的理論。第一個人可以使用一個真正的個人作為神諭，完全按照經(jīng)典的方式，通過連接一個oracle磁帶，上面寫著real的值。這相當于修復一個補充輸入?yún)?shù)，可以被視為產(chǎn)生了黑體理論無限可計算性，就像在描述性中允許任意實參數(shù)一樣黑體?的集論處理～1.1.和π～1.1.（我們將明確采用這樣的黑體透視我們在無限時間下等價關(guān)系理論中的應用還原性。）然而，第二，人們自然希望以某種方式使用一組real作為甲骨文，盡管我們一般不能指望在磁帶上寫下這樣的一套（也許它甚至是不可計數(shù)的）。相反，oracle磁帶在計算開始時是空的，并且在計算期間，機器可以在該磁帶上自由地寫入；每當算法調(diào)用它時，機器可能會進行成員身份查詢，詢問是否真實當前寫在oracle磁帶上的是否是oracle的成員。因此，該機器能夠知道它能產(chǎn)生的任何真實，無論真實是否在預言集中。
這樣的預言計算產(chǎn)生了相對可計算性的概念p（x）和
因此，一個無窮時可變約簡a≤∞B的概念及其伴隨式無限時度關(guān)系A(chǔ) lect∞B。對于任意一個集合A，我們都有光面跳躍A▽。而黑體跳躍AH，對應于兩個停頓問題，與A相對應。
黑體跳躍比淺色跳躍高得多，因為[HL00]確定了A＜∞A▽＜∞啊，還有A▽H≠∞AH和許多其它有趣的相互作用。波斯特問題的無限時間相似性，即是否存在介于0和跳躍0之間的中間半可判定度▽，由[HL02]于解決一個雙向切入的答案：
定理2。波斯特問題的無限時間模擬既有肯定的解決方案，也有否定的解決方案。
?。?）不存在0＜∞z＜∞0的實數(shù)z▽.
（2）存在實數(shù)A的集合，其中0＜∞A＜∞0▽.事實上，實A的半可判定集是不可比的。
意外可寫實數(shù)的度數(shù)是線性排序的，實際上形成了有序類型ζ+1的有序?qū)哟?，這也對應于它們在任何計算中最早出現(xiàn)的順序。在其他作品中，Welch[Wel99]在無限時間的圖靈度。Hamkins和Seabold[HS01]分析了一個磁帶與多帶無限時間圖靈機和Benedikt L¨owe[L¨01]觀察了無限時間圖靈機與真理修正理論之間的聯(lián)系。
2.一些應用和擴展
讓我們簡要介紹一下最近的發(fā)展和無限時間的延伸圖靈機，如無限時間復雜性理論的興起和介紹無限時間可計算模型理論。在此之后，在以下部分中，我們將更詳細地介紹無限時間圖靈機在類似于Borel等價關(guān)系理論。
Ralf Schindler[Sch03]通過求解P與NP問題的無限時間圖靈機模擬。定義多項式類P在無限時間的上下文中，Schindler簡單地觀察到所有實數(shù)具有長度ω，且ω的多項式函數(shù)受形式為ωn的多項式函數(shù)的約束。
因此，他定義了一個集合a?R在P中，如果有一個程序P和一個自然數(shù)n使得p決定A，并在ωn之前的時間內(nèi)停止所有輸入.集合A在NP中，如果存在是程序p和自然數(shù)n使得x∈a當且僅當存在y使得p接受（x，y），并且p在小于ωn的時間內(nèi)停止所有輸入Schindler證明了P≠NP
對于[Sch03]中的無限時間圖靈機，使用從描述集理論到分析類P和NP的復雜性。這已經(jīng)在聯(lián)合中推廣對[DHS05]進行如下運算，其中類co-NP由集合的補集組成在NP中。
定理3.
P≠關(guān)于無限時間圖靈機的NP?co-NP。
此證明出現(xiàn)在[DHS05]中。由此可見，P≠無限時間圖靈機的NP。（這個結(jié)果與有限經(jīng)典P無關(guān)≠NP問題。）
P背后的一些結(jié)構(gòu)性原因≠NP?co-NP是通過放置類來揭示的使用計算的復雜性類Pα和NPα的較大層次中的P和NP大小限制在α以下。[DHS05]中的結(jié)果表明，例如，類NPα對于ω+2≤α≤ω1是相同的CK，但無論如何，Pα+1（任何可計時極限的Pα+2序數(shù)α。如下所示，由于Pα在類NPα≠co-NPα的同時穩(wěn)步增加保持不變，對于ω+2≤α＜ω1的任何序數(shù)α，Pα
因此，P≠NP?co-NP。然而，我們在上確界ω1處獲得相等CK與Pω1CK=NPω1CK?co-NPω1CK。
事實上，這是等式?1的一個例子
1 =Σ11∩Π11.，從而可以開始看看無限時間圖靈機理論是如何自然地發(fā)展成描述集的學說
這種相同的不等式模式Pα（NPα，
當α嚴格位于可計時序數(shù)的連續(xù)塊內(nèi)時，對于在可計時序數(shù)中開始間隙的任何β，對應的Pβ=NPβ≠co-NPβ。在里面
此外，對于其他復雜度類P+、P++和PfBenedikt L¨owe已經(jīng)引入了PSPACE的類似物。
在[HMSW07]中介紹了無限時間可計算模型理論的主題。
可計算模型理論是著眼于結(jié)構(gòu)和理論的可計算性的模型理論。無限時間可計算模型理論利用無限時間圖靈機提供的無限時間可算性概念來執(zhí)行該程序。經(jīng)典理論始于幾十年前，其主題包括可計算完備性（每個可判定理論都有可判定模型嗎？）和可計算分類性（每個同構(gòu)的可計算模型對都有可計算同構(gòu)嗎？），該領(lǐng)域現(xiàn)在已經(jīng)成熟為復雜度譜的復雜分析可數(shù)模型和理論。
更廣泛背景的動機是，雖然經(jīng)典的可計算模型理論必然局限于可數(shù)模型和理論，無限可計算性上下文允許建立在現(xiàn)實基礎(chǔ)上的無數(shù)模型和理論?？捎嬎隳Ｐ屠碚撝械脑S多計算結(jié)構(gòu)都是從建立在N，使用有限時間可計算性，到建立在R上的結(jié)構(gòu)，使用無限時間可計算。不可計數(shù)的上下文打開了新的問題，例如無限可計算L¨owenheim-Skolem定理，它沒有有限時間的相似性。幾個最自然問題被證明是獨立于ZFC的。
在聯(lián)合工作[HMW07]中，我們定義了一個模型a=hA。i是無限時間可計算的，如果A?R是可判定的，并且所有函數(shù)、關(guān)系和常數(shù)都是一致的無限時間，可根據(jù)其G模型代碼和輸入進行計算。結(jié)構(gòu)A是可判定的，如果可以計算出A|=[ˉ一]給定pΓq和ˉ一理論T是無限時間可判定的，如果關(guān)系T?Γ在pΓq中是可計算的。因為我們想處理不可計數(shù)的語言，G模型代碼的自然上下文是R而不是N。
當然，最初的問題是完全性定理的無限時間可計算模擬：每個一致的可判定理論都有一個可判定模型嗎？這個這個答案和ZFC無關(guān)。
定理4（[HMSW07]）。完全性定理的無限時間可計算模擬獨立于ZFC。明確地：
?。?）如果V=L，那么每個一致的無限時間可判定理論都有一個無限時間可決定模型，在語言的可計算翻譯中。
（2）與ZFC相對一致的是，在可計算呈現(xiàn)的語言，在中沒有無限時間的可計算或可判定模型該語言的任何翻譯。
（1）的證明使用了表示良好的語言L的概念，對于該語言存在符號hsα|α＜δi的枚舉使得從任何psαq可以一致計算先驗符號hpsβq|β≤αi的代碼?？梢宰C明每一個一致的在一個表現(xiàn)良好的語言中的可判定理論有一個可判定模型，如果V=L，那么每一種可計算語言都有一個表現(xiàn)良好的可計算翻譯。對于（2），一使用理論T擴展了hWO，lect i的原子圖，同時斷言f是select類上的選擇函數(shù)。這是一個可判定的理論，但對于任何可計算的模型A=hA，lect，fi的T，集{f（cu）|u∈WO}為∑1.2.并且具有基數(shù)ω1。眾所周知與ZFC一致，即沒有∑1.2.集合的大小為ω1。
對于L¨owenheim-Skolem定理的無限時間類似物，我們證明了每一個充分呈現(xiàn)的無限時間可判定模型都有一個適當?shù)南蛏习姹揪哂锌膳卸ū硎镜某醯葦U展，對于向下的版本，每個充分表示的不可數(shù)可判定模型都有一個可數(shù)可判初等下部結(jié)構(gòu)。的完全直接推廣有很強的反例。
然而，L¨owenheim-Skolem定理，因為[HMW07]在整個實數(shù)集上提供了一個可計算結(jié)構(gòu)hR，Ui，它沒有合適的可計算初等子結(jié)構(gòu)。
一些最有趣的工作涉及可計算商。結(jié)構(gòu)具有無限時間可計算表示，如果它同構(gòu)于可計算結(jié)構(gòu)，以及具有可計算商表示，如果它同構(gòu)于可計算的商結(jié)構(gòu)通過可計算的等價關(guān)系（同余）。對于N上的結(jié)構(gòu)，在無論是在有限的還是無限的時間背景下，這些概念都是等價的，因為人們可以可計算地找到任何等價類的最小元素。然而對于R上的結(jié)構(gòu)，計算每個等價類的這種可區(qū)分元素并不總是可能的。
問題5.每一個具有無限時間可計算商表示的結(jié)構(gòu)都有一個無限時間可計算表示？
在有限時間理論中，或者對于N上的結(jié)構(gòu)，答案當然是肯定的。但在R上結(jié)構(gòu)的完全無限時間上下文，答案取決于集合論背景
定理6.問題5的答案與ZFC無關(guān)。明確地
?。?）與ZFC相對一致的是，具有無限時間的每個結(jié)構(gòu)都是可計算的商表示具有無限時間的可計算表示。
?。?）與ZFC相對一致的是，有一個結(jié)構(gòu)具有無限時間可計算的商表示，但沒有無限時間可可計算的表示。
讓我們簡要概述一下證據(jù)中出現(xiàn)的一些想法。為了建造結(jié)構(gòu)的無限時間可計算表示，給定可計算商表示，我們想以某種方式從每個等價類中選擇一個代表，在計算有效的方式，并在這些代表的基礎(chǔ)上構(gòu)建一個結(jié)構(gòu)。在下面集合論假設(shè)V=L，我們可以附加到每個等價的L-東成員真正的A級護衛(wèi)，其力量足以表明它是其L東部成員類，并用這些被護送的實數(shù)對構(gòu)建一個可計算的表示。（特別是，新的演示文稿不僅僅是由原始類別的代表構(gòu)建的，因為這些real可能太弱；他們需要護送人員的幫助。）因此，如果V＝L，那么每個具有可計算商表示的結(jié)構(gòu)都具有可計算表示。
在獨立性的另一方面，我們用強迫的方法證明了陳述2。
結(jié)構(gòu)hω1，＜i總是有一個由實數(shù)編碼的良好階建立的可計算商表示，但存在沒有無限時間可計算集的強迫擴展在描述性集合論的基礎(chǔ)上，大小為ω1。因此，在這些擴展中，hω1，＜i具有可計算的商表示，但沒有可計算的表示。
讓我們也簡要討論一些有序計算的替代模型這是無限時間圖靈機所產(chǎn)生的。Peter Koepke[Koe05]介紹了序圖靈機，它通過擴展來推廣無限時間圖靈機膠帶超限序數(shù)長度。相應地調(diào)整了限額規(guī)則，以便這臺機器可以利用這個額外的空間。具體來說，而不是使用特殊的極限狀態(tài)，序數(shù)圖靈機在它們的（有限多個）上有一個固定的階狀態(tài)，并且在任何極限階段，該狀態(tài)被定義為先前狀態(tài)的lim-inf。這個然后將磁頭位置定義為機器運行時磁頭位置的lim-inf之前處于所產(chǎn)生的極限狀態(tài)。為了一致性，Koepke定義磁帶的單元使用先前單元值的lim-inf（而不是使用無限時間圖靈機）。如果頭部在極限位置從單元格向左移動，則它一直出現(xiàn)在第一個單元格的左側(cè)。
因此，這些機器為序數(shù)上的函數(shù)提供了計算模型，以及序數(shù)類的可判定性概念。主要定理是的冪這些機器本質(zhì)上與G模型的可構(gòu)建宇宙的機器相同。
定理7（Koepke）.序數(shù)圖靈機可判定的序數(shù)集，具有有限許多序數(shù)參數(shù)正是G模型的可構(gòu)造宇宙L中的序數(shù)集。
其他幾種序數(shù)計算的無限模型都是基于序數(shù)寄存器的概念，并產(chǎn)生了豐富的理論。參見[Koe05]、[KS06]、[KK06]、[CS09]，[CFK+10]、[HM07]、[HM09]和[HLM07]。
3.無限時間可計算等價關(guān)系理論
最近，我們介紹了Borel等價關(guān)系理論的自然相似性。其中將無限時間可判定關(guān)系與無限時間可計算歸約函數(shù)進行比較。這在一定程度上是由于研究中的偶爾需要Borel等價關(guān)系超越了Borel。事實上，一個更強大的可約性概念可能能夠準確地比較更復雜的關(guān)系。特別是，我們將能夠考慮由于無限的時間復雜性而產(chǎn)生的新關(guān)系類。
我們首先簡要介紹博雷爾等價關(guān)系的研究。這個這門學科的名稱有點用詞不當--實際上是研究的主要對象是標準Borel空間上的任意等價關(guān)系，即配備有完全可分度量空間的Borel結(jié)構(gòu)。在應用程序中，我們想到等價關(guān)系表示來自的某個其他領(lǐng)域的分類問題數(shù)學例如，由于域為N的任何群都是由其乘法函數(shù)決定的，因此研究可數(shù)群的分類問題相當于×N的一個子空間上的同構(gòu)等價關(guān)系。對于更多示例，請參見[ST11]的第1.2節(jié)。
Borel等價關(guān)系理論圍繞以下關(guān)鍵概念展開復雜性如果E，F(xiàn)是標準Borel空間X，Y上的等價關(guān)系，則如下〔FS89〕和〔HK96〕我們說E是Borel可約為F，寫成E≤BF，當存在Borel函數(shù)f:X→ Y使得
(1)x E x′?? f（x）Ff（x′）。
Borel可約性度量等價關(guān)系的復雜性，而不是作為對的集合，而是分類問題。也就是說，如果E是Borel可約為F，那么的分類X到E的元素并不比Y到F的元素的分類難。
現(xiàn)在，Borel等價關(guān)系的經(jīng)典且非常成功的研究包括兩大努力。首先，人們希望繪制出眾多之間的關(guān)系充分理解和自然發(fā)生的等價關(guān)系。其次，給一個現(xiàn)實生活分類問題應該通過將其與制定基準關(guān)系。
關(guān)于歸約函數(shù)（在這種情況下，它們是Borel）的一些可定義條件是必需的事實上，如果沒有任何這樣的限制，還原性總是可以確定的僅憑基數(shù)。然而，也有通過不變量進行自然分類的情況其不能通過Borel歸約函數(shù)來計算。例如，它是?～1.2.，而不是Borel計算可數(shù)扭阿貝爾群的經(jīng)典Ulm不變量。一可能會傾向于形成?的理論～1.2.可還原性，但事實證明這個概念也是慷慨的事實上，正如我們將在下面的定理11中看到的，它可能包含大多數(shù)等價性關(guān)系合并為一個瑣碎的復雜性類。
我們將在這里考慮可在無限時間內(nèi)計算的約化函數(shù)圖靈機（參見[CH11]以獲得更完整的闡述）。因此，對于R上的任何兩個等價關(guān)系E，F(xiàn)，我們說E是無限時間可計算可約為F，寫E≤cF，如果存在無限時間可計算函數(shù)F（自由允許實參數(shù)）滿足等式（1）。類似地，我們說E最終可約為F，寫成E≤eF，如果存在滿足等式（1）的最終可計算函數(shù)f。請注意由于所有不可數(shù)的標準Borel空間都是Borel同構(gòu)的，我們不失去一般性通過限制我們與域R的等價關(guān)系。
當然，通過第1節(jié)中的評論（并再次強調(diào)我們允許參數(shù)），無限時間可計算的約簡包括所有的Borel約簡。
因此，我們的理論將擴展經(jīng)典理論。相反，許多不可約性E6≤BF的經(jīng)典證明依賴于測度、范疇或強迫等方法。因此，他們經(jīng)?！斑^沖”，并表明不存在從E到F的減少，即Lebesgue可測量，Baire可測量，或絕對?～1.2.（下面討論）。
由于無限時間可計算的和最終可計算的函數(shù)享有這三個函數(shù)在這些性質(zhì)中，在每種情況下，都可以得出E?cF，甚至E?eF，以及因此，當我們從≤B層次轉(zhuǎn)移到≤c和≤e層次時，不會有太多的“塌陷”層次結(jié)構(gòu)。
可約性的無限時間概念與絕對?的概念密切相關(guān)～1.2.可還原性，Hjorth等人在文獻中對此進行了討論?；叵胍幌伦蛹疉?R被認為是絕對?～1.2.
如果它由等價∑定義～1.2.和π～1.2.公式其在每個強制延伸中保持相等。函數(shù)f:R→據(jù)說R是絕對?～1.2.
如果它由等價∑定義～1.2.和π～1.2.公式其在每個強制延伸中保持相等。函數(shù)f:R→據(jù)說R是絕對?～1.2.
如果它的圖{（x，n）|f（x）∈Bn}是絕對?～1.2.（此處，Bn貫穿R的基本開子集）。據(jù)我們所知，很少有自然發(fā)生的病例
絕對存在?～1.2.兩個等價關(guān)系而非無窮大之間的歸約時間可計算縮減。并且當存在無限時間可計算縮減時，人們可以通過簡單地“編碼”實現(xiàn)見證約簡函數(shù)的算法來證明這一點。這種計算方法可能更滿足而不是抽象地定義一個歸約函數(shù)并驗證它是?～1.2.總共強制擴展。另一方面，我們沒有任何通用工具來建立超越已建立的無限時間可計算函數(shù)的不可約性上述工具，所有這些工具都通過絕對?建立了不可還原性～1.2.功能已經(jīng)Hjorth和Kanovei建立絕對?的不可還原性的結(jié)果的簡要總結(jié)～1.2.函數(shù)可以在[CH11]的第5節(jié)中找到。一些更深的關(guān)于這個可約性概念的結(jié)果可以在[Hjo00]的第9章中找到。
對于“編碼”一個新的（非Borel）歸約函數(shù)的例子，考慮Eck如果x和y計算（在普通意義上）相同的序數(shù)，則x和y定義的關(guān)系。
我們將其與關(guān)系進行比較=WO，這只是限于井階的代碼集的同構(gòu)關(guān)系。Borel無法比較這兩種關(guān)系削減；然而，它們是密切相關(guān)的，這一點可以通過以下內(nèi)容來明確后果
定理8. Eck和≌WO是無限時間的可計算雙可教育性。
例如，有一個直觀的減少從Eck到≌WO——即將x映射到代碼對于從x可計算（在普通意義上）的序數(shù)的上確界。事實上，這種直覺很容易轉(zhuǎn)化為無限時間圖靈的程序機器簡單地說，該程序只是模擬所有普通的圖靈計算考察每一個列舉的真實性。每當這些real中的一個被視為好的順序，這個代碼被添加到一個列表中。最后，程序計算并輸出一個代碼為其列表中的序數(shù)的上確界。
使用無限時間可計算并最終可計算的另一個明顯好處減少是為了處理在研究無限時間復雜度類。作為一個非常簡單的例子，考慮其中的兩個這類等價關(guān)系中最重要的一類：無窮時度關(guān)系lect∞在第1節(jié)中介紹了，并且由定義的（光面）跳躍等價關(guān)系xJy當且僅當x▽≡∞ y▽.我們有以下關(guān)系（有些瑣碎）兩者之間。
定理9. J最終可通過計算無限時間的函數(shù)降為lect∞一個真實的跳躍。
見證這一過程的程序只是在輸入時模擬所有無限時間的程序x、并且每當其中一個暫停時，將其索引添加到其輸出磁帶上的列表中。由于所有將在階段λ停止的程序，輸出磁帶最終將顯示x▽.
同時，下一個結(jié)果給出了不可約性結(jié)果的采樣，可以是使用上述Hjorth和Kanovei的方法獲得。這里=當然表示R上的相等關(guān)系，E0是由x定義的幾乎相等關(guān)系當且僅當幾乎所有n的x（n）=y（n）。接下來，≌HC表示同構(gòu)關(guān)系限于可遺傳可數(shù)集的代碼集。最后，Eset表示由x-Esety定義的關(guān)系，如果x和y被認為是實數(shù)的可數(shù)序列的碼，枚舉同一集合。
定理10.
?。?） E0不是無限時間可計算地減少到＝。
（2） Eset不是無限時間可計算地減少到E0。
(3)≌HC和Eset不是無限時間可計算地減少到≌兩個。
如果沒有強的集合論假設(shè)，就不能得到這樣的結(jié)果來進行約簡比絕對?更通用的函數(shù)～1.2.功能。例如
無限時間半可計算歸約函數(shù)仍然在?類中～1.2.，但如果我們允許這個類中的約簡函數(shù)，那么中的所有等價關(guān)系定理10可歸結(jié)為等式關(guān)系。
定理11.如果V=L，則R上的每個無限時間可計算等價關(guān)系都是可約的通過一個無限時間半可計算函數(shù)將等式轉(zhuǎn)化為等式關(guān)系。
定理11的證明使用了與定理6的證明相同的思想，并且參數(shù)，歸約函數(shù)不是關(guān)系的選擇器。另一方面在適當?shù)拇_定性假設(shè)下，每個無限時間半可計算函數(shù)是勒貝格可衡量。在這種情況下，無限時間半可計算可約性再次出現(xiàn)類似于更具體的可約性概念。
我們已經(jīng)看到，通過擴展可用的一類約簡函數(shù)，我們有時能夠考慮更廣泛的一類等價關(guān)系。一個校正這方面的例子是以下可數(shù)Borel等價類的推廣關(guān)系這里，Borel等價關(guān)系被認為是可數(shù)的，當每個等價類是可數(shù)的?？蓴?shù)關(guān)系已經(jīng)成為古典理論中研究的最重要的集合之一，因為許多自然關(guān)系都處于這個層次在≤B條件下揭示其結(jié)構(gòu)已取得基本進展。例如，通過Silver的一個經(jīng)典結(jié)果，等式=是≤B-最小可數(shù)Borel等價關(guān)系。此外，根據(jù)Kechris Harrington-Louveau的一個深入結(jié)果，E0是不可約為=的≤Bleast-Borel等價關(guān)系。第三，我們已經(jīng)做到了是一個≤B-最大可數(shù)Borel等價關(guān)系，表示為E∞。剩余的可數(shù)Borel等價關(guān)系位于區(qū)間（E0，E∞）中，并且是Adams-Kechris的一個結(jié)果這意味著在Borel的雙重教育性之前存在著連續(xù)的許多不同的關(guān)系。
最后一個結(jié)果也適用于≤c和≤e可約性的情況，因為Adams和Kechris用來建立不可約性是測度論的。
我們現(xiàn)在定義了一類無限時間可計算關(guān)系，我們提出它是校正可數(shù)Borel等價關(guān)系的類似，并研究剩余結(jié)果的相應推廣。這個想法來自于經(jīng)典的證明關(guān)于E∞的最大性，這取決于可數(shù)的以下特征Borel等價關(guān)系。也就是說，E是一個可數(shù)的Borel等價關(guān)系，如果和只有當它允許Borel枚舉，也就是說，Borel函數(shù)f使得f（x）編碼一個所有x的[x]E的枚舉。（此特性是描述集合論中的Lusin-Novikov定理。）概括起來，我們說等價關(guān)系E是（無限時間）可枚舉的，如果存在無限時間可計算函數(shù)f，使得f（x）對所有x編碼[x]E的枚舉。最終類似地定義了可枚舉等價關(guān)系。這是一個有價值的概括；例如，由x elec hyp y定義的關(guān)系，當x和y在一中是超對數(shù)的另一個是可枚舉的，但不是Borel。
既然我們已經(jīng)說過，E∞的最大性取決于可數(shù)Borel等價關(guān)系，并且由于我們已經(jīng)定義了可數(shù)和最終，以類似的方式，E∞在Borel上下文中的最大性的證明在我們的上下文中產(chǎn)生了相同的可枚舉等價關(guān)系。
定理12. E∞在可枚舉關(guān)系中≤c-最大，在最終可列舉的關(guān)系。
也許令人驚訝的是，我們也可以建立=的極小性。
定理13.=可通過連續(xù)的作用這一結(jié)果是一個直接的結(jié)果（最初是由于韋爾奇）存在一個完美的lect e∞-類集。（這里，lect e∞表示最終的度關(guān)系，它是定義類似于lect∞。）韋爾奇證明的思想是使用強迫理論L∑得到一個互一般Cohen實數(shù)的完美集，然后論證這個集做這項工作。為了看到定理13的成立，觀察每個最終可枚舉的關(guān)系E（作為一組對）包含在關(guān)系lect E∞中。因此存在一個完美的E類的集合，因此存在從=到E的連續(xù)約簡。
最后，我們無法在等式上建立E0的極小性，我們將其作為一個問題。希望類似于證明的方法定理13將給出答案。
問題14。每一個可枚舉等價關(guān)系E都是真的嗎=否則E0可還原為E？
參考文獻
[CFK+10]Merlin Carl、Tim Fischbach、Peter Koepke、Russell Miller、Miriam Nasfi和Gregor Weckbecker。
無限時間寄存器機的基本理論。拱數(shù)學邏輯，49（2）：249–2732010。
[CH11]Sam Coskey和Joel David Hamkins。無限時間可計算等價關(guān)系。圣母院
《形式邏輯雜志》，2011年。出現(xiàn)。
[DHS05]Vinay Deolalikar、Joel David Hamkins和Ralf Dieter Schindler。P≠無窮大的NP?co-NP計時機器?！哆壿嬇c計算雜志》，15（5）：577-5922005年10月。
[FS89]哈維·弗里德曼和李·斯坦利。一類可數(shù)結(jié)構(gòu)的Borel可約性理論。
J.符號邏輯，54（3）：894–9141989。
[Ham02]喬爾·大衛(wèi)·哈姆金斯。無限時間的圖靈機器?！缎闹桥c機器》，12（4）：521–5392002。（專門討論超計算的特刊）。
[Ham04]喬爾·大衛(wèi)·哈姆金斯。超級任務計算。在Boris Piwinger Benedikt L¨owe和Thoralf R¨asch，編輯，《計算的經(jīng)典和新范式及其復雜性層次》，《邏輯趨勢》第23卷，第141-158頁。Kluwer學術(shù)出版社，2004年。2001年9月21日至24日在維也納舉行的“形式科學基礎(chǔ)III”會議的論文。
[Ham05]喬爾·大衛(wèi)·哈姆金斯。具有無限時間圖靈機的無限可計算性。在巴里S。
Cooper和Benedikt L¨owe，編輯，《新計算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。CiE，Springer Verlag。
[Ham07]喬爾·大衛(wèi)·哈姆金斯。無限時間圖靈機綜述。在J′er?ome Durand Lose and Maurice Margenstern，編輯，《機器、計算和普遍性——2007年第五屆MCU國際會議》，《計算機科學講義》第4664卷，法國奧爾良，2007年。
[Hjo00]Greg Hjorth。分類和軌道等效關(guān)系，《數(shù)學調(diào)查》第75卷專著。美國數(shù)學學會，普羅維登斯，RI，2000年。
[HK96]Greg Hjorth和Alexander S.Kechris。Borel等價關(guān)系和可數(shù)模型的分類。Ann.純應用。邏輯學，82（3）：221-2721996。
[HL00]喬爾·大衛(wèi)·哈姆金斯和安迪·劉易斯。無限時間圖靈機。J.符號邏輯，65（2）：567–604， 2000.
[HL02]喬爾·大衛(wèi)·哈姆金斯和安迪·劉易斯。Post的超級任務問題既有積極的解決方案，也有消極的解決方案。數(shù)理邏輯檔案，41（6）：507–5232002。
[HLM07]喬爾·大衛(wèi)·哈姆金斯、大衛(wèi)·萊涅茨基和拉塞爾·米勒?？焖贈Q策的復雜性O(shè)RM可判定集。Barry Cooper、Benedikt L¨owe和Andrea Sorbi，《計算》雜志編輯和現(xiàn)實世界中的邏輯-第三屆歐洲可計算性會議CiE 2007，第4497卷論文集，《計算機科學講義》，意大利錫耶納，2007年。
[HM07]喬爾·大衛(wèi)·哈姆金斯和拉塞爾·米勒。有序寄存器機的Post問題。在巴里Cooper、Benedikt L¨owe和Andrea Sorbi，《真實世界中的計算與邏輯》的編輯-第三屆歐洲可計算性會議CiE 2007，論文集第4497卷，講義計算機科學，意大利錫耶納，2007年。
[HM09]喬爾·大衛(wèi)·哈姆金斯和拉塞爾·米勒。有序寄存器機的Post問題：一個顯式方法《純粹與應用邏輯年鑒》，160（3）：302-3092009。
[HMW07]J.D.Hamkins、R.Miller、D.Seabold和S.Warner。無限時間可計算模型理論。在里面S.B.Cooper、Benedikt L¨owe和Andrea Sorbi，編輯，《新計算范式：變化》《什么是可計算的概念》，第521–557頁。施普林格，2007年。
[HS01]喬爾·大衛(wèi)·哈姆金斯和丹尼爾·西博爾德。只有一個磁帶的無限時間圖靈機?！稊?shù)理邏輯季刊》，47（2）：271–2872001。
[HW03]喬爾·大衛(wèi)·哈姆金斯和菲利普·韋爾奇。Pf≠NPf對于幾乎所有的f。《數(shù)理邏輯季刊》，49(5):536–540， 2003.
[KK06]Peter Koepke和Martin Koervien。順序計算。數(shù)學結(jié)構(gòu)計算。Sci。，16(5):867–884， 2006.
[Koe05]彼得·科普克。序數(shù)上的圖靈計算。符號邏輯公報，11（3）：377–3972005年9月。
[KS06]Peter Koepke和Ryan Siders。在序數(shù)上注冊計算。提交至：數(shù)學邏輯檔案館，2006年。
[KS09]Peter Koepke和Benjamin Seyfferth。序數(shù)機和容許遞歸理論。安。
純應用程序。邏輯，160（3）：310–3182009。
[L¨01]Benedikt L¨owe。修訂順序和計算機n無限長的時間。邏輯計算。，11(1):25–40， 2001.
[LM04]賈科莫·倫齊和埃里?！っ商乩锇骸ｊP(guān)于不動點算術(shù)和無限時間圖靈機。
信息處理信函，91（3）：121-1282004。
[Sch03]拉爾夫·迪特爾·辛德勒。P≠無限時間圖靈機的NP。馬西馬蒂克國王，139(4):335–340， 2003.
[ST11]Scott Schneider和Simon Thomas。可數(shù)的Borel等價關(guān)系。在阿巴拉契亞地區(qū)理論2006–2010、2011。
菲利普·韋爾奇。關(guān)于Deolalikar、Hamkins和Schindler的問題。
菲利普·韋爾奇。弗里德曼的訣竅：無窮時間圖靈度中的極小性論點。在“集合《美國手語邏輯學術(shù)討論會論文集》，258:425-4361999年。
菲利普·韋爾奇。最終無限時間圖靈機度：無限時間可判定實數(shù)。符號邏輯雜志，65（3）：1193–12032000。
菲利普·韋爾奇。無限時間圖靈機計算的長度。倫敦公報數(shù)學學會，32（2）：129-1362000。
菲利普·韋爾奇。1個磁帶圖靈機的超限動作。巴里·S·庫珀和貝內(nèi)迪克特L¨owe，編輯，《新計算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。
施普林格Verlag多倫多大學街222號菲爾德學院m5t3j1&約克大學
安大略省多倫多市基勒街4700號羅斯N520數(shù)學與統(tǒng)計系
紐約城市大學研究生中心，數(shù)學項目，365第五名
紐約大道，郵編：10016&州立大學庫尼島分校，數(shù)學，2800勝
紐約州斯塔滕島林蔭大道10314