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

[praatika@mappi.helsinki.fi]

"H. Enderton" <hbe at math.ucla.edu> wrote:

> That point is exactly why you're having trouble!  The "real" reason
> the primitive recursive functions can't exhaust the class of
> calculable functions is that we can diagonalize out so easily.
> 
> Historical evidence:  Kleene says that when Church told him
> Church's Thesis (1933?), Kleene didn't believe it.  He sat down
> and tried to diagonalize out of the lambda-definable partial
> functions.  It was his discovery that he couldn't do it that
> convinced him of Church's Thesis!


Church started to speculate about the issue in 1933, but presented his 
thesis in spring 1934. Kleene's recollections are from 
S.C. Kleene, 'Origins of recursive function theory', Annals of the History 
of Computing 3 (1981), 52-67. 

* * * 

what one takes as a natural and illuminating example of rec. but non-p.r. 
function may be a subjective matter and vary depending in one's interests 
and the context.  But at least in some contexts, I would personally use 
something like the following:

Fix some (natural) ordering of
(i) Diophantine equations: D1, D2,...
(ii) finite sequences of natural numbers S1, S2, ...

Define then f as follows:

          the "first" sequence Sm that provides a solution of Dn
f(n) = {    
          undefined, if Dn has no solution. 


(I hope that went right)


Panu Raatikainen

PhD., Docent in Theoretical Philosophy
Fellow, Helsinki Collegium for Advanced Studies
University of Helsinki

Address: 
Helsinki Collegium for Advanced Studies
P.O. Box 4
FIN-00014 University of Helsinki
Finland

E-mail: panu.raatikainen at helsinki.fi

http://www.helsinki.fi/collegium/eng/Raatikainen/raatikainen.htm