遞歸集

遞歸集是遞歸論用語。令A⊆Nn，如果A的特徵函式CA(x1，…，xn)是μ-遞歸函式，則稱A為遞歸集。

遞歸論又稱“遞歸函式論”、“能行性理論”，指主要用數學方法研究“可構造性”、“能行可計算性”或“能行過程”的學科。各種遞歸函式本身的構造也是它研究的重要方面。它既屬於數理邏輯的一個分支學科，不屬於基礎數學的一個分支學科。

基本介紹

• 中文名：遞歸集
• 外文名：Recursive set
• 領域：數學
• 學科：遞歸論
• 函式：特徵函式、遞歸函式
• 定義：具有能行可計算的自然數集

概念

遞歸論用語。令A⊆N，如果A的特徵函式C_A(x₁，…，x_n)是μ-遞歸函式，則稱A為遞歸集。

遞歸集是具有能行可計算的自然數集。設A為自然數集合，若其特徵函式C_A是遞歸函式，則稱A為遞歸集。對遞歸集合A，為了判定某個自然數n是否屬於A，只要計算其特徵函式C_A在n處的值C_A(n)即可。由於C_A的遞歸性，上述過程可能行地完成，從而n是否屬於A是能行可判定的。∅，N都是遞歸集，而且任何有窮集也都是遞歸的。此外，遞歸集類關於集合的交、並、補運算都是封閉的。

遞歸論

又稱“遞歸函式論”、“能行性理論”，指主要用數學方法研究“可構造性”、“能行可計算性”或“能行過程”的學科。各種遞歸函式本身的構造也是它研究的重要方面。它既屬於數理邏輯的一個分支學科，不屬於基礎數學的一個分支學科。

遞歸論的主要內容包括原始遞歸函式，一般遞歸函式，部分遞歸函式，遞歸可枚舉性，判定問題，遞歸不可解理理論，a可遞歸論，碾系理論等。

遞歸論的主要方法是通過對數論函式的研究，揭示能行過程的本質，從而解決許多重要的數學問題。

遞歸論對數論函式的研究從原始遞歸函式開始，進而推廣為一般遞歸函式，並發現一般遞歸函式與能行可計算函式是可以相互定義的，凡是有一個計算過程或一個算法可以將函式值計算出來的函式都是一般遞歸函式。

遞歸論所研究的數論函式都有精確的數學定義，定義是以遞歸的方式進行的。例如，用遞歸定義方式定義“斐博那奇函式”如下：

f(0)=0

f(1)=1

f(n+2)=f(n)+f(n+1)

通過上面的定義，對任意一個自然數n，f(n)恆可使用上述步驟逐步地取得。

在歷史上，對於“能行過程”這一含糊的概念有過許多定義，如一般遞歸式、圖靈機器、正規算法、有限自動機等。通過遞歸論的研究，發展這些定義彼此都是等價的。從這點可以看出，深入研究遞歸論對於弄清“能行過程”是十分關鍵的。

在這一領域裡作出重要貢獻的有希爾伯特、哥德爾、邱吉、圖靈、克林尼、波斯特等人。

遞歸論不僅在數學基礎的研究方面有極其重要的套用，而且在許多新興的科學，尤其在電子計算機科學中愈來愈顯示出它的重要性。

特徵函式

機率論中引進的最重要的變換。機率論中的許多問題，尤其那些連繫著獨立隨機變數求和的問題，可以藉助特徵函式得出簡單的解法。這種函式變換理論最初由法國數學家Fourier引進，在許多數學分支中起了重大作用。特徵函式在解決機率論中著名的“大數定律”及“中心極限定理”時起了舉足輕重的作用。

在機率論中，任何隨機變數的特徵函式(縮寫：ch.f,複數形式：ch.f's)完全定義了它的機率分布。

特徵函式具有以下基本性質：

如果兩個隨機變數具有相同的特徵函式，那么它們具有相同的機率分布； 反之， 如果兩個隨機變數具有相同的機率分布， 它們的特徵函式也相同(顯然)。

獨立隨機變數和的特徵函式等於每個隨機變數特徵函式的乘積。

遞歸函式

函式的概念是一個很一般的概念。在定義函式時，不一定要具體給出通過自變數求函式值的方法。因此，可將函式分成兩類，一類是所謂能行可計算函式，另一類是非能行可計算的函式。這前一種函式無論在理論上或在實際上都是非常重要的，因此人們便試圖給它們以精確的數學刻畫。遞歸函式便是許多這種刻畫中的一種。

我們以下考慮的函式都是從自然數到自然數的函式。

我們先定義幾個初等函式：

(1)零函式 Z(x)=0;

(2)後繼函式 S(x)=x+1;

(3)廣義麼函式 U1n(x₁，…x_n)=x_i;

顯然，上面這些函式都是能行可計算的。

再介紹幾個將函式變換為函式的運算元。

(1)複合運算元 設f是n元函式，g₁…g_n是m元函式，複合運算元將f，g₁…g_n變換成為如下的m元函式h：

h(x₁…xm)=f₁g₁(x₁，…x_m)，…g_n(x₁，…x_m))

(2)遞歸運算元 設f是n元函式 (≥0)，g是n+2元函式，遞歸運算元將f，g變換成滿足下列條件的h+1元函式h：

h(x₁，…，x_n，0)=f(x₁，…x_n)

h(x₁，…x_n，y+1)=g(x₁，…x_n，y，h(x₁，…xn))

(3)μ一運算元，設f是n+1元函式，如果存在y，使f(x1，…x_n，y)=0，我們以μyf(x₁…x_ny)表示這樣的y中的最小者，如果使f(x₁…x_ny)=0的y不存在，我們說μyf(x₁，…x_ny)無定義。μ-運算元將n+1元函式f變換成下面的幾元函式h

h(x₁，…xn)=μyf(x₁…x_ny)

注意，μ運算元可以將一個全函式變換成一個部分函式(即在自然數的某個子集上有定義的函式)。

可以看出，上述所有運算元都是將能行可計算函式變換為能行可計算函式。

所謂遞歸函式類便是包含零函式、廣義麼函式，並在複合運算元、遞歸運算元，μ-運算元下封閒的最小函式類。

容易相信，任何遞歸函式都是能行可計算的。反過來，是否存在直觀上能行可計算的，但不是遞歸的函式呢?人們直到現在還沒有發現這樣的函式。相反，人們證明了，現已遇到的直觀上能行可計算的函式都是遞歸函式。進一步，人們還證明了，遞歸函式類與其他的一些刻畫能行可計算函式的方法產生的函式類是完全一致的，這些事實促使車爾赤(Church)提出了他的著名的論點：

遞歸函式類與直觀能行可計算函式類是重合的。

這個論點已被大多數遞歸論學者所接受。