Skip to main content
Commonmark migration
Source Link

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?

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?

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?

edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
edited title
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Is it true Does the normal form theorem imply that every partially computabe function is primitive recursive?

Tweeted twitter.com/#!/StackCompSci/status/540046879988662272
Source Link
M a m a D
  • 1.5k
  • 2
  • 18
  • 33
Loading