2
$\begingroup$

This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75):

Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a primitive recursive predicate $R(x_1,...,x_n,y)$ such that:

$f(x_1,...,x_n) = L(min R(x_1,...,x_n,z)_z)$ (minimization is on z)

So I think an immediate result of this theorem is that every partially computable function is primitive recursive and every primitive recursive function is partially computable. is it true?

$\endgroup$
  • 1
    $\begingroup$ This is trivially false if the given function isn't total. The question does make sense for total partially computable functions, i.e., computable functions. $\endgroup$ – Yuval Filmus Dec 3 '14 at 7:32
  • $\begingroup$ What does "total partially computable" mean? That sounds like an oxymoron to me. Wouldn't you just say "total computable" instead? Perhaps there is a subtly I am not picking up on here. $\endgroup$ – Jake Dec 3 '14 at 19:32
5
$\begingroup$

No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate.

What does seem to follow from this is that every computable function is $\mu$-recursive as primitive recursion is a subset of $\mu$-recursion. In fact I happen to know this to be true because $\mu$-recursion is turing complete.

You can check out primitive recursion and $\mu$-recursion on Wikipedia.

I also found a wikipedia page with some related matters. In particular they give another form of the Normal Form Theorem that seems slightly stronger; see here.

$\endgroup$
  • $\begingroup$ What is the difference between recursive function and primitive recursive function? $\endgroup$ – M a m a D Dec 3 '14 at 8:38
  • 2
    $\begingroup$ @Mohammad The difference between primitive and general recursion ($\mu$-operator), which is equivalent to the difference between for loops (the basic counting kind, not the sugared while loops in most programming languages) and while loops. $\endgroup$ – Raphael Dec 3 '14 at 11:33
5
$\begingroup$

You read the theorem wrong; the right-hand side contains this $L(\min \dots)$ -- this is not primitive recursive! Note that, in particular, such $z$ does not necessarily exist (the "algorithm" will loop.)

$L(\min \_)$ in that theorem is also called the $\mu$-operator. It can not be expressed with primitive recursion.

This theorem states that one application of the $\mu$-operator is enough for Turing-completeness. In terms of WHILE programs, this means that you can program any function with using at most one WHILE loop.

$\endgroup$
  • $\begingroup$ Thanks. if $L(min)$ was primitive recursive then we could say that every partially computable function is primitive recursive, yes? $\endgroup$ – M a m a D Dec 6 '14 at 8:45
  • $\begingroup$ @Mohammad That's a bit like saying, "if cars could fly then we could say that every plane is a car". $\endgroup$ – Raphael Dec 6 '14 at 8:46
  • $\begingroup$ Every primitive recursive function is total (computable) because it is obtained by finite number of applications of composition and recursion of initial and projection functions but partially computable functions can be both total and non-total. so partially computable function contains larger set of function than the primitive recursive class of functions. so you are right. $\endgroup$ – M a m a D Dec 6 '14 at 14:07
  • 1
    $\begingroup$ @Mohammad Just for completeness' sake, there are also non-primitive-recursive yet still total and recursive functions, e.g. the Ackermann function. $\endgroup$ – Raphael Dec 6 '14 at 14:36
2
$\begingroup$

The classical example of a computable function which is not primitive recursive is the Ackermann function. You can also construct such a function using diagonalization: given some effective enumeration $f_n$ of the primitive recursive functions, the function $n \mapsto f_n(n) + 1$ is computable but not primitive recursive.

$\endgroup$
  • $\begingroup$ Then what is the result of this theorem?! $\endgroup$ – M a m a D Dec 3 '14 at 8:43

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.