Recursive and Primitive recursive functions

[mathmari]

Hey!

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows:

1. The constant, projection, and successor functions are all $\mu-$recursive.
2. If $g_1, \dots , g_m$ are $n-$variable $\mu-$recursive functions and $h$ is an $m-$variable $\mu-$recursive function, then the composite function $f=h \circ (g_1, \dots , g_m)$ is also $\mu-$recursive.
3. If $g$ and $h$ are $n-$ and $(n+2)-$variable $\mu-$recursive functions, then the function $f$ defined from $g$ and $h$ by primitive recursion is also $\mu-$recursive.
4. If $g$ is a total $(n+1)-$variable $\mu-$recursive function, then the function $f$ defined from $g$ by unbounded minimalization is also $\mu-$recursive.

The definition of a primitive recursive function is the following:

1. The constant, projection, and successor functions are all primitive recursive functions.
2. If $g_1, \dots , g_m$ are $n-$variable primitive recursive functions, and if $h$ is an $m-$variable primitve recursive function, then the composite function $h \circ (g_1, \dots , g_m)$ is also a primitive recursive function.
3. If $g$ and $h$ are $n-$ and $(n+1)-$variable primitive recursive functions, then $(n+1)-$variable function $f$ defined from $g$ and $h$ by primitive recursion is also a primitive recursive function.

All primitve recursive functions are $\mu-$recursive, but the inverse doesn't hold, right??

I got stuck right now... The two definitions are similar and a function that is $\mu-$recursive satisfies $4$ properties and the first $3$ are very similar to the properties of a primitive recusive function. But there are $\mu-$recursive functions that are not primtive recursive. Could you explain to me why this hold?? (Wondering)

 

[Evgeny.Makarov]

Recursive (which is the same as mu-recursive) functions allow minimization in addition to the three constructions of primitive recursive functions you listed. This immediately opens the possibility that a recursive function is not total, since functions obtained by minimization do not have to be defined everywhere. There are also total recursive functions that are not primitive recursive. Kleene's normal form theorem shows that in constructing any recursive function it is sufficient to apply minimization only once.

 

[mathmari]

The minimization is the following: $$f(x_1, \dots , x_n )=\mu z[g(x_1, \dots , x_n, z)=0]$$ right? Could you explain to me what this means?

 

[Evgeny.Makarov]

Please see Wikipedia.

 

[mathmari]

In my book there is the following:

Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or effectively computable functions. It does not even include all the effectively computable total functions. It is therefore natural to ask how the class of primitive recursive functions can be extended so as to admit a larger number of effectively computable functions.

One approach is to remove the upper bound from the minimalization operator. The resulting composiition rule leads us to define a new class of effectively computable functions called the $\mu-$recursive functions. With the help of an important technique known as arithmetization, it is possible to show that Ackermann's functionis a $\mu-$recursive function. The same technique can also be used to show that every Turing-computable function is $\mu-$recursive and consequently that the class of $\mu-$recursive functions is identical to the class of Turing-computable functions.
Could you explain to me the part:

"One approach is to remove the upper bound from the minimalization operator."

Does this mean that the primitive functions are bounded above by the minimalization operator??

 

[Evgeny.Makarov]

The bounded minimization operator is $\mu z\le t.\,[g(x_1, \dots , x_n, z)=0]$. The term $t$ is the upper bound on the search for $z$ such that $g(x_1, \dots , x_n, z)=0$. The class of PRF is closed under this operator. The unbounded minimization operator is $\mu z.\,[g(x_1, \dots , x_n, z)=0]$. The class of PRF is not closed under it.