Timeline for Are there natural, small, and total recursive functions that are not primitive recursive?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2014 at 8:39 | comment | added | aws | I think this implies what you want, because every PR function can be simulated by a Turing machine bounded in time (and hence also in space) by the Ackermann function (modulo a constant). The functions themselves are all decision problems, so they are what you describe as small, and since they can't be simulated in Ackermann space, they are not PR. | |
| May 9, 2014 at 8:05 | comment | added | Armando Matos | Very interesting. I couldn't yet look carefully at those papers, but correct me if I'm wrong: (1) the function which is total recursive and not PR is the complexity of a certain (verification) problem. (2) that function grows faster than any PR function - it is not "small". | |
| May 8, 2014 at 22:01 | history | answered | aws | CC BY-SA 3.0 |