波斯特问题

递归论问世后的最初十年中，人们所发现的递归可枚举集可以归纳为两类：递归集和T完全(参见图灵归约)的递归可枚举集(如K=｛x｜φ(x)有定义｝)。1944年，波斯特提出了一个著名的问题：是否存在既非递归，又不是T完全的递归可枚举集?换句话说，也就是问在O和O′之间还有没有其他的图灵度(参见图灵度)。这个问题就称为波斯特问题，它几乎完全决定了此后递归论研究的主流方向。

波斯特本人是相信有这样的递归可枚举集的。他认为，由于递归集及其余集都是递归可枚举集，因而可以说递归集A和它的余集将全体自然数N分成了“厚”“薄”相同的两个部分。而那些完全的递归可枚举集(如K)，其余集不再是递归可枚举集，可以说是把N分成了厚薄不同的两个部分。但仍嫌不够“薄”——它本身虽不是递归可枚举集却仍有递归可枚举的无穷子集(参见产生集和创造集)。波斯特希望能构造出一个递归可枚举集A，使更“薄”一些，其中不再有无穷的递归可枚举子集，他想象这样的A可能既不是递归的，也不是T完全的。

按照这个想法，波斯特提出了单纯集的概念，并证明了单纯集存在(参看单纯集)。波斯特当初所构造出的单纯集现在称为“能行的单纯集”，它满足：存在一个递归函数f，使得如果We(We只能有穷)，则｜We｜＜f(e)。

波斯特证明他所构造出的单纯集都不是m完全的(参看m归约)，但未能证明它们不是T完全的。现在已经知道能行的单纯集事实上都是T完全的。

波斯特认为他的失败在于这些单纯集的余集还不够“薄”，于是又提出了超单纯集、超超单纯集等一系列概念，但也未解决问题：他所构造出的集合仍不能证明是非T完全的(事实上都仍是T完全的)。此后，波斯特又提出了“真值表归约”(≤)，及“有界真值表归约(≤)等概念，但也未能解决问题。

现在知道，单纯集、超单纯集之类的概念与T完全性并没有决定性的联系——对每个递归可枚举的度，有属于的单纯集(超单纯集等等)，因而按波斯特的思路是难以解决他所提出的问题的。

波斯特在世的最后十年，将主要的精力投入了波斯特问题的研究。波斯特问题也吸引了其他许多递归论学者。这十年中，人们对递归可枚举集作了大量工作，文献数以千计，发现了递归可枚举集的许多性质，发展了许多研究方法。最后终于在1956年(波斯特逝世两年之后)由弗里德伯格(Friegberg)和穆切尼克(Mucnik)各自独立地解决了波斯特问题，他们分别证明：

定理 存在既非递归又非T完全的递归可枚举集。

他们所用的方法叫优先方法(有穷损害的优先方法)。此后，递归论的研究便进入了一个新的时代，直到如今，对优先方法(无穷损害的优先方法)的研究和应用仍是递归论的主要课题。