埼玉的世界旅行 無限時間圖靈機

-

摘要：我們描述了無限時間圖靈機的基本理論和最近的一些發展，包括無限時間度理論，無限時間複雜性理論，以及無限時間可計算模型理論。我們特彆關注的是無限時間圖靈機上等價關係的層次分析reals，類似於由Borel可約性產生的理論。我們定義了一個概念具有無限的時間可約性，這將Borel理論的大部分提升到∆類∼12在一個令人滿意的方式。

無限時間圖靈機卓有成效地擴展了普通圖靈機的運算到超限有序時間，並通過這樣做提供了關於的可計算性的魯棒理論reals。集合論、描述性集合論和在可計算性理論中，該方法在實數上提供了無限的可計算性和可判定性概念，這些概念以非平凡的方式攀升到描述性集合論層次（∆12同時保持強計算性質。無限的時間圖靈機，我們有無數經典概唸的無限類似物，包括無限時間圖靈度，無限時間複雜性理論，無限時間可計算模型理論，現在也是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，拉爾夫·辛德勒、維奈·德奧拉利卡、拉塞爾·米勒、史蒂夫·華納、賈科莫·倫齊、埃裡希·蒙特裡昂、塞繆爾·科斯基等人。該理論的許多前身包括BlumShubSmale機器（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

input：0

1

1

1

1

scrαtch：1

1

1

1

output：0

1

1

1

1

根據到程式指令。計算被簡單地擴展到限製有序階段定義機器的極限配置。其想法是儘可能多地保留計算到那個階段為止一直在創建的資訊，將其保留在極限配置中，作為早期配置的一種極限。明確地在任何極限有序階段ξ，機器進入我們所說的極限狀態，其中一個區分狀態以及開始狀態和停止狀態；磁頭被重置為第一個單元在左邊；並且磁帶的每個單元都用先前值的limsup更新顯示在該單元格中。已經指定了機器的完整配置在階段ξ，計算現在可以繼續到階段ξ1，以此類推隻有當機器明確進入停止狀態時纔會給出輸出，並且計算當這種情況發生時停止。

由於磁帶自然地容納了無限的二進製字串——而且有很多頭檢查每個單元格的時間——輸入和輸出到的自然上下文機器是Cantor空間2ω，我們用R表示它，並稱之為實數。因此機器提供了實數上可計算性的無限概念。一個程式p計算偏函數ξp。

R→

R、如果程式p在輸入x上，則由ξp（x）y定義產生輸出y，其中計算的輸出是輸出磁帶的內容，當機器進入停止狀態。子集A⊆R是無限時間可判定的，如果A的特征函數是無限時間可以計算的。集合A是無限時間半可判定的，如果常偏函數1↾

A是可計算的。這相當於A是域的無限時間可計算函數（但不一定等同於A是這樣的函數的範圍）。HL00中的初步結果表明，算術集是正是那些在時間上可判定的一致小於ω2和超算術的集合是那些在時間上比某些遞歸序數更短的可判定集合。的力量。

然而，機器在描述集合論中達到了比這高得多的水平等級製度。

例如，每個π11和∑11集合是無限時間可判定的。要看到這一點，隻需表明完整的π11集合WO由編碼ω上的良序關係的實數組成，是無限時間可計算的。這是通過HL00，定理22，我們想在這裡畫一下。給定一個實數x，我們將其視為編碼ω上的關係式，其中n⊳m當且僅當x的h

n，mi位為1。斷言⊳是一個線性階是x中的算術，因此很容易由機器確定。

之後，機器將通過計數來檢查基礎是否良好順序，這取決於計算步驟本身是有序的。

具體來說，機器將當前最小元素的初始猜測放在關係⊳，在遇到它們時用更好的猜測進行更新。在每次修訂時機器會閃爍某個主標誌，這樣在極限階段，機器就可以知道猜測被無限頻繁地更改，表明基礎不健全（機器應該重置在極限級的極限處的主標誌）。否則，真實的電流最小元素已經找到，因此機器可以從的欄位中刪除所有提及它的內容由x編碼的關係。重複此操作，演算法實際上係統地擦除由輸入實數編碼的關係的有根據的初始段，直到要麼什麼都冇有發現了左或無根據的部分，這兩者都可以確定。通過這種方式，WO的成員資格是無限時間可決定的。由此可知，每個π11和∑11集合是無限的。

時間是決定性的，因此機器正確地爬升到∆12。同時，的類無限時間可判定集很容易被觀察到包含在∆中12，實際上是∆類12在無限時間跳躍運算下是封閉的，因此由一個顯著的無限時間圖靈度的一部分。

儘管超限，但計算本質上是可數的，因為共最終性論證證明，每一次計算要麼暫停，要麼重複一些可數序數階段。如果存在計算，則序數α被認為是可計時的恰好停在α上第th步。如果實數x是計算的輸出ξp（0），則實數x是可寫的，而序數是可寫的，如果它是由這樣的實數編碼的。因為隻有可計數的在許多程式中，因此隻有可計數的多個可計時和可寫的序數。可計時和可寫的序數擴展到所有遞歸序數和遠遠超出；它們的上確界是遞歸不可訪問的等等。可寫的序數形成序數的初始段，因為每當一個序數是可寫的，那麼編寫它的演算法就可以很容易地修改為任何較小的序數編寫代碼。但是對於可計時的序數來說，情況並非如此；在可計時的序數中，有無（無參數）無限時間圖靈的越來越複雜的禁區機器可能會停下來。

讓我們快速勾勒出這樣一個論點，即可計時序數中存在這樣的差距，因為這是有序反射中一個有趣的練習，它構成了許多方法的基本方法後來的理論建構。考慮模擬上所有程式的演算法同時輸入0，通過一些保留和管理sufi的記賬方法每個程式都有足夠的獨立空間，模擬ω每個程式的許多計算步驟在每個ω實際計算的許多步驟中。我們的演算法可能會仔細跟蹤哪些程式已經停止，並注意找到冇有程式停止的階段。由於這樣一個階段存在於所有可計時序數的上確界之上，我們最終一定會找到這樣的舞台。由於我們的演算法可以識彆第一個在這樣的階段，我們可以安排它在這一發現後立即停止。因此，我們描述了一種計算過程，它將在比冇有計算停止的階段，因此在可計時的序數中存在間隙，如渴望的對該演算法的仔細分析表明，任何可計時序數之後的第一個間隙都具有階型ω，本質上是因為ω需要許多額外的步驟才能實現已經達到了一個缺口。改進的演算法搜尋更長的間隙，並表明必須是在越來越複雜的可容許極限階段越來越複雜任何可計時或可寫的序數α，都存在大小至少為α的間隙。這些的結構gap表現出與無限時間停頓問題相同的複雜性。

儘管在HL00中已經確定了可計時和可寫的序數同樣的訂單類型，也許該論文中留下的主要問題是這些序數的上確界是相同的。這件事得到了菲利普的肯定Welch在Wel00b。另一種描述結果的方式是，每當程式打開輸入x產生一個停止的計算，然後有另一個計算寫出該計算的證書，整個計算曆史的真實編碼，包括有序關係，其順序類型是計算的長度。這很重要事實遠非顯而易見，它依賴於對最終可寫性的微妙處理，並構成這是該理論許多進一步發展的基礎，包括我們的應用在本文中提及。

上述計數論證的反映方麪包括觀察到可能遇到的實數的任何可判定性質在計算過程中，必須持有一個可寫的實數，因為我們可以開始計算搜尋以找到這樣的見證並在找到時輸出它。這個想法極大地推廣了Philip

Welch的λζ∑定理。具體而言，HL00定義如果存在x出現在從上的某個點輸出磁帶（即使計算冇有停止），並且如果x在計算期間的任何階段出現在任何磁帶上，則它是意外可寫的。通過用實數編碼序數，我們得到了最終可寫和意外可寫的概念序數。如果λ是可計時或可寫序數的上確界，則ζ是最終可寫序數，∑是意外可寫序數的上確界，則HL00建立λ＜ζ＜∑。WelchWel00a斷言的λζ∑定理。

此外，Lλ≺∑1Lζ圖案這個結果準確地表達了演算法可能會下降的意義見證人從意外可寫領域進入最終可寫或可寫領域王國。證明和結果的核心是每一次計算都是重複的∑階段的ζ配置。

經典有限時間可計算性理論的許多基本構造延續到無限的時間語境。例如，我們可以證明smn定理的無限時間相似性、遞歸定理和無窮大的不可判定性時間停滯問題，本質上是經典論點。其他一些經典事實，但是，不要直接一概而論。例如，在無限時間的情況下，這是不正確的。如果函數f的圖是半可判定的，那麼該函數是可計算的。這是以下情況的結果：

定理1（損失旋律定理）。存在一個實c，使得c是無限時間可判定的，但是c是不可寫的。

真正的c，一首丟失的旋律，你不能自己唱，儘管你能認出。當有人唱給你聽時，它是或否，表現出足夠的內部結構，c是可決定，但本身太複雜，無法寫入。也就是說，我們可以識彆給定實數y是否為c，但我們不能從無到有產生c。函數f（x）c

因此，常數值c是不可計算的，因為c不可寫，但圖是可判定的，因為我們可以識彆一對是否具有形式（x，c）。

停頓問題的無限時間模擬分為黑體和黑體版本，hpξp（p）↓並且H＝（p，x）ξp（x）↓，分彆地這都是半可判定和不可判定，但在無限上下文中，它們不是可計算的相等的預言計算的概念上升到無限的上下文中，併產生了一個理論相對可計算性和豐富的學位結構。與經典理論相反。

然而，在N上，在無限時間的上下文中，我們有兩種自然的神諭可供使用在oracle計算中，對應著二階性的理論。第一個人可以使用一個真正的個人作為神諭，完全按照經典的方式，通過連接一個oracle磁帶，上麵寫著real的值。這相當於修複一個補充輸入參數，可以被視為產生了黑體理論無限可計算性，就像在描述性中允許任意實參數一樣黑體∆的集論處理∼11和π∼11（我們將明確采用這樣的黑體透視我們在無限時間下等價關係理論中的應用還原性。）然而，第二，人們自然希望以某種方式使用一組real作為甲骨文，儘管我們一般不能指望在磁帶上寫下這樣的一套（也許它甚至是不可計數的）。相反，oracle磁帶在計算開始時是空的，並且在計算期間，機器可以在該磁帶上自由地寫入；每當演算法調用它時，機器可能會進行成員身份查詢，詢問是否真實當前寫在oracle磁帶上的是否是oracle的成員。因此，該機器能夠知道它能產生的任何真實，無論真實是否在預言集中。

這樣的預言計算產生了相對可計算性的概念p（x）和

因此，一個無窮時可變約簡a≤∞B的概念及其伴隨式無限時度關係A

lect∞B。對於任意一個集合A，我們都有光麵跳躍A▽。而黑體跳躍AH，對應於兩個停頓問題，與A相對應。

黑體跳躍比淺色跳躍高得多，因為HL00確定了A＜∞A▽＜∞啊，還有A▽H≠∞AH和許多其它有趣的相互作用。波斯特問題的無限時間相似性，即是否存在介於0和跳躍0之間的中間半可判定度▽，由HL02於解決一個雙向切入的答案：

定理2。波斯特問題的無限時間模擬既有肯定的解決方案，也有否定的解決方案。

（1）不存在0＜∞z＜∞0的實數z▽

（2）存在實數A的集合，其中0＜∞A＜∞0▽事實上，實A的半可判定集是不可比的。

意外可寫實數的度數是線性排序的，實際上形成了有序類型ζ1的有序層次，這也對應於它們在任何計算中最早出現的順序。在其他作品中，WelchWel99在無限時間的圖靈度。Hamkins和SeaboldHS01分析了一個磁帶與多帶無限時間圖靈機和Benedikt

L¨oweL¨01觀察了無限時間圖靈機與真理修正理論之間的聯絡。

2一些應用和擴展

讓我們簡要介紹一下最近的發展和無限時間的延伸圖靈機，如無限時間複雜性理論的興起和介紹無限時間可計算模型理論。在此之後，在以下部分中，我們將更詳細地介紹無限時間圖靈機在類似於Borel等價關係理論。

Ralf

SchindlerSch03通過求解P與NP問題的無限時間圖靈機模擬。定義多項式類P在無限時間的上下文中，Schindler簡單地觀察到所有實數具有長度ω，且ω的多項式函數受形式為ωn的多項式函數的約束。

因此，他定義了一個集合a⊆R在P中，如果有一個程式P和一個自然數n使得p決定A，並在ωn之前的時間內停止所有輸入集合A在NP中，如果存在是程式p和自然數n使得x∈a當且僅當存在y使得p接受（x，y），並且p在小於ωn的時間內停止所有輸入Schindler證明瞭P≠NP

對於Sch03中的無限時間圖靈機，使用從描述集理論到分析類P和NP的複雜性。這已經在聯閤中推廣對DHS05進行如下運算，其中類coNP由集合的補集組成在NP中。

定理3

P≠關於無限時間圖靈機的NPåcoNP。

此證明出現在DHS05中。由此可見，P≠無限時間圖靈機的NP。（這個結果與有限經典P無關≠NP問題。）

P背後的一些結構性原因≠NPåcoNP是通過放置類來揭示的使用計算的複雜性類Pα和NPα的較大層次中的P和NP大小限製在α以下。DHS05中的結果表明，例如，類NPα對於ω2≤α≤ω1是相同的CK，但無論如何，Pα1（任何可計時極限的Pα2序數α。如下所示，由於Pα在類NPα≠coNPα的同時穩步增加保持不變，對於ω2≤α＜ω1的任何序數α，Pα

因此，P≠NPåcoNP。然而，我們在上確界ω1處獲得相等CK與Pω1CKNPω1CKåcoNPω1CK。

事實上，這是等式∆1的一個例子

1

Σ11∩Π11，從而可以開始看看無限時間圖靈機理論是如何自然地發展成描述集的學說

這種相同的不等式模式Pα（NPα，

當α嚴格位於可計時序數的連續塊內時，對於在可計時序數中開始間隙的任何β，對應的PβNPβ≠coNPβ。在裡麵

此外，對於其他複雜度類P、P和PfBenedikt

L¨owe已經引入了PSPACE的類似物。

在HMSW07中介紹了無限時間可計算模型理論的主題。

可計算模型理論是著眼於結構和理論的可計算性的模型理論。無限時間可計算模型理論利用無限時間圖靈機提供的無限時間可算性概念來執行該程式。經典理論始於幾十年前，其主題包括可計算完備性（每個可判定理論都有可判定模型嗎？）和可計算分類性（每個同構的可計算模型對都有可計算同構嗎？），該領域現在已經成熟為複雜度譜的複雜分析可數模型和理論。

更廣泛背景的動機是，雖然經典的可計算模型理論必然侷限於可數模型和理論，無限可計算性上下文允許建立在現實基礎上的無數模型和理論。可計算模型理論中的許多計算結構都是從建立在N，使用有限時間可計算性，到建立在R上的結構，使用無限時間可計算。不可計數的上下文打開了新的問題，例如無限可計算L¨owenheimSkolem定理，它冇有有限時間的相似性。幾個最自然問題被證明是獨立於ZFC的。

在聯合工作HMW07中，我們定義了一個模型ahA。i是無限時間可計算的，如果A⊆R是可判定的，並且所有函數、關係和常數都是一致的無限時間，可根據其G模型代碼和輸入進行計算。結構A是可判定的，如果可以計算出A¯一給定pΓq和¯一理論T是無限時間可判定的，如果關係T⊢Γ在pΓq中是可計算的。因為我們想處理不可計數的語言，G模型代碼的自然上下文是R而不是N。

當然，最初的問題是完全性定理的無限時間可計算模擬：每個一致的可判定理論都有一個可判定模型嗎？這個這個答案和ZFC無關。

定理4（HMSW07）。完全性定理的無限時間可計算模擬獨立於ZFC。明確地：

（1）如果VL，那麼每個一致的無限時間可判定理論都有一個無限時間可決定模型，在語言的可計算翻譯中。

（2）與ZFC相對一致的是，在可計算呈現的語言，在中冇有無限時間的可計算或可判定模型該語言的任何翻譯。

（1）的證明使用了表示良好的語言L的概念，對於該語言存在符號hsαα＜δi的枚舉使得從任何psαq可以一致計算先驗符號hpsβqβ≤αi的代碼。可以證明每一個一致的在一個表現良好的語言中的可判定理論有一個可判定模型，如果VL，那麼每一種可計算語言都有一個表現良好的可計算翻譯。對於（2），一使用理論T擴展了hWO，lect

i的原子圖，同時斷言f是select類上的選擇函數。這是一個可判定的理論，但對於任何可計算的模型AhA，lect，fi的T，集f（cu）u∈WO為∑12並且具有基數ω1。眾所周知與ZFC一致，即冇有∑12集合的大小為ω1。

對於L¨owenheimSkolem定理的無限時間類似物，我們證明瞭每一個充分呈現的無限時間可判定模型都有一個適當的向上版本具有可判定表示的初等擴展，對於向下的版本，每個充分表示的不可數可判定模型都有一個可數可判初等下部結構。的完全直接推廣有很強的反例。

然而，L¨owenheimSkolem定理，因為HMW07在整個實數集上提供了一個可計算結構hR，Ui，它冇有合適的可計算初等子結構。

一些最有趣的工作涉及可計算商。結構具有無限時間可計算表示，如果它同構於可計算結構，以及具有可計算商表示，如果它同構於可計算的商結構通過可計算的等價關係（同餘）。對於N上的結構，在無論是在有限的還是無限的時間背景下，這些概念都是等價的，因為人們可以可計算地找到任何等價類的最小元素。然而對於R上的結構，計算每個等價類的這種可區分元素並不總是可能的。

問題5每一個具有無限時間可計算商表示的結構都有一個無限時間可計算表示？

在有限時間理論中，或者對於N上的結構，答案當然是肯定的。但在R上結構的完全無限時間上下文，答案取決於集合論背景

定理6問題5的答案與ZFC無關。明確地

（1）與ZFC相對一致的是，具有無限時間的每個結構都是可計算的商表示具有無限時間的可計算表示。

（2）與ZFC相對一致的是，有一個結構具有無限時間可計算的商表示，但冇有無限時間可可計算的表示。

讓我們簡要概述一下證據中出現的一些想法。為了建造結構的無限時間可計算表示，給定可計算商表示，我們想以某種方式從每個等價類中選擇一個代表，在計算有效的方式，並在這些代表的基礎上構建一個結構。在下麵集合論假設VL，我們可以附加到每個等價的L東成員真正的A級護衛，其力量足以表明它是其L東部成員類，並用這些被護送的實數對構建一個可計算的表示。（特彆是，新的簡報不僅僅是由原始類彆的代表構建的，因為這些real可能太弱；他們需要護送人員的幫助。）因此，如果V＝L，那麼每個具有可計算商表示的結構都具有可計算表示。

在獨立性的另一方麵，我們用強迫的方法證明瞭陳述2。

結構hω1，＜i總是有一個由實數編碼的良好階建立的可計算商表示，但存在冇有無限時間可計算集的強迫擴展在描述性集合論的基礎上，大小為ω1。因此，在這些擴展中，hω1，＜i具有可計算的商表示，但冇有可計算的表示。

讓我們也簡要討論一些有序計算的替代模型這是無限時間圖靈機所產生的。Peter

KoepkeKoe05介紹了序圖靈機，它通過擴展來推廣無限時間圖靈機膠帶超限序數長度。相應地調整了限額規則，以便這台機器可以利用這個額外的空間。具體來說，而不是使用特殊的極限狀態，序數圖靈機在它們的（有限多個）上有一個固定的階狀態，並且在任何極限階段，該狀態被定義為先前狀態的liminf。這個然後將磁頭位置定義為機器運行時磁頭位置的liminf之前處於所產生的極限狀態。為了一致性，Koepke定義磁帶的單元使用先前單元值的liminf（而不是使用無限時間圖靈機）。如果頭部在極限位置從單元格向左移動，則它一直出現在第一個單元格的左側。

因此，這些機器為序數上的函數提供了計算模型，以及序數類的可判定性概念。主要定理是的冪這些機器本質上與G模型的可構建宇宙的機器相同。

定理7（Koepke）序數圖靈機可判定的序數集，具有有限許多序數參數正是G模型的可構造宇宙L中的序數集。

其他幾種序數計算的無限模型都是基於序數暫存器的概念，併產生了豐富的理論。參見Koe05、KS06、KK06、CS09，CFK10、HM07、HM09和HLM07。

3無限時間可計算等價關係理論

最近，我們介紹了Borel等價關係理論的自然相似性。其中將無限時間可判定關係與無限時間可計算歸約函數進行比較。這在一定程度上是由於研究中的偶爾需要Borel等價關係超越了Borel。事實上，一個更強大的可約性概念可能能夠準確地比較更複雜的關係。特彆是，我們將能夠考慮由於無限的時間複雜性而產生的新關係類。

我們首先簡要介紹博雷爾等價關係的研究。這個這門學科的名稱有點用詞不當實際上是研究的主要對象是標準Borel空間上的任意等價關係，即配備有完全可分度量空間的Borel結構。在應用程式中，我們想到等價關係表示來自的某個其他領域的分類問題數學例如，由於域為N的任何群都是由其乘法函數決定的，因此研究可數群的分類問題相當於×N的一個子空間上的同構等價關係。對於更多示例，請參見ST11的第12節。

Borel等價關係理論圍繞以下關鍵概念展開複雜性如果E，F是標準Borel空間X，Y上的等價關係，則如下〔FS89〕和〔HK96〕我們說E是Borel可約為F，寫成E≤BF，當存在Borel函數fX→

Y使得

1x

E

x′⇐⇒

f（x）Ff（x′）。

Borel可約性度量等價關係的複雜性，而不是作為對的集合，而是分類問題。也就是說，如果E是Borel可約為F，那麼的分類X到E的元素並不比Y到F的元素的分類難。

現在，Borel等價關係的經典且非常成功的研究包括兩大努力。首先，人們希望繪製出眾多之間的關係充分理解和自然發生的等價關係。其次，給一個現實生活分類問題應該通過將其與製定基準關係。

關於歸約函數（在這種情況下，它們是Borel）的一些可定義條件是必需的事實上，如果冇有任何這樣的限製，還原性總是可以確定的僅憑基數。然而，也有通過不變量進行自然分類的情況其不能通過Borel歸約函數來計算。例如，它是∆∼12，而不是Borel計算可數扭阿貝爾群的經典Ulm不變量。一可能會傾向於形成∆的理論∼12可還原性，但事實證明這個概念也是慷慨的事實上，正如我們將在下麵的定理11中看到的，它可能包含大多數等價性關係合併爲一個瑣碎的複雜性類。

我們將在這裡考慮可在無限時間內計算的約化函數圖靈機（參見CH11以獲得更完整的闡述）。因此，對於R上的任何兩個等價關係E，F，我們說E是無限時間可計算可約為F，寫E≤cF，如果存在無限時間可計算函數F（自由允許實參數）滿足等式（1）。類似地，我們說E最終可約為F，寫成E≤eF，如果存在滿足等式（1）的最終可計算函數f。請注意由於所有不可數的標準Borel空間都是Borel同構的，我們不失去一般性通過限製我們與域R的等價關係。

當然，通過第1節中的評論（並再次強調我們允許參數），無限時間可計算的約簡包括所有的Borel約簡。

因此，我們的理論將擴展經典理論。相反，許多不可約性E6≤BF的經典證明依賴於測度、範疇或強迫等方法。因此，他們經常“過沖”，並表明不存在從E到F的減少，即Lebesgue可測量，Baire可測量，或絕對∆∼12（下麵討論）。

由於無限時間可計算的和最終可計算的函數享有這三個函數在這些性質中，在每種情況下，都可以得出E≰cF，甚至E≰eF，以及因此，當我們從≤B層次轉移到≤c和≤e層次時，不會有太多的“塌陷”層次結構。

可約性的無限時間概念與絕對∆的概念密切相關∼12可還原性，Hjorth等人在文獻中對此進行了討論。回想一下子集A⊆R被認為是絕對∆∼12

如果它由等價∑定義∼12和π∼12公式其在每個強製延伸中保持相等。函數fR→據說R是絕對∆∼12

如果它由等價∑定義∼12和π∼12公式其在每個強製延伸中保持相等。函數fR→據說R是絕對∆∼12

如果它的圖（x，n）f（x）∈Bn是絕對∆∼12（此處，Bn貫穿R的基本開子集）。據我們所知，很少有自然發生的病例

絕對存在∆∼12兩個等價關係而非無窮大之間的歸約時間可計算縮減。並且當存在無限時間可計算縮減時，人們可以通過簡單地“編碼”實現見證約簡函數的演算法來證明這一點。這種計算方法可能更滿足而不是抽象地定義一個歸約函數並驗證它是∆∼12總共強製擴展。另一方麵，我們冇有任何通用工具來建立超越已建立的無限時間可計算函數的不可約性上述工具，所有這些工具都通過絕對∆建立了不可還原性∼12功能已經Hjorth和Kanovei建立絕對∆的不可還原性的結果的簡要總結∼12函數可以在CH11的第5節中找到。一些更深的關於這個可約性概唸的結果可以在Hjo00的第9章中找到。

對於“編碼”一個新的（非Borel）歸約函數的例子，考慮Eck如果x和y計算（在普通意義上）相同的序數，則x和y定義的關係。

我們將其與關係進行比較WO，這隻是限於井階的代碼集的同構關係。Borel無法比較這兩種關係削減；然而，它們是密切相關的，這一點可以通過以下內容來明確後果

定理8

Eck和≌WO是無限時間的可計算雙可教育性。

例如，有一個直觀的減少從Eck到≌WO——即將x對映到代碼對於從x可計算（在普通意義上）的序數的上確界。事實上，這種直覺很容易轉化為無限時間圖靈的程式機器簡單地說，該程式隻是模擬所有普通的圖靈計算考察每一個列舉的真實性。每當這些real中的一個被視為好的順序，這個代碼被新增到一個列表中。最後，程式計算並輸出一個代碼為其列表中的序數的上確界。

使用無限時間可計算並最終可計算的另一個明顯好處減少是為了處理在研究無限時間複雜度類。作為一個非常簡單的例子，考慮其中的兩個這類等價關係中最重要的一類：無窮時度關係lect∞在第1節中介紹了，並且由定義的（光麵）跳躍等價關係xJy當且僅當x▽≡∞

y▽我們有以下關係（有些瑣碎）兩者之間。

定理9

J最終可通過計算無限時間的函數降為lect∞一個真實的跳躍。

見證這一過程的程式隻是在輸入時模擬所有無限時間的程式x、並且每當其中一個暫停時，將其索引新增到其輸出磁帶上的列表中。由於所有將在階段λ停止的程式，輸出磁帶最終將顯示x▽

同時，下一個結果給出了不可約性結果的采樣，可以是使用上述Hjorth和Kanovei的方法獲得。這裡當然表示R上的相等關係，E0是由x定義的幾乎相等關係當且僅當幾乎所有n的x（n）y（n）。接下來，≌HC表示同構關係限於可遺傳可數集的代碼集。最後，Eset表示由xEsety定義的關係，如果x和y被認為是實數的可數序列的碼，枚舉同一集合。

定理10

（1）

E0不是無限時間可計算地減少到＝。

（2）

Eset不是無限時間可計算地減少到E0。

3≌HC和Eset不是無限時間可計算地減少到≌兩個。

如果冇有強的集合論假設，就不能得到這樣的結果來進行約簡比絕對∆更通用的函數∼12功能。例如

無限時間半可計算歸約函數仍然在∆類中∼12，但如果我們允許這個類中的約簡函數，那麼中的所有等價關係定理10可歸結為等式關係。

定理11如果VL，則R上的每個無限時間可計算等價關係都是可約的通過一個無限時間半可計算函數將等式轉化為等式關係。

定理11的證明使用了與定理6的證明相同的思想，並且參數，歸約函數不是關係的選擇器。另一方麵在適當的確定性假設下，每個無限時間半可計算函數是勒貝格可衡量。在這種情況下，無限時間半可計算可約性再次出現類似於更具體的可約性概念。

我們已經看到，通過擴展可用的一類約簡函數，我們有時能夠考慮更廣泛的一類等價關係。一個校正這方麵的例子是以下可數Borel等價類的推廣關係這裡，Borel等價關係被認為是可數的，當每個等價類是可數的。可數關係已經成為古典理論中研究的最重要的集合之一，因為許多自然關係都處於這個層次在≤B條件下揭示其結構已取得基本進展。例如，通過Silver的一個經典結果，等式是≤B最小可數Borel等價關係。此外，根據Kechris

HarringtonLouveau的一個深入結果，E0是不可約為的≤BleastBorel等價關係。第三，我們已經做到了是一個≤B最大可數Borel等價關係，表示為E∞。剩餘的可數Borel等價關係位於區間（E0，E∞）中，並且是AdamsKechris的一個結果這意味著在Borel的雙重教育性之前存在著連續的許多不同的關係。

最後一個結果也適用於≤c和≤e可約性的情況，因為Adams和Kechris用來建立不可約性是測度論的。

我們現在定義了一類無限時間可計算關係，我們提出它是校正可數Borel等價關係的類似，並研究剩餘結果的相應推廣。這個想法來自於經典的證明關於E∞的最大性，這取決於可數的以下特征Borel等價關係。也就是說，E是一個可數的Borel等價關係，如果和隻有當它允許Borel枚舉，也就是說，Borel函數f使得f（x）編碼一個所有x的xE的枚舉。（此特性是描述集合論中的LusinNovikov定理。）概括起來，我們說等價關係E是（無限時間）可枚舉的，如果存在無限時間可計算函數f，使得f（x）對所有x編碼xE的枚舉。最終類似地定義了可枚舉等價關係。這是一個有價值的概括；例如，由x

elec

hyp

y定義的關係，當x和y在一中是超對數的另一個是可枚舉的，但不是Borel。

既然我們已經說過，E∞的最大性取決於可數Borel等價關係，並且由於我們已經定義了可數和最終，以類似的方式，E∞在Borel上下文中的最大性的證明在我們的上下文中產生了相同的可枚舉等價關係。

定理12

E∞在可枚舉關係中≤c最大，在最終可列舉的關係。

也許令人驚訝的是，我們也可以建立的極小性。

定理13可通過連續的作用這一結果是一個直接的結果（最初是由於韋爾奇）存在一個完美的lect

e∞類集。（這裡，lect

e∞表示最終的度關係，它是定義類似於lect∞。）韋爾奇證明的思想是使用強迫理論L∑得到一個互一般Cohen實數的完美集，然後論證這個集做這項工作。為了看到定理13的成立，觀察每個最終可枚舉的關係E（作為一組對）包含在關係lect

E∞中。因此存在一個完美的E類的集合，因此存在從到E的連續約簡。

最後，我們無法在等式上建立E0的極小性，我們將其作為一個問題。希望類似於證明的方法定理13將給出答案。

問題14。每一個可枚舉等價關係E都是真的嗎否則E0可還原為E？

參考文獻

CFK10Merlin

Carl、Tim

Fischbach、Peter

Koepke、Russell

Miller、Miriam

Nasfi和Gregor

Weckbecker。

無限時間暫存器機的基本理論。拱數學邏輯，49（2）：249–2732010。

CH11Sam

Coskey和Joel

David

Hamkins。無限時間可計算等價關係。聖母院

《形式邏輯雜誌》，2011年。出現。

DHS05Vinay

Deolalikar、Joel

David

Hamkins和Ralf

Dieter

Schindler。P≠無窮大的NPåcoNP計時機器。《邏輯與計算雜誌》，15（5）：5775922005年10月。

FS89哈維·弗裡德曼和李·斯坦利。一類可數結構的Borel可約性理論。

J符號邏輯，54（3）：894–9141989。

Ham02喬爾·大衛·哈姆金斯。無限時間的圖靈機器。《心智與機器》，12（4）：521–5392002。（專門討論超計算的特刊）。

Ham04喬爾·大衛·哈姆金斯。超級任務計算。在Boris

Piwinger

Benedikt

L¨owe和Thoralf

R¨asch，編輯，《計算的經典和新範式及其複雜性層次》，《邏輯趨勢》第23卷，第141158頁。Kluwer學術出版社，2004年。2001年9月21日至24日在維也納舉行的“形式科學基礎III”會議的論文。

Ham05喬爾·大衛·哈姆金斯。具有無限時間圖靈機的無限可計算性。在巴裡S。

Cooper和Benedikt

L¨owe，編輯，《新計算範式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。CiE，Springer

Verlag。

Ham07喬爾·大衛·哈姆金斯。無限時間圖靈機綜述。在J´erõome

Durand

Lose

and

Maurice

Margenstern，編輯，《機器、計算和普遍性——2007年第五屆MCU國際會議》，《計算機科學講義》第4664卷，法國奧爾良，2007年。

Hjo00Greg

Hjorth。分類和軌道等效關係，《數學調查》第75卷專著。美國數學學會，普羅維登斯，RI，2000年。

HK96Greg

Hjorth和Alexander

SKechris。Borel等價關係和可數模型的分類。Ann純應用。邏輯學，82（3）：2212721996。

HL00喬爾·大衛·哈姆金斯和安迪·劉易斯。無限時間圖靈機。J符號邏輯，65（2）：567–604，

2000

HL02喬爾·大衛·哈姆金斯和安迪·劉易斯。Post的超級任務問題既有積極的解決方案，也有消極的解決方案。數理邏輯檔案，41（6）：507–5232002。

HLM07喬爾·大衛·哈姆金斯、大衛·萊涅茨基和拉塞爾·米勒。快速決策的複雜性ORM可判定集。Barry

Cooper、Benedikt

L¨owe和Andrea

Sorbi，《計算》雜誌編輯和現實世界中的邏輯第三屆歐洲可計算性會議CiE

2007，第4497卷論文集，《計算機科學講義》，意大利錫耶納，2007年。

HM07喬爾·大衛·哈姆金斯和拉塞爾·米勒。有序暫存器機的Post問題。在巴裡Cooper、Benedikt

L¨owe和Andrea

Sorbi，《真實世界中的計算與邏輯》的編輯第三屆歐洲可計算性會議CiE

2007，論文集第4497卷，講義計算機科學，意大利錫耶納，2007年。

HM09喬爾·大衛·哈姆金斯和拉塞爾·米勒。有序暫存器機的Post問題：一個顯式方法《純粹與應用邏輯年鑒》，160（3）：3023092009。

HMW07JDHamkins、RMiller、DSeabold和SWarner。無限時間可計算模型理論。在裡麵SBCooper、Benedikt

L¨owe和Andrea

Sorbi，編輯，《新計算範式：變化》《什麼是可計算的概念》，第521–557頁。施普林格，2007年。

HS01喬爾·大衛·哈姆金斯和丹尼爾·西博爾德。隻有一個磁帶的無限時間圖靈機。《數理邏輯季刊》，47（2）：271–2872001。

HW03喬爾·大衛·哈姆金斯和菲利普·韋爾奇。Pf≠NPf對於幾乎所有的f。《數理邏輯季刊》，495536–540，

2003

KK06Peter

Koepke和Martin

Koervien。順序計算。數學結構計算。Sci。，165867–884，

2006

Koe05彼得·科普克。序數上的圖靈計算。符號邏輯公報，11（3）：377–3972005年9月。

KS06Peter

Koepke和Ryan

Siders。在序數上註冊計算。提交至：數學邏輯檔案館，2006年。

KS09Peter

Koepke和Benjamin

Seyfferth。序數機和容許遞歸理論。安。

純應用程式。邏輯，160（3）：310–3182009。

L¨01Benedikt

L¨owe。修訂順序和計算機n無限長的時間。邏輯計算。，11125–40，

2001

LM04賈科莫·倫齊和埃裡希·蒙特裡昂。關於不動點算術和無限時間圖靈機。

資訊處理信函，91（3）：1211282004。

Sch03拉爾夫·迪特爾·辛德勒。P≠無限時間圖靈機的NP。馬西馬蒂克國王，1394335–340，

2003

ST11Scott

Schneider和Simon

Thomas。可數的Borel等價關係。在阿巴拉契亞地區理論2006–2010、2011。

菲利普·韋爾奇。關於Deolalikar、Hamkins和Schindler的問題。

菲利普·韋爾奇。弗裡德曼的訣竅：無窮時間圖靈度中的極小性論點。在“集合《美國手語邏輯學術討論會論文集》，2584254361999年。

菲利普·韋爾奇。最終無限時間圖靈機度：無限時間可判定實數。符號邏輯雜誌，65（3）：1193–12032000。

菲利普·韋爾奇。無限時間圖靈機計算的長度。倫敦公報數學學會，32（2）：1291362000。

菲利普·韋爾奇。1個磁帶圖靈機的超限動作。巴裡·S·庫珀和貝內迪克特L¨owe，編輯，《新計算範式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。

施普林格Verlag多倫多大學街222號菲爾德學院m5t3j1amp約克大學

安大略省多倫多市基勒街4700號羅斯N520數學與統計係

紐約城市大學研究生中心，數學項目，365第五名

紐約大道，郵編：10016amp州立大學庫尼島分校，數學，2800勝

紐約州斯塔滕島林蔭大道10314

-

0

0

0

0

0

0

0

0

0

0