波兰一美国数理逻辑学家波斯特(Post， E. L.)提出了如下著名问题:是否存在非递归并且非完备的re集?即是否存在:。度a，使OGTaGTO'?此问题即波斯特问题。1944年，波斯特本人为解决此问题做了许多工作.他计划构造一个re集A，使得A具有某种可定义的(与A非递归相容的)性质，并且这种性质能保证A非T完备.称此计划为波斯特规划.波斯特试图构造一个re集A，使得A是足够“稀疏”的，并且这种“稀疏’，性最终能保证A非T完备.他首先定义了单纯集，并证明了它的存在性，还证明了单纯集不是m完备的.但事实上，单纯集仍可能是tt完备的(从而也是T完备的).于是，他又定义了补集比单纯集更稀疏的超单纯集和超超单纯集，它们不再是tt完备的.他构造了一个超单纯集，但未能证明超超单纯集的存在性，也没有证明超单纯集或超超单纯集不是T完备的.到1954年，德克尔(Dekker，J.)证明了超单纯集不一定不是T完备的.后来，曼希尔(Myhill ， J.)又引进了极大集的概念，这是可能做到的使re集的补集最稀疏的情况.弗里德((Friedberg，R. M.)证明了极大集与超超单纯集的存在性，而耶茨(Ya