可计算枚举集和图灵度

可计算枚举集是指其成员可以有效列出的集合，而图灵度则通过相对可计算性对所有集合进行排序，从而组织了不可解问题的领域。

Definition

如果某个算法能精确列出集合的所有成员，则该集合是可计算枚举的；如果一个集合可以利用另一个集合作为预言机来计算，则该集合可图灵归约到另一个集合，而相互归约下的等价类就是图灵度，它们通过相对可计算性进行偏序。

Scope

本主题涵盖可计算枚举集及其基本性质、图灵可归约性及度的偏序关系、停机集作为完全枚举集、波斯特问题及其通过优先级方法解决、以及可计算枚举度的结构理论。

Core questions

• 可计算集和仅仅是可计算枚举集之间有什么区别？
• 图灵可归约性如何比较两个集合的难度？
• 在可计算集和停机问题之间是否存在严格的可计算枚举度？
• 不可解度的全局结构是什么？

Key theories

补集和停机集

一个集合是可计算的当且仅当它及其补集都是可计算枚举的，而停机集是可计算枚举但不可计算的，它是规范的完全枚举集。

波斯特问题和优先级方法

波斯特曾问是否存在严格介于可计算集和停机问题之间的可计算枚举度；弗里德伯格和穆奇尼克通过发明有限损伤优先级方法给出了肯定的答案。

度的结构

图灵度和可计算枚举度形成了丰富、稠密的有序结构，通过高级优先级构造进行研究，揭示了复杂的定义性和嵌入性质。

Clinical relevance

度理论提供了不可解问题的精细分类，表明不可判定性存在无限多个严格递增的层次，而为研究这些问题而开发的优先级方法是一种核心证明技术，影响了逆向数学和算法随机性分析。

History

波斯特于1944年引入了可计算枚举集并提出了他的问题，询问是否存在不完全的不可计算枚举度。弗里德伯格和穆奇尼克在大约1956年独立地用优先级方法解决了这个问题，该方法成为萨克斯、索尔和许多其他人深入研究度的结构的主要工具。

Key figures

• Emil Post
• Richard Friedberg
• Albert Muchnik
• Robert Soare

Seminal works

• soare1987
• post1944
• rogers1987

Frequently asked questions

在可计算性理论中，什么是预言机？

预言机是一个外部来源，可以即时回答关于固定集合的成员资格问题。带有预言机的机器可以在计算过程中使用这些答案，图灵可归约性则询问一个集合是否可以通过一台以另一个集合作为预言机的机器来计算。

为什么波斯特问题很重要？

它询问在可计算枚举集中，在可判定集和停机问题之间是否存在中间层次的不可解性。肯定的答案揭示了度的精细结构，并需要优先级方法这一强大的新技术，该技术塑造了整个学科。