2。隨機度:基于概率計算的不可預測性。
3。高階遞歸度:通過迭代遞歸算子(如hyperjump、jump
hierarchy的極限)生成的度,包含非遞歸可枚舉(non-r。e。)集合、在高階遞歸論中用于分類高階不可計算性。
4。超限算術度:通過超限歸納生成的度,對應超限圖靈機的停機問題,例如:0<sup>?(
sharp度):與可構成基數相關的度、Δ?1-完全度:解析集的完全度(如所有Δ?1集合的并集)。
超限算術度嚴格包含算術度,與可構成性和內模論密切相關。
5。弱緊致度:與弱緊致基數的力迫性質相關的度,具有某種“通用性”,能編碼大量子結構,在模型論中用于構造特殊模型(如飽和模型)。
6。自指度:通過自指構造(如quine句、哥德爾配數)生成的度,與元數學和自指悖論(如羅素悖論)緊密相關,常用于構造不可判定性的增強版本。
7。高階邏輯度:通過二階邏輯以及更高階邏輯可定義的集合生成的度,在描述集合論中用于分類復雜點集。
……如此類推。
圖靈度是非數值的層次結構,其“分級”通過符號(如0’,
0^(w))和邏輯關系(如歸約、低高度)定義,0度代表可由圖靈機解決的問題(遞歸可枚舉集),非0度代表不可計算問題(如停機問題的0’度)。
部分圖靈機的圖靈度:
1。經典圖靈機:處理的問題屬于可計算度
0,即所有可判定問題。
2。限制性圖靈機(如線性空間限制)可能對應更低子度,但本質上仍屬于
0。
3。通用元胞自動機。
而超圖靈機的圖靈度則取決于具體的模型(超超圖靈機、超超超圖靈機、……等等等等亦在此列),以下是部分超圖靈機的圖靈度:
1。無限時間圖靈機:
允許在無限步后繼續計算,能解決0^(w)度的問題(如康托爾對角化構造的集合)。
可判定算術層次中所有Σ??問題(n為自然數),但無法超越算術層次。
2。量子圖靈機:
若不借助量子并行性(如量子糾纏),其能力仍屬于
0。
若允許量子并行性(如shor算法),仍屬于