Problem Detail: 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?
Asked By : Drupalist
Answered By : Jake
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33772 Ask a Question Download Related Notes/Documents
