指标集

构造非递归集的一种方法。

图灵机是四元组的有穷集，因而可以用能行的方法给图灵机编号。以φ表示第e号图灵机所计算的一元部分递归函数，于是，序列

φ，φ，…，φ，…

中包含了全体一元部分递归函数，而且每个函数出现无穷多次，也就是说每个部分递归函数有无穷多个指标。

以表示全体一元部分递归函数的类，是的任何一个子类：，则形如

B=｛x｜φ∈｝

的自然数集称为指标集。

显然，当B是指标集，x∈B且φ=φ时，y∈B。

指标集中只有、ω两个极端情形是递归的，其余的指标集都不是递归集。因而指标集是定义非递归集的一种最简单、直观的方法，以下是一些常用的指标集的例子：

　　Fin=｛x｜W有穷｝

　　Inf=｛x｜W无穷｝

　　Cof=｛x｜W有穷｝

它们分属于不同的层次，但都不是递归的，Fin是∑完全的，Inf是Ⅱ完全的，Cof是∑完全的，等等。

不过指标集的方法并不能构造出任意的非递归集。

设B是指标集，W=Φ，若x∈B则B是产生集(从而不是递归可枚举集)。这就意味着如果指标集B是递归可枚举集，W=Φ，则xB，从而x∈。当然也是指标集，于是是产生集，从而B是创造集(因而也是m完全集、T完全集)，所以不能用指标集的方法构造各种非m完全的集合(如单纯集)，更不能用它来构造非T完全的递归可枚举集(如解决波斯特问题)。