斜斑鼓額食蚜蠅

[拼音]：digui kemeijuji

[外文]：recursively enumerable set

又稱部分遞迴集。在能行性理論中，基本概念是遞迴函式，它可刻畫為：任給x，只要它在x處有定義必可在有限步驟內求出其值。因此遞迴全函式（即處處有定義的）必可在有限步驟內求出它的任一值，至於遞迴部分函式（未必處處有定義的）則只要求有定義處可求出其值，但不要求能夠在有限步驟內判定它的定義域的元素，即對任給的x判定x是否屬於函式的定義域。

設有一集合 A與一函式α(x)，如果α(x)=0當且僅當x∈A，則α(x)叫做A的特徵部分函式，如果還有α(x)=1，當且僅當x唘A，則α（x）叫做A的特徵全函式，簡稱特徵函式。如果一集合 A的特徵部分函式（也是特徵函式）是遞迴全函式，則A叫做遞迴集；如果一集A的特徵部分函式是遞迴部分函式，則A叫做部分遞迴集;部分遞迴集又可定義為某個遞迴部分函式的定義域。顯然，A為遞迴集當且僅當:任給x，x屬於A與否，恆可在有限步內判定；A為部分遞迴集當且僅當：任給x，如果x∈A，則必可在有限步內判定，但如果x唘A，可能永遠不知道這件事（除非從別的途徑）。因此有下列結果：

（1）如果A為遞迴集，則A為部分遞迴集；

（2）A為遞迴集當且僅當A的補集亦為遞迴集；

（3）A為遞迴集當且僅當A與它的補集都是部分遞迴集。

最後一點可看出：如果x∈A，因A為部分遞迴集必可在有限步內看出；如果x唘A，因A的補集為部分遞迴集亦可在有限步內看出，從而A必為遞迴集。

遞迴可列舉集是指它是某個一般遞迴函式（即遞迴全函式）ƒ(x)的值域。因為遞迴全函式ƒ(x)的每一個值都可在有限步內算出，可以逐步地計算ƒ（0），ƒ（1），ƒ(2)，…，從而得出遞迴可列舉集的所有元素。這便是遞迴可列舉集名稱的來源。ƒ（x）叫做該集的列舉函式，可能有兩值ƒ(α)與ƒ(b)是相等的，即容許重複列舉。如果ƒ(x)是不減函式或(嚴格)遞增函式，便叫做不減列舉或（嚴格）遞增列舉。

顯然，如果x在一個遞迴可列舉集A內，必可在有限步內判定（只須依次計算ƒ(0)，ƒ(1)，…，便可）；但如果x不在A內，而A又不是嚴格遞增列舉，則很可能人們永遠也不知道這事。根據上述部分遞迴集的特性，可知遞迴可列舉集都是部分遞迴集。反之，如果A為部分遞迴集，命其特徵部分函式為α(x)，當A為空集時，它當然不是任何遞迴全函式的值域，當A非空集時，則在第一階段對α(0)，α(1)各計算1步，第二階段對α(0)，α(1)，α(2)各計算2步，…，第n階段對α(0)，α(1)，α(2)，…，α(n)各計算n步，…，並把首先出現的α(x)=0的根取為ƒ(0)，以後在每一階段之末均把在該階段時所已知的α(x)=0的根取為ƒ在新主目處的值，ƒ必為遞迴全函式，而且A的元素恰巧便是ƒ(0)，ƒ(1)，…的值。可見非空的部分遞迴集必是遞迴可列舉集。一般還把空集也算作遞迴可列舉集，這樣兩種集便一致起來了。

可以證明，A為遞迴可列舉集當且僅當它是某個原始遞迴函式的值域，又當且僅當它是某個初等函式的值域。另一方面，A為遞迴可列舉當且僅當它是某個遞迴部分函式的值域，只須仿照上法，在第n階段計算ƒ(0)，ƒ(1)，…，ƒ(n)各n步，便可把遞迴部分函式的值全部都枚舉出來了。

已有辦法把全體遞迴部分函式全部列舉起來，因此也可以把它們的定義域或值域全部列舉起來。設把第 x個遞迴部分函式的定義域（值域）記為Wx，則Wx便是全體部分遞迴集（遞迴可列舉集）的列舉（注意其中是有重複的）。如命K={x:x∈Wx}（即如果x恰巧在第x個部分遞迴集之內，便把x作為K 的元素），則K是一個遞迴可列舉集但不是遞迴集，從而K 的補集既不是遞迴集又不是遞迴可列舉集。這是人們作出的第一個不是遞迴可列舉集的例子，它也是一個很重要的集，對它已有充分的研究。

此外，如果ƒ 為遞迴部分函式，A為遞迴可列舉，則ƒ-1(A)也是遞迴可列舉集。

著名的希爾伯特第10問題是：有沒有一個能行方法，可決定任給的一個不定方程

是否有整數解?這裡P、Q是兩個具有整係數的多項式。這個問題到1970年已經被否定地解決了，即如果把“能行方法”理解為“用計算遞迴全函式的方法”，那末可以證明：這個能行方法是沒有的。因為任何一個部分遞迴集（遞迴可列舉集）A，都有兩個帶整係數的多項式P、Q，使得

特別是當A即集合K時，也可找出相應的兩個多項式P、Q。既然K不是遞迴的，x屬於K與否是不能遞迴地判定的，那末對於“什麼樣的x能夠使

有解”的問題，也就不能遞迴地判定了。

上面關於集合的討論可以推廣到n元關係去。就n元關係R(x1，x2，…，xn)而言，如果R(x1，x2，…，xn)成立當且僅當

，則ƒ(x1，x2，…，xn)叫做R(x1，x2，…，xn) 的特徵部分函式，如果還要求：R(x1，x2，…，xn)不成立當且僅當

，則ƒ 叫做R的特徵全函式，簡稱特徵函式。如果關係R(x1，x2，…，xn)的特徵部分函式(也是特徵函式)是一個遞迴全函式，則R叫做遞迴關係；如果R(x1，x2，…，xn)的特徵部分函式是遞迴部分函式，則R叫做部分遞迴關係。有了這些定義以後，以上的討論完全可以推廣到遞迴關係與部分遞迴關係方面來。當然，由於函式的值是一個數而不是n元向量，所以“遞迴可列舉關係”不能定義為某個遞迴全函式的值域而只能定義為部分遞迴關係。

但是對遞迴關係而論，有下列的結果，這是討論遞迴時所沒有的。

（1）R(x1，x2，…，xn)為部分遞迴關係當且僅當有一個n+1元遞迴關係或部分遞迴關係 W 使得