控制函式

控制函式(dominating function)是一種特殊函式，是遞歸證明中常用的一種函式。若對某個a和任何x≥a，均有g(x)≤f(x)，則稱f為g的控制函式(或稱f控制g，或f強於g)。如果Δ為一個函式集合，g為一個二元函式，若對任何f∈Δ，存在t和a，使得當u=max(x₁，x₂，…，x_n)≥a時，均有f(x₁，x₂，…，x_n)<g(t，u)，則稱g為Δ的控制函式。直觀上，g為Δ的控制函式指g“控制”Δ中的每一個函式，因而，Δ的控制函式g必定不屬於Δ，證明g是Δ的控制函式，是證明g不屬於Δ的一種常用方法。

基本介紹

• 中文名：控制函式
• 外文名：dominating function
• 所屬領域：數理邏輯（遞歸論）
• 相關概念：遞歸證明、遞歸生成的函式集等

定義

設有一函式集Δ，再設對t和x 均不減，如果在集Δ中任取一函式，恆存在有兩數，使得：

則稱為Δ的控制函式。

注意：這裡要求對t和x均不減，如果原耠的並非不減函式，則可代以，因此這個要求一般來說極易滿足，既然g為不減函式，顯見均可換為max()。

因此，下面永假定所找出的兩數是相同的，設記其為。

相關性質定理

定理1

如果函式集Δ含有後繼函式，且對迭置封閉，則Δ的控制函式，作為t、x的二元函式時，不可能屬於Δ。

證明： 如果屬於Δ，則Sg(t，x)也屬於Δ，且應可找出，使得

今對t、x均代以，將得

的矛盾結果，定理得證。

當Δ為遞歸生成的函式集時，其控制函式常可利用下法而得到：

如果Δ的開始函式為，而對迭置和運算元封閉；又，如果能找出一不減函式g(t，x)滿足下列條件：

(1)對每一，均有，使得條件()對成立；

(2)如果對於A及，均有，使得()對A、對成立，則也有使()對成立；

(3)在(2)的假設下，也有，使()對成立，那么，便是該遞歸生成的函式集的控制函式。

如果生成運算元滿足一定的條件，則控制函式更易找出。

定義1

如果有一不減函式，使得：(中可合有參數，這時G也含有)，則說是有界運算元，井以為界，叫做的界(對一般的型運算元，也有類似的定義，這裡不予贅述)。

今試討論由有界運算元遞歸生成的函式集。

定義2

如果永真，則說被所控制。

定理2

設函式集Δ是利用迭置及有界運算元從某些開始函式而遞歸生成的，如果Δ的每一個開始函式及它的每一個生成運算元的界都被集中某一個不減函式所控制，而對迭置封閉，則Δ中每一個函式都被中某一個不減函式所控制。

（文中定理及理論的證明均可參考相應的參考書籍）。

推論

如果有不減函式，使得對一遞歸生成集的開始函式及各生成運算元的界說來，恆有，使得

則，即為該遞歸生成集的控制函式。

注意：這推論是以前對各級初等函式集找控制函式的方法的推廣。作為二元函式，控制函式儘管一般不屬於原函式集，但對於每個固定的t，g(t，x)卻很可能屬於原函式集(一般情形也確如此)，因此引入：

定義3

如果g(t，x)為函式集Δ的控制函式，且對每個固定的t來說，g(t，x)均屬於Δ，則函式列稱為Δ的控制骨幹。

定義4

設函式集Δ的生成運算元為，如果對函式集中每個函式說來，恆可找出一個數，使得(指的模運算元)

則g(t，x)稱為函式集Δ的副控制函式。如果對於每個固定的t，g(t，x)恆屬於Δ，則稱為的副控制骨幹。

定理3

設為函式集Δ的副控制骨幹，井且Δ為由開始函式經過迭置及若干運算元而作成的；今以原開始函式、函式max及為開始函式，經過迭置及加限運算元作成的函式集記為，則等於諸的井集，即

一般說來，加限運算元均為初等運算元，因此，一般地說，合乎定理3的條件的遞歸生成集均可分解為初等函式集的並集.

當為原始遞歸式時(這時副控制函式和控制函式同)，可以很筒單地作出控制骨幹，而也可很簡單地取為開始函式(無須兼取及max為開始函式)，其詳細內容不做贅述遺，讀者可自行探求。