趣书网

第84章 前所未有的幸福（第4页）

6.自指度：通过自指构造（如quine句、哥德尔配数）生成的度，与元数学和自指悖论（如罗素悖论）紧密相关，常用于构造不可判定性的增强版本。

7.高阶逻辑度：通过二阶逻辑以及更高阶逻辑可定义的集合生成的度，在描述集合论中用于分类复杂点集。

……如此类推。

图灵度是非数值的层次结构，其“分级”通过符号（如0’, 0^(w)）和逻辑关系（如归约、低\/高度）定义，0度代表可由图灵机解决的问题（递归可枚举集），非0度代表不可计算问题（如停机问题的0’度）。

部分图灵机的图灵度：

1.经典图灵机：处理的问题属于可计算度 0，即所有可判定问题。

2.限制性图灵机（如线性空间限制）可能对应更低子度，但本质上仍属于 0。

3.通用元胞自动机。

而超图灵机的图灵度则取决于具体的模型（超超图灵机、超超超图灵机、……等等等等亦在此列），以下是部分超图灵机的图灵度：

1.无限时间图灵机：

允许在无限步后继续计算，能解决0^(w)度的问题（如康托尔对角化构造的集合）。

可判定算术层次中所有Σ??问题（n为自然数），但无法超越算术层次。

2.量子图灵机：

若不借助量子并行性（如量子纠缠），其能力仍属于 0。

若允许量子并行性（如Shor算法），仍属于 0，因为量子计算不突破可计算性边界（仅优化时间\/空间复杂度）。

3.物理超图灵机（如基于广义相对论或量子引力）：

理论上可能突破图灵极限（如处理非递归物理过程），但无严格数学定义。