遞歸定理

當事物根據其本身或其類型進行定義時，就會發生遞歸。遞歸用於從語言學到邏輯的各種學科。遞歸的最常見的應用是數學和計算機科學，其中定義的函數在其自己的定義中被應用。雖然這顯然定義了無限數量的實例（函數值），但它通常以這樣的方式完成，即不會發生循環或無限鏈引用。

遞歸是程序在其中一個步驟涉及調用過程本身時所經歷的過程。遞歸的過程被稱為“遞歸過程”。

要理解遞歸，必須認識到一個過程和一個過程的運行之間的區別。程序是基於一組規則的一組步驟。程序的運行涉及實際遵循規則並執行步驟。類比：程序就像書麵食譜；運行程序就像實際準備飯菜一樣。

遞歸與執行某些其他過程的過程規範中的引用相關，但與之不同。例如，食譜可能指的是烹飪蔬菜，這是另一種程序，又需要加熱水等等。然而，一個遞歸過程是（至少）其中一個步驟中的一個步驟需要一個相同過程的新實例，就像一個sourdough配方調用最後一次同一個配方所剩下的一些麵糰。這當然會立即產生無限循環的可能性；如果在某些情況下跳過有問題的步驟，則可以在定義中正確使用遞歸，因為該過程可以完成，就像一個sourdough配方，也告訴你如何獲得一些起始麵糰，以防萬一你從未做過。即使正確定義，遞歸過程對於人類來說也不容易，因為它需要區分新的與過程的（部分執行的）調用；這需要對各種同時進行的程序的實現進行一些管理。因此，遞歸定義在日常情況下非常罕見。一個例子可能是以下程序找到一條通過迷宮的方式。繼續前進，直到到達出口或分支點（死端被認為是具有0個分支的分支點）。如果達到的點是退出，終止。否則反覆嘗試每個分支，遞歸地使用該過程；如果每次試驗都沒有達到死胡同，就返回到導致這個分支點的路徑並報告失敗。這是否實際上定義了終止程序取決於迷宮的性質：它不能允許循環。在任何情況下，執行該過程需要仔細記錄所有當前探索的分支點，並且哪些分支已經被徹底地嘗試。

遞歸定理的原始形式（特稱為第二遞歸定理）為：若為部分遞歸函數，則存在e，使得。

與第二遞歸定理等價的是下列不動點定理：對任何遞歸函數f，存在自然數n(稱為f的不動點)，使。不動點定理有一些推廣的形式：

1.帶參數的遞歸定理。若f為元遞歸函數，則存在一一的n元遞歸函數h，使

2.二重遞歸定理。對遞歸函數f，g，存在自然數a，b，使得：.

對一個遞歸函數f，其不動點不僅存在，而且一定有無窮多個，它們所組成的集合可能是遞歸集，也可能是非遞歸的。值得指出的是，對部分遞歸函數，其不動點定理與第二遞歸定理是等價的，但兩者的證明所需要的基礎並不一樣。前者依賴於S定理和枚舉定理，而後者則僅依賴於S定理。因此，若一個函數類具有S性質但不具有枚舉性(如原始遞歸函數類)，則第二遞歸定理對它也成立，而不動點定理則不然。與第二遞歸定理相對應的是關於部分遞歸泛函的第一不動點定理(美國邏輯學家、數學家克林(Kleene，S.C.)，於1952年證明的)：設F(α，x)為部分遞歸泛函，則存在一個部分遞歸函數α，使得：

1.;

2.;

此時α稱為F的最小不動點。第一和第二不動點定理之名稱純粹是由克林的經典著作《元數學導論》中表述的先後次序而定的，別無他意。此外，在許多文獻中，上述的(第二)不動點定理也稱為遞歸定理而不加區分。