[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
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
More information about the FOM
mailing list