控制函数
函数
控制函数(dominating function)是一种特殊函数,是递归证明中常用的一种函数。若对某个a和任何x≥a,均有g(x)≤f(x),则称f为g的控制函数(或称f控制g,或f强于g)。如果Δ为一个函数集合,g为一个二元函数,若对任何f∈Δ,存在t和a,使得当u=max(x1,x2,…,xn)≥a时,均有f(x1,x2,…,xn)
定义
设有一函数集Δ,再设对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为开始函数),其详细内容不做赘述遗,读者可自行探求。
参考资料
最新修订时间:2023-05-23 09:41
目录
概述
定义
相关性质定理
参考资料