[FOM] A question for Recursion Theorists

[mail@sakharov.net]

Hello,
Sorry for a late response. I awaited for more authoritative recursion theorists of the FOM community than me to elaborate on this topic. I am not a recursion theorist, but I am a big fan of this area of knowledge because of its negative results. Diagonalization is a basis for negative results in the recursion theory. In particular, it helps find undecidable sets.

Negative results are the most puristic math in a sense. In any other science, negative results are deemed of no or little value. Not so in math. The recursion theory, in my opinion, is a theory of negative results in the first place. Negative results are the most puristic because they are less materialistic than any others. These results make math stand out as a spiritial discipline in contrast to other sciences. I would say that the most remarkable math discoveries of the 20th century are negative results. 

It is funny that my first reaction to the quoted sentence from Roger's monography was quite opposite. I noted this sentence while studying the course of the recursion theory taught by Anatol Slissenko at St Petersburg University in Russia. My reaction was like: "That is it!" When studying this subject, I had to go through numerous exercises in proofs of undecidability. You do these proofs either directly by using diagonalization or - most often - you reduce your problem to another problem that is known to be recursively undecidable. In the latter case, you basically recur to diagonalization.

Undecidabilty is important because it sets up a stage for the entire theory of computability. Before theories related to computability emerged, the naive default view was:  every problem is decidable, but we may not be smart enough to figure it out how to construct a decision. Now we know that most problems are undecidable and actually the decidable ones are kind of less interesting and more trivial. The most of math theories are expected to be undecidable. Decidable theories like classical propositional logic present interest to complexity theorists only. The recursion theory studies undecidable sets. (I jumped to sets from problems, but it is legitimate due to Godel numbering.) Diagonalization is a way to administer the first test of undecidability. 

Speaking of proof methods in recursion theory in general, they are no different than those in the rest of math. It is the bottom layer that is based on diagonalization. Once we get through the bottom layer, a usual mathematical cuisine starts, and proof methods in the recursion theory reached beyond diagonalization even before sixties of the last century.
Alex Sakharov



-----Original Message-----
From: steve newberry <stevnewb at ix.netcom.com>
Sent: Sep 18, 2003 9:25 PM
To: Foundations Of Mathematics <fom at cs.nyu.edu>
Subject: [FOM] A question for Recursion Theorists

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

Steve Newberry

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom