遞歸定理(recursion theorem)亦稱不動點定理。反映部分遞歸函式類基本性質的重要定理。最初是由美國邏輯學家、數學家克林(Kleene, S. C.)於1938年證明的，克林所給的遞歸定理的原始形式特稱為第二遞歸定理)：若\varphi為部分遞歸函式，則存在e使得\alpha_{e}(x)=\varphi(e,x)。
基本介紹
- 中文名：遞歸定理
- 外文名：recursion theorem
- 領域：數學
- 適用對象：遞歸函式
- 別稱：不動點定理、第二遞歸定理
- 首次證明：美國數學家克林
遞歸,定義,定理表述,
遞歸
當事物根據其本身或其類型進行定義時，就會發生遞歸。 遞歸用於從語言學到邏輯的各種學科。 遞歸的最常見的套用是數學和計算機科學，其中定義的函式在其自己的定義中被套用。 雖然這顯然定義了無限數量的實例（函式值），但它通常以這樣的方式完成，即不會發生循環或無限鏈引用。
定義
遞歸是程式在其中一個步驟涉及調用過程本身時所經歷的過程。遞歸的過程被稱為“遞歸過程”。
要理解遞歸，必須認識到一個過程和一個過程的運行之間的區別。程式是基於一組規則的一組步驟。程式的運行涉及實際遵循規則並執行步驟。類比：程式就像書面食譜;運行程式就像實際準備飯菜一樣。
遞歸與執行某些其他過程的過程規範中的引用相關，但與之不同。例如，食譜可能指的是烹飪蔬菜，這是另一種程式，又需要加熱水等等。然而，一個遞歸過程是（至少）其中一個步驟中的一個步驟需要一個相同過程的新實例，就像一個sourdough配方調用最後一次同一個配方所剩下的一些麵團。這當然會立即產生無限循環的可能性;如果在某些情況下跳過有問題的步驟，則可以在定義中正確使用遞歸，因為該過程可以完成，就像一個sourdough配方，也告訴你如何獲得一些起始麵團，以防萬一你從未做過。即使正確定義，遞歸過程對於人類來說也不容易，因為它需要區分新的與過程的（部分執行的）調用;這需要對各種同時進行的程式的實現進行一些管理。因此，遞歸定義在日常情況下非常罕見。一個例子可能是以下程式找到一條通過迷宮的方式。繼續前進，直到到達出口或分支點（死端被認為是具有0個分支的分支點）。如果達到的點是退出，終止。否則反覆嘗試每個分支，遞歸地使用該過程;如果每次試驗都沒有達到死胡同，就返回到導致這個分支點的路徑並報告失敗。這是否實際上定義了終止程式取決於迷宮的性質：它不能允許循環。在任何情況下，執行該過程需要仔細記錄所有當前探索的分支點，並且哪些分支已經被徹底地嘗試。
定理表述
遞歸定理的原始形式（特稱為第二遞歸定理）為：若
為部分遞歸函式，則存在e，使得
。
與第二遞歸定理等價的是下列不動點定理：對任何遞歸函式f，存在自然數n(稱為f的不動點)，使φn=φf(n)。不動點定理有一些推廣的形式：
- 帶參數的遞歸定理。若f為n+1元遞歸函式，則存在一一的n元遞歸函式h，使
2.二重遞歸定理.對遞歸函式f，g，存在自然數a，b，使得：φa=φf(a，b)& φb=φg(a，b).
對一個遞歸函式f，其不動點不僅存在，而且一定有無窮多個，它們所組成的集合可能是遞歸集，也可能是非遞歸的.值得指出的是，對部分遞歸函式，其不動點定理與第二遞歸定理是等價的，但兩者的證明所需要的基礎並不一樣.前者依賴於Sm定理和枚舉定理，而後者則僅依賴於Sm定理.因此，若一個函式類具有Sm性質但不具有枚舉性(如原始遞歸函式類)，則第二遞歸定理對它也成立，而不動點定理則不然.與第二遞歸定理相對應的是關於部分遞歸泛函的第一不動點定理(美國邏輯學家、數學家克林(Kleene，S.C.)，於1952年證明的)：設F(α，x)為部分遞歸泛函，則存在一個部分遞歸函式α，使得：
1.ᗄx(α(x)=F(α，x));
2.ᗄx(β(x)=F(β，x))→α⊆β;
此時α稱為F的最小不動點。第一和第二不動點定理之名稱純粹是由克林的經典著作《元數學導論》中表述的先後次序而定的，別無他意。此外，在許多文獻中，上述的(第二)不動點定理也稱為遞歸定理而不加區分。
