Timeline for Does the normal form theorem imply that every partially computabe function is primitive recursive?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2014 at 14:36 | comment | added | Raphael | @Mohammad Just for completeness' sake, there are also non-primitive-recursive yet still total and recursive functions, e.g. the Ackermann function. | |
| Dec 6, 2014 at 14:07 | comment | added | M a m a D | 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. | |
| Dec 6, 2014 at 8:46 | comment | added | Raphael | @Mohammad That's a bit like saying, "if cars could fly then we could say that every plane is a car". | |
| Dec 6, 2014 at 8:45 | comment | added | M a m a D | Thanks. if $L(min)$ was primitive recursive then we could say that every partially computable function is primitive recursive, yes? | |
| Dec 3, 2014 at 11:37 | history | answered | Raphael | CC BY-SA 3.0 |