[FOM] A question for Recursion Theorists
stevnewb at ix.netcom.com
Thu Sep 18 21:25:40 EDT 2003
I begin by freely confessing that I am SADLY deficient in my study of
Recursion Theory, and am now trying to make up for it by plodding through
Hartley Roger's great monograph, THEORY OF RECURSIVE FUNCTIONS AND EFFECTIVE
COMPUTABILITY. The book is copyright 1967, and most of the foundation work
was done in the thirties and forties. Presumably, there have been a lot of
new theorems, methods, and proof techniques developed in the interim.
On p. 31, Rogers states, "It is not inaccurate to say that our theory is, in
large part, a 'theory of diagonalization'."
Does anyone know WHY this is so? Are there no other ways to prove the
Are none of the theorems capable of proof within the methods of Proof Theory?
Or the methods collected under the rubric of "Predicativity"? Or ANYTHING other
than the deadly repetition of one or another versions of the "Diagonal Proof"?
Or is it the case that no one feels that answers of such questions have any
relevance to Foundations?
I'm NOT trying to be wise guy, I really want to know.
Please, somebody, reply,
More information about the FOM