[FOM] Recursive but not p.r. computable functions -- the simplest "natural" examples???

[Jeremy Clark]

It depends on what you mean by a diagonal argument. Isn't Ackerman's 
function based on a diagonal argument
of sorts? (I mean, doesn't one show that Ackerman's function eventually 
outstrips any p.r. function by taking some
sort of fixed point?) On the other hand, what is so unnatural about 
diagonalisation? Suppose you encode all the
p.r. functions so that f(e,x) = the x-th value of the e-th p.r. 
function. Then f is total recursive and cannot be p.r. by
the usual diagonal argument. But f is also highly natural, especially 
to someone interested in computation
(f is a [p.r.] computer, basically).

Regards,

Jeremy Clark

On Wednesday, February 12, 2003, at 05:34 PM, Peter Smith wrote:

> I'm lecturing again this term to philosophers (nb, not 
> mathematicians!) about Gödel's theorems. computability etc. In two 
> weeks time, I'll be  talking about recursive functions and wanting to 
> give a "natural" example of a computable-but-not-primitive-recursive 
> function ("natural" = not defined by a diagonal construction). At this 
> point, I usually  mention a simple Ackermann function like e.g. the 
> one defined by the double recursion
> 	F(0, z) = Sz
> 	F(Sx, 0) = F(x, S0)
> 	F(Sx, Sz) = F(x, F(Sx, z))
> And then I cheerfully announce (not prove) that we can show that 
> F(n,n) is not p.r. I give some some arm-waving motivation but can I do 
> better???  Ideally I'd like an even more "natural" (and easily 
> motivated) definition of a computable function, such that I can prove 
> reasonably quickly and elegantly (to non-mathematicians) that the 
> function is not p.r.
>
> Any suggestions???
>
> Dr Peter Smith
> Director of Studies in Philosophy and HPS
> Jesus College, Cambridge CB5 8BL, UK
> www.phil.cam.ac.uk/Smith
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 1897 bytes
Desc: not available
Url : /pipermail/fom/attachments/20030212/8ad04a2e/attachment.bin