-
控制函數
鎖定
- 中文名
- 控制函數
- 外文名
- dominating function
- 所屬領域
- 數理邏輯（遞歸論）
- 相關概念
- 遞歸證明、遞歸生成的函數集等
- 定 義
- 遞歸證明中常用的一種函數
控制函數定義
設有一函數集Δ，再設
對t和x 均不減，如果在集Δ中任取一函數
，恆存在有兩數
，使得：
注意：這裏要求
對t和x均不減，如果原耠的
並非不減函數，則可代以
，因此這個要求一般來説極易滿足，既然g為不減函數，顯見
均可換為max(
)。
控制函數相關性質定理
控制函數定理1
如果函數集Δ含有後繼函數
，且對迭置封閉，則Δ的控制函數，作為t、x的二元函數時，不可能屬於Δ。
證明： 如果
屬於Δ，則Sg(t，x)也屬於Δ，且應可找出
，使得
當Δ為遞歸生成的函數集時，其控制函數常可利用下法而得到：
如果Δ的開始函數為
，而對迭置和算子
封閉；又，如果能找出一不減函數g(t，x)滿足下列條件：
(1)對每一
，均有
，使得條件(
)對
成立；
(2)如果對於A及
，均有
，使得(
)對A、對
成立，則也有
使(
)對
成立；
(3)在(2)的假設下，也有
，使(
)對
成立，那麼，
便是該遞歸生成的函數集
的控制函數。
如果生成算子
滿足一定的條件，則控制函數更易找出。
控制函數定義1
如果有一不減函數
，使得：
(
中可合有參數，這時G也含有)，則説
是有界算子，井以
為界，
叫做
的界(對一般的
型算子，也有類似的定義，這裏不予贅述)。
今試討論由有界算子遞歸生成的函數集。
控制函數定義2
如果
永真，則説
被
所控制。
控制函數定理2
設函數集Δ是利用迭置及有界算子從某些開始函數而遞歸生成的，如果Δ的每一個開始函數及它的每一個生成算子的界都被集
中某一個不減函數所控制，而
對迭置封閉，則Δ中每一個函數都被
中某一個不減函數所控制。
[2]
（文中定理及理論的證明均可參考相應的參考書籍）。
控制函數推論
如果有不減函數
，使得對一遞歸生成集的開始函數
及各生成算子的界
説來，恆有
，使得
注意：這推論是以前對各級初等函數集找控制函數的方法的推廣。作為二元函數，控制函數
儘管一般不屬於原函數集，但對於每個固定的t，g(t，x)卻很可能屬於原函數集(一般情形也確如此)，因此引入：
控制函數定義3
如果g(t，x)為函數集Δ的控制函數，且對每個固定的t來説，g(t，x)均屬於Δ，則函數列
稱為Δ的控制骨幹。
控制函數定義4
設函數集Δ的生成算子為
，如果對函數集中每個函數
説來，恆可找出一個數
，使得(
指
的模算子)
控制函數定理3
設
為函數集Δ的副控制骨幹，井且Δ為由開始函數經過迭置及若干算子
而作成的；今以原開始函數、函數max及
為開始函數，經過迭置及加限算子
作成的函數集記為
，則
等於諸
的井集，即
一般説來，加限算子均為初等算子，因此，一般地説，合乎定理3的條件的遞歸生成集均可分解為初等函數集的並集.
