"Primitive recursive functions" (1947 paper by Raphael Robinson)

[David]

Guys,

I just got a 15-minute break at work without our book, so I could not
make progress on chapter 12. But I picked up the article I mentioned
earlier in a different thread. Even though Nick does not have the
article yet, I think it makes sense to start a new thread for each
paper (Mike said he would start reading it as well).

OK, so I have read pages 925-927 only (that is, the first section),
but it is a real beauty! For example, the way he defines the following
functions, in order, from the basic functions, is quite neat:

D(x) = x % 2 (the characteristic functions of the odd numbers)

T(x) = x % 3

trunc(x/2) (the integer division by 2)

trunc(sqrt(x))

Q(x) (the characteristic function of the perfect squares)

And that's just the intro... The main result is apparently in the next
section.

Enjoy!

[David]

I just found the paper online, it's at:

http://www.ams.org/bull/1947-53-10/S0002-9904-1947-08911-4/

Apparently the whole journal (Bulletin) is available for free online.
Wow!

I read the rest of the paper diagonally and it is about whether
simpler forms of recursion (than the classical one we studied) are
enough to generate all of the primitive recursive functions, and if
not, which basic functions are enough to make up for the difference. I
am pretty sure that this paper will not shed light on the Ackermann
function, but I'll read it some more anyway. It should not hurt to
know more about PRF for when I get to the next paper by Robinson in
which he does prove that the Ackermann function is not primitive
recursive.