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

[Peter Smith]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 1050 bytes
Desc: not available
Url : /pipermail/fom/attachments/20030212/11660b92/attachment.bin