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