1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ No, the PR functions are defined in terms of 1) some basic functions 2) some operations to build functions from ones already shown to be PR. One of the tools your book allows is for you to find the least $y$ satisfying some property, below some bound, and to output that $y$. If you drop the requirement that you have a bound, you get a more broad toolkit to build functions, and so, more functions. $\endgroup$ – James May 10 '15 at 20:59
  • $\begingroup$ I got stuck right now... I thought that the $\mu-$recursive functions have the minimalization operator and not the PR functions... @James $\endgroup$ – Mary Star May 10 '15 at 21:12
  • 2
    $\begingroup$ Well, if the passage you are quoting from your book makes sense, the book allows bounded minimization in the PR setting. Perhaps you should look at the definition? $\endgroup$ – James May 10 '15 at 21:42
3
$\begingroup$

If $f(x_1,x_2,\dots,x_n)$ is a primitive recursive function, then $$g(y,x_2,\dots,x_n)=\min_{k<y}f(k,x_2,\dots,x_n)=0 \;(\mbox{else }y) $$ is also a primitive function.

Hence primitive recursive functions are closed under limited minimisation. However if you remove the bound, you obtain the $\mu$ operator and get a larger class : the recursive functions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, the class of primitive recursive functions is closed under the bounded minimisation and the class of recursive functions is closed under the unbounded minimisation?? @Xoff $\endgroup$ – Mary Star May 11 '15 at 18:03
  • $\begingroup$ @MaryStar Yes, and the class of recursive functions is the smallest class of functions containing the class of primitive recursive functions and closed under the unbounded minimisation. $\endgroup$ – Xoff May 11 '15 at 18:45
  • $\begingroup$ In my book there are the following definitions for the $\mu$-recursive functions and the primitive recursive functions: math.stackexchange.com/questions/1258178/… Is the fact that the class of primitve recursive functions is closed under the bounded minimisation mentioned?? $\endgroup$ – Mary Star May 11 '15 at 19:44
  • $\begingroup$ @MaryStar No, but it's a (direct) consequence of primitive recursion, so when primitive recursion is used, bounded minimisation is assumed. $\endgroup$ – Xoff May 11 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.