[FOM] A question for Recursion Theorists

Jeff Hirst jlh at cs.appstate.edu
Tue Sep 23 12:39:31 EDT 2003

Hi Steve-

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

I think that it is fair to say that diagonalization in some form is frequently
used in the proofs of the results in Rogers' book.  Given Rogers' goal of
answering "questions of existence or nonexistence of computational methods"
(p. 31), diagonalization is certainly a central technique.

Of course, a great deal of work has been done in this area since 1967, and
I don't think that it would be appropriate to refer to the current body
of computability theory as a "theory of diagonalization," at least not
without using a very (perhaps unreasonably) broad notion of diagonalization.

Jeff Hirst   jlh at math.appstate.edu
Professor of Mathematics
Appalachian State University, Boone, NC  28608
vox:828-262-2861    fax:828-265-8617

More information about the FOM mailing list