请输入您要查询的字词:

 

单词 BoundedMaximization
释义

bounded maximization


The proof involved in showing that functions obtained via bounded minimizing (http://planetmath.org/BoundedMinimization) primitive recursive functionsMathworldPlanetmath are themselves primitive recursive can be used to show the primitive recursiveness of another family of functions derived from existing primitive recursive functions via a similar technique, called bounded maximization.

Definition. Let f:m+1 be a function. For each y, set

Af(𝒙,y):={zzy and f(𝒙,z)=0}.

Define

fbmax(𝒙,y):={maxAf(𝒙,y)if Af(𝒙,y),0otherwise.

fbmax is called the function obtained from f by bounded maximization.

Proposition 1.

If f:Nm+1N is primitive recursive, so is fbmax.

Proof.

The proof of this is very similar to the proof that fbmin is primitive recursive in the parent entry. The initial set up is the same: define g:=sgnf, where sgn is the sign function. So g is primitive recursive.

Next, define h:m+2 by h(𝒙,y,z)=g(𝒙,y-˙z). So h, and therefore its bounded product:

hp(𝒙,y,z):=i=0zh(𝒙,y,i)

are primitive recursive. hp has the following property: given y,

  • if k is the largest number less than or equal to y such that f(𝒙,k)=0, then

    hp(𝒙,y,z):={1if z<y-k,0otherwise.
  • if no such k exists, then hp(𝒙,y,z)=1, for all (𝒙,y,z)m+2.

As a result, the bounded sum

(hp)s(𝒙,y,z):=i=0zhp(𝒙,y,i),

and in particular, the function g*(𝒙,y):=(hp)s(𝒙,y,y), are primitive recursive. After some simplification, g* becomes

g*(𝒙,y):={y-kif k=maxAf(𝒙,y) exists,s(y)otherwise.

Finally, the function g**(𝒙,y):=y-˙g*(𝒙,y), which is just fbmax(𝒙,y), is primitive recursive too.∎

Example. Using bounded maximization, we can show that q(x,y), the quotient of x÷y, is primitive recursive. When y=0, we set q(x,y)=0

First note that q(x,y) is the largest integer z less than or equal to x such that zyx. Let A(y,x)={zzyx}. Then A(y,x) can be rewritten as

{zzx and sgn(yz-˙x)=0}.

Define f:3 by f(x,y,t)=sgn(yt-˙x). Then

Af(x,y,t)={zzt and sgn(yz-˙x)=0}.

Since f is primitive recursive, so is fbmax(x,y,t). Since A(x,y)=Af(x,y,x), the quotient q(x,y) may be defined as fbmax(x,y,x), and therefore is primitive recursive.

With q(x,y), we may define rem(x,y), the remainder of x÷y, as x-˙yq(x,y), which is easily seen to be primitive recursive.

Remark. Please see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions) for an alternative way of showing that q(x,y) and rem(x,y) are primitive recursive without using bounded maximization. In the alternative method, one shows that rem(x,y) is primitive recursive first. In additionPlanetmathPlanetmath, rem(x,0):=0 in the alternative method, as opposed to x discussed here.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 14:39:07