創造集

創造集(creative set)亦稱能行非遞歸集，是余集為產生集的re集。設a為re集，若ā是產生集，則稱a為創造集。例如K={x|φx(x)↓}就是一個創造集。關於創造集的最重要的結果是邁希爾(J.Myhill)證明的：A為創造集，若且唯若A為一一完全的，又若且唯若A為m完全的。若A為創造集，則A既非遞歸集，也非單純集。但是遞歸集、創造集和單純集並沒有窮盡全部的re集，德克爾(J.Dekker)證明了存在一個非遞歸、非單純又非創造集的re集。並稱這種集合為中間集。不僅如此，還證明了任何非遞歸reT度中都有中間集 。

定義

創造集

創造集

創造集

創造集

創造集

創造集

定義1設 是一個遞歸可枚舉集。若存在遞歸函式 使對任何遞歸可枚舉集 ，如果 ， ，就說 是 創造集。

與創造集緊密聯繫的有另一個概念，即生產集。

創造集

創造集

創造集

創造集

創造集

定義2給定集合 ，若存在遞歸函式 ，使當 時， ，就說A是一個 生產集， 叫A的 生產函式。

生產集當然不是遞歸可枚舉集。

定義3利用生產集的概念，可以重新定義創造集如下：

若A滿足下列條件：

(1) A 是遞歸可枚舉集；

創造集

(2) 是生產集，

就說A是創造集。

生產集的特點是從它的任何一個遞歸可枚舉子集出發，可以有效地找出一個更大的遞歸可枚舉子集 。

相關結論

創造集

創造集

創造集

定理1 設 為一元遞歸函式的集合， ，如果 是遞歸枚舉集，那么F是 創造集。

創造集

創造集

創造集

證明：顯然空函式 ，因為不然的話F是生成集，與題設矛盾。因此 ，又由定理2，是生成集，從而F是創造集。證畢。

創造集

運用本定理可以很快地判定 等遞歸枚舉集是創造集。

創造集

創造集

創造集

創造集

定理2 設為一元遞歸函式的集合，，並且至少有一個，那么是生成集。

創造集的一個重要性質如下.

創造集

定理3 如果A是創造集，那么A的補集 含有一個無窮的遞歸枚舉子集。

創造集

定理4 設 ，若A是生產集，則B是生產集。

創造集

推論 設 ，設A是創造集，B是遞歸可枚舉集，則B是創造集。

定理5 若A是單純集，那么A不是創造集 。