FOM: little steps for little feet

[George Odifreddi]

i'd like to make two minor comments on the long postings of harvey and
bob, which naturally deserve a much more careful look that this.

1) harvey says that he knows of no mathematically natural example of
an r.e. set of natural numbers that is not recursive, and no similar
example that is r.e. complete.

i think there is ONE, at least. kolmogorov defined a natural number as
RANDOM if it is less than or equal to its shortest description. so, for
example, "1 followed by a million 0's" is not random. 

one can prove that the set of non random numbers is simple in the sense
of post. in particular, it is not recursive and not m-complete. however,
it is turing complete. 

if this is considered as a natural set, then it solves both questions 
of harvey at once. for those interested, the proofs of these results
are in volume I of my book (classical recursion theory).

2) bob starts questioning the interest of reverse mathematics, in the
same way some people question the interest of recursion theory. i'm
not going to enter the dispute, but i just wanted to point out the fact
(probably quoted in steve's book) that reverse mathematics has a very
old tradition. 

the first example i can think of is john wallis' proposal of replacing
the parallel axiom by the theorem that "given any triangle and a
segment, one can construct on that segment a triangle similar to the
given one". he finds this axiom more natural than the parallel one,
being an analogue of the other axiom that given a point and a radius
one can construct a circle with that radius and center in the given
point". and then he derives the parallel axiom from this new axiom,
thus proving the equivalence of the two over basic geometry as the
base theory.

obviously, all proofs of equivalence of the parallel axioms to other
theorems of euclidean geometry are examples of reverse mathematics.

3) on the other hand, one could similarly claim that degree theory 
really started in euclid's book X, where a classification of real
numbers is given in terms of a degree notion defined via a reducibility
notion related to rational dependency. 

once again, thus, it seems that, as borges once said, "every age tells
the same stories in its own words".

4) a propos of quotations, some readers have asked me what the quote
from myhill was in my previous posting, since the transmission had played
some tricks with it.

here it is: "recursion theory is a subject full of ingenuity, but not
of intelligence". this was from an old manuscript in the 70's, and i
don't know if it was ever published, but i once reminded myhill about
it in the 80's, and he held to it. 

my point in quoting it was that we (recursion theorists) should be 
aware of the perception that our field has on other people whose work
and ideas we respect. after all, myhill was one of the early major
contributors to the field, and rather than being offended i was and
am interested in what he had to criticize in it. 

for the same reason, i don't dismiss simpson's view on recursion theory,
because he too has contributed major results and, especially, 
perspectives to it:  i'm thinking here not only of his characterization
of the complexity of the theory of degrees, but also of his work on
admissible degree theory, on bounded induction and, least but not last,
on natural definitions of degrees. 

i'm saying this to cool down a bit the heat of the debate, and to
recognize that some parts of recursion theory have indeed become very
technical, to the point of appearing disgusting to many people, outside
and inside the field.

bob stresses the importance of getting new results. personally, i would
put more stress not only on the interest of the results (lenin once
said to his followers: "better less, but better"), but also on the
ratio of: interest of result/difficulty of proof. 

it is perfectly justified, in my view, to use all the machinery one can
use to prove the definability of the jump or the existence of nontrivial
automorphisms of the degrees. perhaps it is less to use monster injury
arguments to prove simple curiosities. and perhaps THIS is what 
outsiders complain about.

i hope i'm not offending anybody by these remarks. they're just my point
of view, but they may show that there is room for the middle way, in
this debate.

george odifreddi