Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

Primitive recursive function

From Wikipedia, the free encyclopedia
Function computable with bounded loops

Incomputability theory, aprimitive recursive function is, roughly speaking, a function that can be computed by acomputer program whoseloops are all"for" loops (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Primitive recursive functions form a strictsubset of thosegeneral recursive functions that are alsototal functions.

The importance of primitive recursive functions lies in the fact that mostcomputable functions that are studied innumber theory (and more generally in mathematics) are primitive recursive. For example,addition anddivision, thefactorial andexponential function, and the function which returns thenth prime are all primitive recursive.[1] In fact, for showing that a computable function is primitive recursive, it suffices to show that itstime complexity is bounded above by a primitive recursive function of the input size.[2] It is hence not particularly easy to devise acomputable function that isnot primitive recursive; some examples are shown in section§ Limitations below.

The set of primitive recursive functions is known asPR incomputational complexity theory.

Definition

[edit]

A primitive recursive function takes a fixed number of arguments, each anatural number (nonnegative integer: {0, 1, 2, ...}), and returns a natural number. If it takesn arguments it is calledn-ary.

The basic primitive recursive functions are given by theseaxioms:

  1. Constant functionsCnk{\displaystyle C_{n}^{k}}: For each natural numbern{\displaystyle n} and everyk{\displaystyle k}, thek-ary constant function, defined byCnk(x1,,xk) =def n{\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}, is primitive recursive.
  2. Successor function: The 1-ary successor functionS, which returns the successor of its argument (seePeano postulates), that is,S(x) =def x+1{\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1}, is primitive recursive.
  3. Projection functionsPik{\displaystyle P_{i}^{k}}: For all natural numbersi,k{\displaystyle i,k} such that1ik{\displaystyle 1\leq i\leq k}, thek-ary function defined byPik(x1,,xk) =def xi{\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}} is primitive recursive.

More complex primitive recursive functions can be obtained by applying theoperations given by these axioms:

  1. Composition operator{\displaystyle \circ \,} (also called thesubstitution operator): Given anm-ary functionh(x1,,xm){\displaystyle h(x_{1},\ldots ,x_{m})\,} andmk-ary functionsg1(x1,,xk),,gm(x1,,xk){\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}:h(g1,,gm) =def f,wheref(x1,,xk)=h(g1(x1,,xk),,gm(x1,,xk)).{\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).} Form=1{\displaystyle m=1}, the ordinaryfunction compositionhg1{\displaystyle h\circ g_{1}} is obtained.
  2. Primitive recursion operatorρ{\displaystyle \rho }: Given thek-ary functiong(x1,,xk){\displaystyle g(x_{1},\ldots ,x_{k})\,} and the(k+2){\displaystyle (k+2)}-ary functionh(y,z,x1,,xk){\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}:
    ρ(g,h) =def f,where the (k+1)-ary function f is defined byf(y,x1,,xk)={g(x1,,xk)if y=0h(y,f(y,x1,,xk),x1,,xk)if y=S(y) for a yN{\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where the }}(k+1){\text{-ary function }}f{\text{ is defined by}}\\f(y,x_{1},\dots ,x_{k})&={\begin{cases}g(x_{1},\dots ,x_{k})&{\text{if }}y=0\\h(y',f(y',x_{1},\dots ,x_{k}),x_{1},\dots ,x_{k})&{\text{if }}y=S(y'){\text{ for a }}y'\in \mathbb {N} \\\end{cases}}\end{aligned}}}

    Interpretation:

    The functionf{\displaystyle f} acts as afor-loop from0{\displaystyle 0} up to the value of its first argument. The rest of the arguments forf{\displaystyle f}, denoted here withx1,,xk{\displaystyle x_{1},\ldots ,x_{k}}, are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functionsg{\displaystyle g} andh{\displaystyle h} on the right-hand side of the equations that definef{\displaystyle f} represent the body of the loop, which performs calculations. The functiong{\displaystyle g} is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed byh{\displaystyle h}. The first parameter ofh{\displaystyle h} is fed the "current" value of the for-loop's index. The second parameter ofh{\displaystyle h} is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters forh{\displaystyle h} are those immutable initial conditions for the for-loop mentioned earlier. They may be used byh{\displaystyle h} to perform calculations but they will not themselves be altered byh{\displaystyle h}.

Theprimitive recursive functions are the basic functions and those obtained from the basic functions by applying these operations a finite number of times.

Primitive-recursiveness of vector-valued functions

[edit]

A (vector-valued) function[5]f:NmNn{\displaystyle f:\mathbb {N} ^{m}\to \mathbb {N} ^{n}} is primitive recursive if it can be written as

f(x1,,xm)=(f1(x1,,xm),,fn(x1,,xm)){\displaystyle f(x_{1},\dots ,x_{m})=(f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}))}

where each componentfi:NmN{\displaystyle f_{i}:\mathbb {N} ^{m}\to \mathbb {N} } is a (scalar-valued) primitive recursive function.[6]

Examples

[edit]

Addition

[edit]

A definition of the 2-ary functionAdd{\displaystyle Add}, to compute the sum of its arguments, can be obtained using the primitive recursion operatorρ{\displaystyle \rho }. To this end, the well-known equations

0+y=y andS(x)+y=S(x+y).{\displaystyle {\begin{array}{rcll}0+y&=&y&{\text{ and}}\\S(x)+y&=&S(x+y)&.\\\end{array}}}

are "rephrased in primitive recursive function terminology": In the definition ofρ(g,h){\displaystyle \rho (g,h)}, the first equation suggests to chooseg=P11{\displaystyle g=P_{1}^{1}} to obtainAdd(0,y)=g(y)=y{\displaystyle Add(0,y)=g(y)=y}; the second equation suggests to chooseh=SP23{\displaystyle h=S\circ P_{2}^{3}} to obtainAdd(S(x),y)=h(x,Add(x,y),y)=(SP23)(x,Add(x,y),y)=S(Add(x,y)){\displaystyle Add(S(x),y)=h(x,Add(x,y),y)=(S\circ P_{2}^{3})(x,Add(x,y),y)=S(Add(x,y))}. Therefore, the addition function can be defined asAdd=ρ(P11,SP23){\displaystyle Add=\rho (P_{1}^{1},S\circ P_{2}^{3})}. As a computation example,

Add(1,7)=ρ(P11,SP23)(S(0),7) by Def. Add,S=(SP23)(0,Add(0,7),7) by case ρ(g,h)(S(...),...)=S(Add(0,7)) by Def. ,P23=S(ρ(P11,SP23)(0,7)) by Def. Add=S(P11(7)) by case ρ(g,h)(0,...)=S(7) by Def. P11=8 by Def. S.{\displaystyle {\begin{array}{lll}&Add(1,7)\\=&\rho (P_{1}^{1},S\circ P_{2}^{3})\;(S(0),7)&{\text{ by Def. }}Add,S\\=&(S\circ P_{2}^{3})(0,Add(0,7),7)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&S(Add(0,7))&{\text{ by Def. }}\circ ,P_{2}^{3}\\=&S(\;\rho (P_{1}^{1},S\circ P_{2}^{3})\;(0,7)\;)&{\text{ by Def. }}Add\\=&S(P_{1}^{1}(7))&{\text{ by case }}\rho (g,h)\;(0,...)\\=&S(7)&{\text{ by Def. }}P_{1}^{1}\\=&8&{\text{ by Def. }}S.\\\end{array}}}

Doubling

[edit]

GivenAdd{\displaystyle Add}, the 1-ary functionAdd(P11,P11){\displaystyle Add\circ (P_{1}^{1},P_{1}^{1})} doubles its argument,(Add(P11,P11))(x)=Add(x,x)=x+x{\displaystyle (Add\circ (P_{1}^{1},P_{1}^{1}))(x)=Add(x,x)=x+x}.

Multiplication

[edit]

In a similar way as addition, multiplication can be defined byMul=ρ(C01,Add(P23,P33)){\displaystyle Mul=\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))}. This reproduces the well-known multiplication equations:

Mul(0,y)=ρ(C01,Add(P23,P33))(0,y) by Def. Mul=C01(y) by case ρ(g,h)(0,...)=0 by Def. C01.{\displaystyle {\begin{array}{lll}&Mul(0,y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(0,y)&{\text{ by Def. }}Mul\\=&C_{0}^{1}(y)&{\text{ by case }}\rho (g,h)\;(0,...)\\=&0&{\text{ by Def. }}C_{0}^{1}.\\\end{array}}}

and

Mul(S(x),y)=ρ(C01,Add(P23,P33))(S(x),y) by Def. Mul=(Add(P23,P33))(x,Mul(x,y),y) by case ρ(g,h)(S(...),...)=Add(Mul(x,y),y) by Def. ,P23,P33=Mul(x,y)+y by property of Add.{\displaystyle {\begin{array}{lll}&Mul(S(x),y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(S(x),y)&{\text{ by Def. }}Mul\\=&(Add\circ (P_{2}^{3},P_{3}^{3}))\;(x,Mul(x,y),y)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&Add(Mul(x,y),y)&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\=&Mul(x,y)+y&{\text{ by property of }}Add.\\\end{array}}}

Predecessor

[edit]

The predecessor function acts as the "opposite" of the successor function and is recursively defined by the rulesPred(0)=0{\displaystyle Pred(0)=0} andPred(S(n))=n{\displaystyle Pred(S(n))=n}. A primitive recursive definition isPred=ρ(C00,P12){\displaystyle Pred=\rho (C_{0}^{0},P_{1}^{2})}. As a computation example,

Pred(8)=ρ(C00,P12)(S(7)) by Def. Pred,S=P12(7,Pred(7)) by case ρ(g,h)(S(...),...)=7 by Def. P12.{\displaystyle {\begin{array}{lll}&Pred(8)\\=&\rho (C_{0}^{0},P_{1}^{2})\;(S(7))&{\text{ by Def. }}Pred,S\\=&P_{1}^{2}(7,Pred(7))&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&7&{\text{ by Def. }}P_{1}^{2}.\\\end{array}}}

Truncated subtraction

[edit]

The limited subtraction function (also called "monus", and denoted "˙{\displaystyle \mathbin {\dot {-}} }") is definable from the predecessor function. It satisfies the equations

y˙0=yandy˙S(x)=Pred(y˙x).{\displaystyle {\begin{array}{rcll}y\mathbin {\dot {-}} 0&=&y&{\text{and}}\\y\mathbin {\dot {-}} S(x)&=&Pred(y\mathbin {\dot {-}} x)&.\\\end{array}}}

Since the recursion runs over the second argument, we begin with a primitive recursive definition of the reversed subtraction,RSub(y,x)=x˙y{\displaystyle RSub(y,x)=x\mathbin {\dot {-}} y}. Its recursion then runs over the first argument, so its primitive recursive definition can be obtained, similar to addition, asRSub=ρ(P11,PredP23){\displaystyle RSub=\rho (P_{1}^{1},Pred\circ P_{2}^{3})}. To get rid of the reversed argument order, then defineSub=RSub(P22,P12){\displaystyle Sub=RSub\circ (P_{2}^{2},P_{1}^{2})}. As a computation example,

Sub(8,1)=(RSub(P22,P12))(8,1) by Def. Sub=RSub(1,8) by Def. ,P22,P12=ρ(P11,PredP23)(S(0),8) by Def. RSub,S=(PredP23)(0,RSub(0,8),8) by case ρ(g,h)(S(...),...)=Pred(RSub(0,8)) by Def. ,P23=Pred(ρ(P11,PredP23)(0,8)) by Def. RSub=Pred(P11(8)) by case ρ(g,h)(0,...)=Pred(8) by Def. P11=7 by property of Pred.{\displaystyle {\begin{array}{lll}&Sub(8,1)\\=&(RSub\circ (P_{2}^{2},P_{1}^{2}))\;(8,1)&{\text{ by Def. }}Sub\\=&RSub(1,8)&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\=&\rho (P_{1}^{1},Pred\circ P_{2}^{3})\;(S(0),8)&{\text{ by Def. }}RSub,S\\=&(Pred\circ P_{2}^{3})\;(0,RSub(0,8),8)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&Pred(RSub(0,8))&{\text{ by Def. }}\circ ,P_{2}^{3}\\=&Pred(\;\rho (P_{1}^{1},Pred\circ P_{2}^{3})\;(0,8)\;)&{\text{ by Def. }}RSub\\=&Pred(P_{1}^{1}(8))&{\text{ by case }}\rho (g,h)\;(0,...)\\=&Pred(8)&{\text{ by Def. }}P_{1}^{1}\\=&7&{\text{ by property of }}Pred.\\\end{array}}}

Converting predicates to numeric functions

[edit]

In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers withtruth values (that ist{\displaystyle t} for true andf{\displaystyle f} for false),[citation needed] or that produce truth values as outputs.[8] This can be accomplished by identifying the truth values with numbers in any fixed manner. For example, it is common to identify the truth valuet{\displaystyle t} with the number1{\displaystyle 1} and the truth valuef{\displaystyle f} with the number0{\displaystyle 0}. Once this identification has been made, thecharacteristic function of a setA{\displaystyle A}, which always returns1{\displaystyle 1} or0{\displaystyle 0}, can be viewed as a predicate that tells whether a number is in the setA{\displaystyle A}. Such an identification of predicates with numeric functions will be assumed for the remainder of this article.

Predicate "Is zero"

[edit]

As an example for a primitive recursive predicate, the 1-ary functionIsZero{\displaystyle IsZero} shall be defined such thatIsZero(x)=1{\displaystyle IsZero(x)=1} ifx=0{\displaystyle x=0}, andIsZero(x)=0{\displaystyle IsZero(x)=0}, otherwise. This can be achieved by definingIsZero=ρ(C10,C02){\displaystyle IsZero=\rho (C_{1}^{0},C_{0}^{2})}. Then,IsZero(0)=ρ(C10,C02)(0)=C10()=1{\displaystyle IsZero(0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}()=1} and e.g.IsZero(8)=ρ(C10,C02)(S(7))=C02(7,IsZero(7))=0{\displaystyle IsZero(8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,IsZero(7))=0}.

Predicate "Less or equal"

[edit]

Using the propertyxyx˙y=0{\displaystyle x\leq y\iff x\mathbin {\dot {-}} y=0}, the 2-ary functionLeq{\displaystyle Leq} can be defined byLeq=IsZeroSub{\displaystyle Leq=IsZero\circ Sub}. ThenLeq(x,y)=1{\displaystyle Leq(x,y)=1} ifxy{\displaystyle x\leq y}, andLeq(x,y)=0{\displaystyle Leq(x,y)=0}, otherwise. As a computation example,

Leq(8,3)=IsZero(Sub(8,3)) by Def. Leq=IsZero(5) by property of Sub=0 by property of IsZero{\displaystyle {\begin{array}{lll}&Leq(8,3)\\=&IsZero(Sub(8,3))&{\text{ by Def. }}Leq\\=&IsZero(5)&{\text{ by property of }}Sub\\=&0&{\text{ by property of }}IsZero\\\end{array}}}

Predicate "Greater or equal"

[edit]

Once a definition ofLeq{\displaystyle Leq} is obtained, the converse predicate can be defined asGeq=Leq(P22,P12){\displaystyle Geq=Leq\circ (P_{2}^{2},P_{1}^{2})}. Then,Geq(x,y)=Leq(y,x){\displaystyle Geq(x,y)=Leq(y,x)} is true (more precisely: has value 1) if, and only if,xy{\displaystyle x\geq y}.

If-then-else

[edit]

The 3-ary if-then-else operator known from programming languages can be defined byIf=ρ(P22,P34){\displaystyle {\textit {If}}=\rho (P_{2}^{2},P_{3}^{4})}. Then, for arbitraryx{\displaystyle x},

If(S(x),y,z)=ρ(P22,P34)(S(x),y,z) by Def. If=P34(x,If(x,y,z),y,z) by case ρ(S(...),...)=y by Def. P34{\displaystyle {\begin{array}{lll}&{\textit {If}}(S(x),y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(S(x),y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{3}^{4}(x,{\textit {If}}(x,y,z),y,z)&{\text{ by case }}\rho (S(...),...)\\=&y&{\text{ by Def. }}P_{3}^{4}\\\end{array}}}

and

If(0,y,z)=ρ(P22,P34)(0,y,z) by Def. If=P22(y,z) by case ρ(0,...)=z by Def. P22.{\displaystyle {\begin{array}{lll}&{\textit {If}}(0,y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(0,y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{2}^{2}(y,z)&{\text{ by case }}\rho (0,...)\\=&z&{\text{ by Def. }}P_{2}^{2}.\\\end{array}}}.

That is,If(x,y,z){\displaystyle {\textit {If}}(x,y,z)} returns the then-part,y{\displaystyle y}, if the if-part,x{\displaystyle x}, is true, and the else-part,z{\displaystyle z}, otherwise.

Junctors

[edit]

Based on theIf{\displaystyle {\textit {If}}} function, it is easy to define logical junctors. For example, definingAnd=If(P12,P22,C02){\displaystyle And={\textit {If}}\circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}, one obtainsAnd(x,y)=If(x,y,0){\displaystyle And(x,y)={\textit {If}}(x,y,0)}, that is,And(x,y){\displaystyle And(x,y)} is trueif, and only if, bothx{\displaystyle x} andy{\displaystyle y} are true (logical conjunction ofx{\displaystyle x} andy{\displaystyle y}).

Similarly,Or=If(P12,C12,P22){\displaystyle Or={\textit {If}}\circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})} andNot=If(P11,C01,C11){\displaystyle Not={\textit {If}}\circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})} lead to appropriate definitions ofdisjunction andnegation:Or(x,y)=If(x,1,y){\displaystyle Or(x,y)={\textit {If}}(x,1,y)} andNot(x)=If(x,0,1){\displaystyle Not(x)={\textit {If}}(x,0,1)}.

Equality predicate

[edit]

Using the above functionsLeq{\displaystyle Leq},Geq{\displaystyle Geq} andAnd{\displaystyle And}, the definitionEq=And(Leq,Geq){\displaystyle Eq=And\circ (Leq,Geq)} implements the equality predicate. In fact,Eq(x,y)=And(Leq(x,y),Geq(x,y)){\displaystyle Eq(x,y)=And(Leq(x,y),Geq(x,y))} is true if, and only if,x{\displaystyle x} equalsy{\displaystyle y}.

Similarly, the definitionLt=NotGeq{\displaystyle Lt=Not\circ Geq} implements the predicate "less-than", andGt=NotLeq{\displaystyle Gt=Not\circ Leq} implements "greater-than".

Other operations on natural numbers

[edit]

Exponentiation andprimality testing are primitive recursive. Given primitive recursive functionse{\displaystyle e},f{\displaystyle f},g{\displaystyle g}, andh{\displaystyle h}, a function that returns the value ofg{\displaystyle g} whenef{\displaystyle e\leq f} and the value ofh{\displaystyle h} otherwise is primitive recursive.

Operations on integers and rational numbers

[edit]

By usingGödel numberings, the primitive recursive functions can be extended to operate on other objects such as integers andrational numbers. If integers are encoded by Gödel numbers in a standard way, the arithmetic operations including addition, subtraction, and multiplication are all primitive recursive. Similarly, if the rationals are represented by Gödel numbers then thefield operations are all primitive recursive.

Some common primitive recursive functions

[edit]

The following examples and definitions are fromKleene 1974, pp. 222–231. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, inBoolos, Burgess & Jeffrey 2002, pp. 63–70 they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

In the following the mark " ' ", e.g. a', is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =def a'. The functions 16–20 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed asGödel numbers.

  1. Addition: a+b
  2. Multiplication: a×b
  3. Exponentiation: ab
  4. Factorial a! : 0! = 1, a'! = a!×a'
  5. pred(a): (Predecessor or decrement): If a > 0 then a−1 else 0
  6. Proper subtraction a ∸ b: If a ≥ b then a−b else 0
  7. Minimum(a1, ... an)
  8. Maximum(a1, ... an)
  9. Absolute difference: | a−b | =def (a ∸ b) + (b ∸ a)
  10. ~sg(a): NOT[signum(a)]: If a=0 then 1 else 0
  11. sg(a): signum(a): If a=0 then 0 else 1
  12. a | b: (a divides b): If b=k×a for some k then 0 else 1
  13. Remainder(a, b): the leftover if b does not divide a "evenly". Also called MOD(a, b)
  14. a = b: sg | a − b | (Kleene's convention was to representtrue by 0 andfalse by 1; presently, especially in computers, the most common convention is the reverse, namely to representtrue by 1 andfalse by 0, which amounts to changing sg into ~sg here and in the next item)
  15. a < b: sg( a' ∸ b )
  16. Pr(a): a is a prime number Pr(a) =def a>1 & NOT(Exists c)1<c<a [ c|a ]
  17. pi: the i+1th prime number
  18. (a)i: exponent of pi in a: the unique x such that pix|a & NOT(pix'|a)
  19. lh(a): the "length" or number of non-vanishing exponents in a
  20. lo(a, b): (logarithm of a to base b): If a, b > 1 then the greatest x such that bx | a else 0
In the following, the abbreviationx =def x1, ... xn; subscripts may be applied if the meaning requires.
  • #A: A function φ definable explicitly from functions Ψ and constants q1, ... qn is primitive recursive in Ψ.
  • #B: The finite sum Σy<z ψ(x, y) and product Πy<zψ(x, y) are primitive recursive in ψ.
  • #C: Apredicate P obtained by substituting functions χ1,..., χm for the respective variables of a predicate Q is primitive recursive in χ1,..., χm, Q.
  • #D: The followingpredicates are primitive recursive in Q and R:
  • NOT_Q(x) .
  • Q OR R: Q(x) V R(x),
  • Q AND R: Q(x) & R(x),
  • Q IMPLIES R: Q(x) → R(x)
  • Q is equivalent to R: Q(x) ≡ R(x)
  • #E: The followingpredicates are primitive recursive in thepredicate R:
  • (Ey)y<z R(x, y) where (Ey)y<z denotes "there exists at least one y that is less than z such that"
  • (y)y<z R(x, y) where (y)y<z denotes "for all y less than z it is true that"
  • μyy<z R(x, y). The operator μyy<z R(x, y) is abounded form of the so-called minimization- ormu-operator: Defined as "the least value of y less than z such that R(x, y) is true; or z if there is no such value."
  • #F: Definition by cases: The function defined thus, where Q1, ..., Qm are mutually exclusivepredicates (or "ψ(x) shall have the value given by the first clause that applies), is primitive recursive in φ1, ..., Q1, ... Qm:
φ(x) =
  • φ1(x) if Q1(x) is true,
  • . . . . . . . . . . . . . . . . . . .
  • φm(x) if Qm(x) is true
  • φm+1(x) otherwise
  • #G: If φ satisfies the equation:
φ(y,x) = χ(y, COURSE-φ(y; x2, ... xn ), x2, ... xn then φ is primitive recursive in χ. The value COURSE-φ(y;x2 to n ) of the course-of-values function encodes the sequence of values φ(0,x2 to n), ..., φ(y-1,x2 to n) of the original function.

Relationship to recursive functions

[edit]

The broader class ofpartial recursive functions is defined by introducing anunbounded search operator. The use of this operator may result in apartial function, that is, a relation withat most one value for each argument, but does not necessarily haveany value for any argument (seedomain). An equivalent definition states that a partial recursive function is one that can be computed by aTuring machine. A total recursive function is a partial recursive function that is defined for every input.

Every primitive recursive function is total recursive, but not all total recursive functions are primitive recursive. TheAckermann functionA(m,n) is a well-known example of a total recursive function (in fact, provable total), that is not primitive recursive. There is a characterization of the primitive recursive functions as a subset of the total recursive functions using the Ackermann function. This characterization states that a function is primitive recursiveif and only if there is a natural numberm such that the function can be computed by a Turingmachine that always halts within A(m,n) or fewer steps, wheren is the sum of the arguments of the primitive recursive function.[9]

An important property of the primitive recursive functions is that they are arecursively enumerable subset of the set of alltotal recursive functions (which is not itself recursively enumerable). This means that there is a single recursive functionf(m,n) that enumerates the primitive recursive functions, namely:

  • For every unary primitive recursive functiong, there is anm such thatg(n) =f(m,n) for alln, and
  • For everym, the functionh(n) =f(m,n) is primitive recursive.
  • Primitive recursive functions with two or more arguments can be encoded as unary primitive recursive functions by using a primitive recursivepairing function with two primitive recursive inverses.

f can be explicitly constructed by iteratively repeating all possible ways of creating primitive recursive functions. Thus, it is provably total. One can use adiagonalization argument to show thatf is not recursive primitive in itself: had it been such, so would beh(n) =f(n,n)+1. But if this equals some primitive recursive function, there is anm such thath(n) =f(m,n) for alln, and thenh(m) =f(m,m), leading to contradiction.

However, the set of primitive recursive functions is not thelargest recursively enumerable subset of the set of all total recursive functions. For example, the set of provably total functions (in Peano arithmetic) is also recursively enumerable, as one can enumerate all the proofs of the theory. While all primitive recursive functions are provably total, the converse is not true.

Limitations

[edit]

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However, the set of primitive recursive functions does not include every possible total computable function—this can be seen with a variant ofCantor's diagonal argument. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

The primitive recursive functions of one argument (i.e., unary functions) can becomputably enumerated. This enumeration uses the definitions of the primitive recursive functions (which are essentially just expressions with the composition and primitive recursion operations as operators and the basic primitive recursive functions as atoms), and can be assumed to contain every definition once, even though a samefunction will occur many times on the list (since many definitions define the same function; indeed simply composing by theidentity function generates infinitely many definitions of any one primitive recursive function). This means that then{\displaystyle n}-th definition of a primitive recursive function in this enumeration can be effectively determined fromn{\displaystyle n}. Indeed if one uses someGödel numbering to encode definitions as numbers, then thisn{\displaystyle n}-th definition in the list is computed by a primitive recursive function ofn{\displaystyle n}. Letfn{\displaystyle f_{n}} denote the unary primitive recursive function given by this definition.

Now define the "evaluator function"ev{\displaystyle ev} with two arguments, byev(i,j)=fi(j){\displaystyle ev(i,j)=f_{i}(j)}. Clearlyev{\displaystyle ev} is total and computable, since one can effectively determine the definition offi{\displaystyle f_{i}}, and being a primitive recursive functionfi{\displaystyle f_{i}} is itself total and computable, sofi(j){\displaystyle f_{i}(j)} is always defined and effectively computable. However a diagonal argument will show that the functionev{\displaystyle ev} of two arguments is not primitive recursive.

Supposeev{\displaystyle ev} were primitive recursive, then the unary functiong{\displaystyle g} defined byg(i)=S(ev(i,i)){\displaystyle g(i)=S(ev(i,i))} would also be primitive recursive, as it is defined by composition from the successor function andev{\displaystyle ev}. But theng{\displaystyle g} occurs in the enumeration, so there is some numbern{\displaystyle n} such thatg=fn{\displaystyle g=f_{n}}. But nowg(n)=S(ev(n,n))=S(fn(n))=S(g(n)){\displaystyle g(n)=S(ev(n,n))=S(f_{n}(n))=S(g(n))} gives a contradiction.

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the articleMachine that always halts. Note however that thepartial computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.

Other examples of total recursive but not primitive recursive functions are known:

Variants

[edit]

Constant functions

[edit]

Instead ofCnk{\displaystyle C_{n}^{k}},alternative definitions use just one 0-aryzero functionC00{\displaystyle C_{0}^{0}} as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator.[citation needed]

Iterative functions

[edit]

Robinson[10] considered various restrictions of the recursion rule. One is the so-callediteration rule where the functionh does not have access to the parametersxi (in this case, we may assume without loss of generality that the functiong is just the identity, as the general case can be obtained by substitution):

f(0,x)=x,f(S(y),x)=h(y,f(y,x)).{\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(y,f(y,x)).\end{aligned}}}

He proved that the class of all primitive recursive functions can still be obtained in this way.

Pure recursion

[edit]

Another restriction considered by Robinson[10] ispure recursion, whereh does not have access to the induction variabley:

f(0,x1,,xk)=g(x1,,xk),f(S(y),x1,,xk)=h(f(y,x1,,xk),x1,,xk).{\displaystyle {\begin{aligned}f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k}),\\f(S(y),x_{1},\ldots ,x_{k})&=h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}

Gladstone[11] proved that this rule is enough to generate all primitive recursive functions. Gladstone[12] improved this so that even the combination of these two restrictions, i.e., thepure iteration rule below, is enough:

f(0,x)=x,f(S(y),x)=h(f(y,x)).{\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(f(y,x)).\end{aligned}}}

Further improvements are possible: Severin[13] prove that even the pure iteration rulewithout parameters, namely

f(0)=0,f(S(y))=h(f(y)),{\displaystyle {\begin{aligned}f(0)&=0,\\f(S(y))&=h(f(y)),\end{aligned}}}

suffices to generate allunary primitive recursive functions if we extend the set of initial functions with truncated subtractionx ∸ y. We getall primitive recursive functions if we additionally include + as an initial function.

Additional primitive recursive forms

[edit]

Some additional forms of recursion also define functions that are in factprimitive recursive. Definitions in these forms may be easier to find ormore natural for reading or writing.Course-of-values recursion defines primitive recursive functions. Some forms ofmutual recursion also define primitive recursive functions.

The functions that can be programmed in theLOOP programming language are exactly the primitive recursive functions. This gives a different characterization of the power of these functions. The main limitation of the LOOP language, compared to aTuring-complete language, is that in the LOOP language the number of times that each loop will run is specified before the loop begins to run.

Computer language definition

[edit]

An example of a primitive recursive programming language is one that contains basic arithmetic operators (e.g. + and −, or ADD and SUBTRACT), conditionals and comparison (IF-THEN, EQUALS, LESS-THAN), and bounded loops, such as the basicfor loop, where there is a known or calculable upper bound to all loops (FOR i FROM 1 TO n, with neither i nor n modifiable by the loop body). No control structures of greater generality, such aswhile loops or IF-THEN plusGOTO, are admitted in a primitive recursive language.

TheLOOP language, introduced in a 1967 paper byAlbert R. Meyer andDennis M. Ritchie,[14] is such a language. Its computing power coincides with the primitive recursive functions. A variant of the LOOP language isDouglas Hofstadter'sBlooP inGödel, Escher, Bach. Adding unbounded loops (WHILE, GOTO) makes the languagegeneral recursive andTuring-complete, as are all real-world computer programming languages.

The definition of primitive recursive functions implies that their computation halts on every input (after a finite number of steps). On the other hand, thehalting problem isundecidable for general recursive functions.

Finitism and consistency results

[edit]

The primitive recursive functions are closely related to mathematicalfinitism, and are used in several contexts in mathematical logic where a particularly constructive system is desired.Primitive recursive arithmetic (PRA), a formal axiom system for the natural numbers and the primitive recursive functions on them, is often used for this purpose.

PRA is much weaker thanPeano arithmetic, which is not a finitistic system. Nevertheless, many results innumber theory and inproof theory can be proved in PRA. For example,Gödel's incompleteness theorem can be formalized into PRA, giving the following theorem:

IfT is a theory of arithmetic satisfying certain hypotheses, with Gödel sentenceGT, then PRA proves the implication Con(T)→GT.

Similarly, many of the syntactic results in proof theory can be proved in PRA, which implies that there are primitive recursive functions that carry out the corresponding syntactic transformations of proofs.

In proof theory andset theory, there is an interest in finitisticconsistency proofs, that is, consistency proofs that themselves are finitistically acceptable. Such a proof establishes that the consistency of a theoryT implies the consistency of a theoryS by producing a primitive recursive function that can transform any proof of an inconsistency fromS into a proof of an inconsistency fromT. One sufficient condition for a consistency proof to be finitistic is the ability to formalize it in PRA. For example, many consistency results in set theory that are obtained byforcing can be recast as syntactic proofs that can be formalized in PRA.

History

[edit]

Recursive definitions had been used more or less formally in mathematics before, but the construction of primitive recursion is traced back toRichard Dedekind's theorem 126 of hisWas sind und was sollen die Zahlen? (1888). This work was the first to give a proof that a certain recursive construction defines a unique function.[15][16][17]

Primitive recursive arithmetic was first proposed byThoralf Skolem[18] in 1923.

The current terminology was coined byRózsa Péter (1934) afterAckermann had proved in 1928 that the function which today is named after him was not primitive recursive, an event which prompted the need to rename what until then were simply called recursive functions.[16][17]

See also

[edit]

Notes

[edit]
  1. ^Brainerd & Landweber 1974.
  2. ^Hartmanis 1989.
  3. ^Fachini & Maggiolo-Schettini 1979.
  4. ^Fachini & Maggiolo-Schettini 1982.
  5. ^also known as"sequence function"[3][4]
  6. ^PlanetMath
  7. ^E.g.:Henk Barendregt (1990), "Functional Programming and Lambda Calculus", inJan van Leeuwen (ed.),Formal Models and Semantics, Handbook of Theoretical Computer Science, vol. B, Elsevier, pp. 321–364,ISBN 0-444-88074-7 Here: 2.2.6initial functions, Def.2.2.7primitive recursion, p.331-332.
  8. ^Kleene 1974, pp. 226–227.
  9. ^This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, seeLinz, Peter (2011),An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, p. 332,ISBN 9781449615529. For the latter, seeMoore, Cristopher; Mertens, Stephan (2011),The Nature of Computation, Oxford University Press, p. 287,ISBN 9780191620805
  10. ^abRobinson 1947.
  11. ^Gladstone 1967.
  12. ^Gladstone 1971.
  13. ^Severin 2008.
  14. ^Meyer, Albert R.;Ritchie, Dennis M. (1967), "The complexity of loop programs",ACM '67: Proceedings of the 1967 22nd national conference, pp. 465–469,doi:10.1145/800196.806014
  15. ^Peter Smith (2013),An Introduction to Gödel's Theorems (2nd ed.), Cambridge University Press, pp. 98–99,ISBN 978-1-107-02284-3
  16. ^abGeorge Tourlakis (2003),Lectures in Logic and Set Theory: Volume 1, Mathematical Logic, Cambridge University Press, p. 129,ISBN 978-1-139-43942-8
  17. ^abRod Downey, ed. (2014),Turing's Legacy: Developments from Turing's Ideas in Logic, Cambridge University Press, p. 474,ISBN 978-1-107-04348-0
  18. ^Thoralf Skolem (1923) "The foundations of elementary arithmetic" inJean van Heijenoort, translator and ed. (1967)From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 302-33.

References

[edit]
  • Brainerd, W.S.; Landweber, L.H. (1974),Theory of Computation, Wiley,ISBN 0471095850
  • Fachini, Emanuela; Maggiolo-Schettini, Andrea (1982), "Comparing Hierarchies of Primitive Recursive Sequence Functions",Zeitschrift für mathematische Logik und Grundlagen der Mathematik,28 (27–32):431–445,doi:10.1002/malq.19820282705
  • Hartmanis, Juris (1989), "Overview of Computational Complexity Theory",Computational Complexity Theory, Proceedings of Symposia in Applied Mathematics, vol. 38, American Mathematical Society, pp. 1–17,ISBN 978-0-8218-0131-4,MR 1020807
  • Rogers, Hartley Jr. (1987) [1967],Theory of Recursive Functions and Effective Computability (Reprint ed.),MIT Press,ISBN 9780262680523
General
Theorems (list)
 and paradoxes
Logics
Traditional
Propositional
Predicate
Set theory
Types ofsets
Maps and cardinality
Set theories
Formal systems (list),
language and syntax
Example axiomatic
systems
 (list)
Proof theory
Model theory
Computability theory
Related
Retrieved from "https://en.wikipedia.org/w/index.php?title=Primitive_recursive_function&oldid=1324017254"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp