请输入您要查询的字词:

 

单词 AlternativeCharacterizationOfPrimitiveRecursiveness
释义

alternative characterization of primitive recursiveness


One useful feature regarding the extended notion of primitive recursiveness described in the parent entry is that it can be used to characterize the original notion of primitive recursiveness. As in the parent entry, we use the notation

𝒮:={f:many m1},𝒱:={f:mnany m,n1}.

In addition, let

𝒱(m,n):={f𝒱f:mn}.

Finally, denote 𝒫 the set of primitive recursive functionsMathworldPlanetmath in the traditional sense (as a subset of 𝒮), and 𝒫 the set of primitive recursive vector-valued functions (a subset of 𝒱). It is clear that 𝒫=𝒫𝒮.

Let 𝒟 be the smallest subset of 𝒱 such that

  1. 1.

    𝒟 contains the zero function z, the successor function s, and the projection functions pmk (see the definition of primitive recursive functions for more detail),

  2. 2.

    𝒟 is closed underPlanetmathPlanetmath functionalPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmathPlanetmath in 𝒱,

  3. 3.

    𝒟 is closed under extensionPlanetmathPlanetmathPlanetmath of coordinates: that is, if f1,,fn𝒱(m,1) are in 𝒟, so is f:=(f1,,fn)𝒱(m,n), given by f(𝒙)=(f1(𝒙),,fn(𝒙)),

  4. 4.

    𝒟 is closed under iterated composition: if f𝒱(m,m) is in 𝒟, and so is g𝒱(m+1,n), given by g(𝒙,n)=fn(𝒙) (where f0 is the identity function).

We now state the characterization.

Proposition 1.

𝒫=𝒟.

Proof.

First, observe that condition 1 is satisfied by both 𝒫 and 𝒟. To see that 𝒟𝒫, note that condition 3 is just the definition in the parent entry, and conditions 2 and 4 are discussed and proved, also in the parent entry. So we have one inclusion. To see the other inclusion 𝒫𝒟, we need to verify the two closure properties:

  1. 1.

    functional composition (in 𝒮): suppose g1,,gm𝒱(k,1) and h𝒱(m,1) are in 𝒟, we want to show that f:=h(g1,,gm)𝒱(k,1) is in 𝒟 too. First, form g=(g1,,gm). Then g𝒟 by extension of coordinates. Then f=hg𝒟 by functional composition (in 𝒱).

  2. 2.

    primitive recursion: suppose g𝒱(k,1) and h𝒱(k+2,1) are both in 𝒟, we want to show that f𝒱(k+1,1) given by f(𝒙,0)=g(𝒙) and f(𝒙,n+1)=h(𝒙,n,f(𝒙,n)) is in 𝒟 too. First, define a function H𝒱(k+2,k+2) by

    H(𝒙,y,z):=(𝒙,s(y),h(𝒙,y,z)).

    Then H is formed by extension of coordinates via the projection functions pik+2 (with i=1,,k) producing the first k coordinates (the coordinates of 𝒙), the function spk+1k+2 producing the k+1st coordinate s(y), and h producing the last coordinate. Since each of the coordinate functions is in D, so is H.

    Next, the function F𝒱(k+3,k+2) given by F(𝒙,y,z,m)=Hm(𝒙,y,z) is in D by iterated composition. We now verify by inductionMathworldPlanetmath on n that

    F(𝒙,0,g(𝒙),n)=(𝒙,n,f(𝒙,n)).
    • F(𝒙,0,g(𝒙),0)=(𝒙,0,g(𝒙), and its third coordinate is f(𝒙,0), as desired.

    • Suppose now that F(𝒙,0,g(𝒙),n)=(𝒙,n,f(𝒙,n)). Then

      F(𝒙,0,g(𝒙),n+1)=H(𝒙,n,f(𝒙,n))
      =(𝒙,s(n),h(𝒙,n,f(𝒙,n)))
      =(𝒙,n+1,f(𝒙,n+1)).

    As a result, f(𝒙,n)=pk+2k+2F(𝒙,0,g(𝒙),n) is in 𝒟 also.

Therefore, 𝒫𝒟, and the proof is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.∎

Remark. According to the characterization above, one sees that primitive recursion is in a sense a special form of iterated composition. The above characterization is helpful in proving, among other things, that every URM-computable function is recursive, and that the Ackermann function is not primitive recursive.

随便看

 

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

 

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