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

Peter Smith ps218 at cam.ac.uk
Wed Feb 12 11:34:19 EST 2003

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
-------------- 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

More information about the FOM mailing list