FOM: an unusual recursion theory meeting; impressions of CTA talks

[Stephen G Simpson]

This FOM posting is about the recent meeting ``Computability Theory
and Applications'', which I will abbreviate as CTA.  For background,
see <http://www.math.psu.edu/simpson/cta/> and my posting of 21 Jun
1999 14:53:41.  Computability theory is of course a synonym for
recursion theory.

Obviously the organizers of the CTA meeting were concerned with a
distinction between *pure* recursion theory, i.e. the study of
structural questions concerning r.e. degrees, r.e. sets, etc., and
*applied* recursion theory, i.e. recursion theory connected to issues
and programs in f.o.m. and other areas, including: recursive
mathematics, intuitionistic mathematics, constructive mathematics,
reverse mathematics, theoretical computer science, undecidable
problems in mathematics, etc.  

Historically, the pure/applied dichotomy has been fairly stark.  For
example, priority methods were originated by Friedberg and Muchnik to
produce an incomparable pair of r.e. degrees, and difficult priority
arguments remain a hallmark of pure recursion theory.  But priority
methods are almost completely absent from applied recursion theory.
(Below I will point out an exception to this rule.)

At the CTA meeting, the pure/applied distinction was also much in
evidence.  Although the organizers tried to include a lot of applied
recursion theory talks and to bridge the pure/applied gap, there was
very little actual connection between the two domains.  There were
only a few points of intellectual contact between the pure recursion
theory talks and the applied recursion theory talks.  (Below I will
mention some of these points of contact.)

Here are some of my impressions of individual talks at the CTA
meeting.  I will post more on this later.  I urge other FOM
subscribers who were CTA participants to comment further.

 >     8:30-9:15   Sergey Goncharov,           computable model theory 
 >                 Novosibirsk
 >    11:00-11:20  Serikzhan Badaev, Almaty    numeration theory  
 >     3:30-3:50   Bakh Khoussainov, Auckland  issues in computable
 >                                             presentations of models
 >     7:20-7:35   Yuri Ershov, Novosibirsk    Computability in HF over
 >                                             a dense linear order

These Russian talks on recursive model theory were ``applied'' but
very hard to understand.  No motivation was given in terms of
f.o.m. or connections with other subjects.  Of this group of talks,
Khoussainov's was the easiest for me to understand, maybe because his
English is excellent.  I wish I knew this area better.

 >     4:00-4:20   Mikhail Peretyat'kin        finitely axiomatizable theories
 >                 Almaty                      and Lindenbaum algebras

It was very helpful that Peretyatkin circulated a 5-page abstract.
But his talk was hard to understand.

It so happens that Peretyatkin has a lot of beautiful results and
conjectures on properties of finitely axiomatizable theories, along
the lines of saying that given any recursively axiomatizable theory,
you can construct a finitely axiomatizable theory with similar
properties.  But I doubt that anybody could have gleaned this from his
talk, because he stated the results in an opaque way.  I understood
the talk, but only because I happen to have previous familiarity with
Peretyatkin's book.

 >    10:30-10:50  Julia Knight, Notre Dame    models of arithmetic

This was a nice ``applied recursion theory'' talk, linking recursion
theory to models of first-order arithmetic, PA.  Knight also
circulated a paper to go with the talk.  She emphasized Scott sets,
i.e., omega-models of WKL_0, as we reverse mathematicians prefer to
call them.

Knight mentioned the following problems, where S is a Scott set.

  0. Does there exist a model M of PA such that S is the Scott system
     of M? 

  1. If X belongs to S and is nonrecursive, does there exist Y in S
     that is Turing incomparable to X?

  2. If X belongs to S and is nonrecursive, does there exist a Scott
     set S_1 included in M such that X does not belong to S_1?

Question 0 has been around for a long time and there has not been any
recent progress.  The answer is yes if S is countable, by an old
result of Scott, and yes if S is of cardinality aleph_1, by an old
result of Harvey Friedman, but otherwise nothing is known.

Groszek and Slaman now think they can answer problem 1 affirmatively,
using difficult techniques from their recent paper showing that any
Scott set contains a minimal Turing degree.

It turns out that the answer to problem 2 was essentially already
known.  The answer to problem 2 is yes if the complete r.e. set
belongs to M, by the usual Gandy/Kreisel/Tait construction, and no
otherwise, by a result of Kucera in a paper published in the Logic
Colloquium 87 volume.

Kucera's result is as follows: There exists a recursively inseparable
pair of disjoint r.e. sets A and B such that if X and Y are separating
sets then either the symmetric difference of X and Y is finite or the
complete r.e. set is recursive in the pair (X,Y).

Outline of proof: Let C be a maximal r.e. set such that for all i, the
ith element of the complement of C is greater than the stage at which
the ith Turing machine halts, if it halts.  Thus the complete r.e. set
is recursive in any infinite subset of the complement of C.  Now apply
the Friedberg splitting theorem to decompose C as A union B.

[ It's interesting to me that this result of Kucera uses a priority
argument.  As everybody knows and as I mentioned above, priority
arguments are a distinctive hallmark of pure recursion theory and are
usually absent from applied recursion theory.  For example, my book on
reverse mathematics <http://www.math.psu.edu/simpson/sosoa/> contains
absolutely no applications of priority arguments.  However, if I had
known about this result of Kucera in time, I would certainly have
incorporated it into my book, in section VIII.2 to be exact. ]

 >     1:30-2:15   Jeff Remmel, San Diego      computable algebra  

This was a very rapid-fire talk with a zillion theorems on recursive
algebra and combinatorics, polynomial time algebra, etc.
Unfortunately there was no accompanying paper, and there was little in
the way of motivation.

A good thing that Remmel did was to advertise the recently published
two-volume collection of papers, ``Handbook of Recursive Mathematics''
(North-Holland), which he did a huge amount of work on, and which
looks extremely impressive.

 >     8:30-9:15   Peter Cholak, Notre Dame    lattice of computably
 >                                             enumerable sets 

This was an excellent ``pure recursion theory'' talk.  It dealt mostly
with the relationship between r.e. degrees and the lattice of
r.e. sets.  Why should anyone be interested in this?  No answer, and
no accompanying paper.  Eloquently presented, however.

 >     10:15-11:00 Bob Soare, Chicago     lattice of computably
 >                                        enumerable sets 

Another ``pure recursion theory'' talk.  The focus was on advanced
methodology for constructing automorphisms of the lattice of
r.e. sets.  Why should anyone be interested in this?  No answer, and
no accompanying paper.  Eloquently presented, but totally
incomprehensible except to experts on r.e. sets.

There were the usual Soare touches.  For example, Soare tried to push
a mystical or Zen-like analogy concerning a sword and a scabbard, with
references to the Star Wars movie series.  In addition, he made an
extremely dubious claim that high-school students can appreciate
advanced methods of constructing automorphisms of the lattice of
r.e. sets.  The reason that Soare gave is that experts on r.e. sets
such as himself are able to draw Venn diagrams presenting their
methodological ideas to each other, and every high-school student
understands Venn diagrams.

 >     11:10-11:30 Klaus Ambos-Spies,          genericity and randomness
 >                 Heidelberg        

This talk was a nice survey comparing various notions of genericity
(in the sense of Baire category) and randomness (in the sense of
Lebesgue measure), with connections to Kolmogorov complexity,
polynomial time computability, etc.  I had not previously been aware
of Schnorr's interesting work.

Ambos-Spies mentioned the following remarkable result of Kucera: there
exists a non-recursive real X such every Martin-Lof random real is
Martin-Lof random relative to X.  

[ Martin-Lof randomness is very interesting to me, because it is
closely connected to the formal system WWKL_0 which arises naturally
in the reverse mathematics of measure theory.  See my book for
references. ]

 >      1:30-4:50  Barry Cooper, Leeds         proof of the
 >                                             automorphism theorem,
 >                                             part 1 
 >     7:00-10:00  Barry Cooper, Leeds         proof of the
 >                                             automorphism theorem,
 >                                             part 2  

An amazing performance by Cooper.  More than 6 hours of well-prepared
lectures presenting some details of the latest version of Cooper's
massively complex proof that there exists a non-trivial automorphism
of the Turing degrees.  (Other results of Cooper imply that this
necessarily also gives an automorphism of the r.e. degrees.)
Apparently recursion theorists such as Slaman, Lempp, Harrington and
Cholak have tried to read the earlier version of the proof, which has
been available for several years in an as-yet-unpublished paper.  They
have not been convinced.  Hence this talk.

Cooper seems to have acquitted himself extremely well, answering most
or all of the objections that were raised.  I only hung around for the
first 20 minutes, but I got reports from other people.

[ I have a stake in this, because I proved years ago that every
automorphism of the Turing degrees must be the identity on a cone. ]

 >      8:30-9:15   Andre Nies, Chicago        definability and coding  

A ``pure recursion theory'' talk.  Somewhat hard to follow.  The focus
was the so-called ``bi-interpretability conjecture'' for the partial
ordering R of r.e. degrees.  The conjecture seems to be that there
exists an interpretation I of the standard model of first-order
arithmetic into R in such a way that there is an R-definable
isomorphism between R and its image under I.  This would have strong
consequences for our understanding of the structure of R.

There is a similar conjecture for the partial ordering D of all Turing
degrees and the standard model of second-order arithmetic.  Nies also
considered other structures, such as partial orderings of many-one
degrees.

[ I myself have something of a stake in this.  Long ago, in 1977 in a
paper in Annals of Math, I proved that there exists an interpretation
of the standard model of second-order arithmetic into D.  (The
existence of an interpretation going the other way is trivial.)  But I
did not obtain the additional properties that are now being
demanded. ]

 >     10:15-11:00 Richard Shore, Cornell      natural definability in degree 
 >                                             structures 

A very nice ``pure recursion theory'' talk.  A survey of properties of
r.e. degrees and Turing degrees that are definable over R and D
respectively by formulas that are ``mathematically natural'', i.e. do
not involve coding of the standard model of first-order arithmetic
into R.  There are many open problems.

 >     11:10-11:30 Gerald Sacks, Harvard & MIT   higher recursion theory

Actually Sacks ended up speaking on something else: work in progress
related to his long-term attempt to prove Vaught's conjecture,
building on old ideas of Scott and Morley.

Vaught's conjecture says that a countable theory with uncountably many
nonisomorphic countable models has a continuum of nonisomorphic
countable models.  This is an old, deceptively simple problem in model
theory.  Sacks has some ideas involving admissible sets that could
conceivably eventually lead to a solution.

 >     8:30-9:15   Steve Simpson, Penn State   reverse mathematics  

Before my talk I made available two handouts: (1) the front matter and
introductory chapter of my book on reverse mathematics
<http://www.math.psu.edu/simpson/sosoa/>; (2) an 11-page paper
describing some open problems in reverse mathematics
<http://www.math.psu.edu/simpson/cta/>.

I spent the first 25 minutes of my talk haranguing everybody about
f.o.m. and where reverse mathematics fits in and how it addresses some
basic f.o.m. issues.  Then I spent 20 minutes describing some open
problems in reverse mathematics.  After that I talked for another 40
minutes about open problems in reverse mathematics; this took place in
a separate room, which was packed with distinguished people, even if I
do say so myself.

One of the directions for future research that I emphasized is that of
weakening the base theory, from RCA_0 to something weaker.  This would
greatly expand the scope of reverse mathematics, by making it apply to
mathematical theorems that are provable in RCA_0.  A good start has
been made on this.

The next day, Harvey mentioned to me that the organizers of the CTA
meeting had expressed dissatisfaction with my talk, because according
to them I spent way too much time on issues and programs in f.o.m.,
and not enough time on open problems in reverse mathematics.  I was
quite discouraged to hear this.

Harvey, would you care to expand on this here on the FOM list?

This incident tends to confirm my impression that hard-core recursion
theorists see reverse mathematics solely as a source of open problems
for recursion theorists to work on and publish technical papers on,
and not at all in terms of philosophical or f.o.m. issues.  Is this a
fair summary of how recursion theorists view reverse mathematics?

This may be symptomatic of a kind of cultural gap between mathematical
logic and f.o.m.  I would like to discuss this further with hard-core
recursion theorists, including the organizers of the CTA meeting.

So far as I know, the only positive comment on my talk from someone
not actually doing reverse mathematics came from Martin Davis, who
said he enjoyed it very much, even the f.o.m. parts.  Thanks Martin!

By the way Martin, I hope you will post something here on the FOM list
about your impressions of the CTA meeting.

 >     10:30-11:00 Carl Jockusch, Urbana       Pi01 classes and computable
 >                                          combinatorics

A beautiful ``applied'' talk.  Part of it was about Pi^0_1 subclasses
of 2^omega, a chapter of recursion theory where Jockusch has
contributed a huge amount, and in which I am particularly interested
because it is closely related to omega-models of WKL_0 and thereby to
reverse mathematics.  Jockusch emphasized this connection.  Another
part of Jockusch's talk was about open problems left over from the
recent Cholak/Jockusch/Slaman paper on the reverse mathematics of
Ramsey's theorem for exponent 2 (71 pages, to appear in JSL).  This
paper has already been discussed extensively here on FOM.

 >     11:10-11:30 Chi Tat Chong, Singapore    reverse computability
 >                                            theory 

This is about a generalization of recursion-theoretic topics such as
r.e. degrees, etc., to nonstandard models of fragments of first-order
arithmetic.  The slogan ``reverse recursion theory'' arises here,
because some of the theorems say that a certain recursion-theoretic
result requires a certain amount of induction to prove.  So it's
something like reverse mathematics, applied to recursion theory.

[ I myself contributed a little to this area, in the early days of
reverse mathematics. ]

 >     1:30-2:15   Harvey Friedman, Ohio State    reverse mathematics  

This was a visionary talk on the history and future of reverse
mathematics.  Part of the talk had to do with ``severe reverse
arithmetic'', where one shows that very basic facts of elementary
number theory imply high logical strength, at least EFA.  Another part
had to do with analyzing the strength of propositions from the classic
number theory textbook by Hardy and Wright.  Another part dealt with
coding issues and was somewhat critical of the fact that I don't do
much in my book to explain my coding choices, even though (according
to Harvey) they are undoubtedly the correct choices.

I hope Harvey will make the text of his talk available soon.

 >     3:30-3:50   Sasha Shlapentokh,     issues related to Hilbert's Tenth
 >                 E. Carolina                 Problem 

A very nice talk on the problem of generalizing the MRDP theorem to
number fields and their rings of integers.  The 800-pound gorilla
problem here is whether the solvability of Diophantine problems over
the rational field is decidable.  Results and conjectures of Barry
Mazur were mentioned.

 >     4:00-4:20   Anil Nerode, Cornell        computable analysis and
 >                                           topology 

An inspiring ``applied'' talk.  Nerode surveyed the history of
recursive mathematics and intuitionistic/constructive mathematics, and
said that mathematical logicians should pay attention to these things.

 >     7:00-7:15   Bob Soare, Chicago          Computability and differential
 >                                             geometry 

In this talk Soare described some recent applications of recursion
theory to the study of spaces Riemannian metrics on compact manifolds,
in papers by Shmuel Weinberger (Soare's colleague at the U of Chicago)
and Alex Nabutovsky (U of Toronto).

Unfortunately Soare did not give enough details for anyone to
understand any of the underlying mathematics or the nature of the
application to Riemannian manifolds.  He claimed that the theory of
r.e. sets and degrees as presented in his book, including results such
as the Sacks density theorem, is highly relevant.  But he was unable
to back this up by explaining the application.  In any case, he is
obviously thrilled about this and views it as a vindication of pure
recursion theory.

In order to push these ideas, Soare and the CTA meeting organizers
arranged for Weinberger's talk at a concurrent meeting on manifolds to
be moved into the CTA meeting, so that the recursion theorists would
hear it.

Weinberger's talk was also fairly incomprehensible, but I got hold of
one of the Nabutovsky/Weinberger papers and read it on the plane home
from the meeting.  It goes back to the old Markov theorem that the
problem of whether a given compact 5-manifold is diffeomorphic to a
5-sphere is undecidable.  The main Nabutovsky/Weinberger result
(``Theorem 1'') is a refinement of this, saying that the same problem
remains undecidable if you restrict it to 5-manifolds which are
homology 5-spheres, i.e. indistinguishable from 5-spheres insofar as
homology is concerned.  So, given an instance i of the halting
problem, you can effectively construct a homology 5-sphere M_i (with
additional properties) such that i halts if and only if M_i is
actually a 5-sphere.  The proof of this uses Markov's result plus
undecidability of the word problem for groups plus erudite techniques
from the theory of arithmetic groups (A. Borel et al).

As an application, Nabutovsky/Weinberger deduce that for appropriate
values of the parameters x and v, the space of all compact Riemannian
5-manifolds with absolute sectional curvature less than or equal to 1,
volume greater than or equal to v, and diameter less than or equal to
x, is in a certain sense highly disconnected, and indeed these spaces
have a certain highly irregular or ``fractal-like'' nature.  Earlier
Nabutovsky had obtained some results along these lines.

I will post more about this stuff later.

 >     7:40-7:55   Doug Cenzer, University of  The lattice of Pi01 classes 
 >                 Florida      

Another ``pure recursion theory'' talk.  The Pi^0_1 subclasses of
2^omega form a lattice, and one can ask many of the same questions as
for the familiar lattice of r.e. sets.  The methods and results are
for the most part similar, but with interesting new twists.

 >     8:00-8:15   Eberhard Herrmann, Humboldt The definability of the      
 >                 University, Berlin          Sigma4-acceptable ideals 

Sorry, I missed this talk and don't know what it was about.

 >     8:20-8:35   Steve Simpson, Penn State   A Mailing List for
 >                                        Foundations of Mathematics  

This was an infomercial for the FOM mailing list.  I briefly presented
several of the f.o.m. issues that we have been discussing here on the
FOM list in the past year or two.

This created quite a stir.  Many junior researchers and grad students
were receptive to my message.  On the other hand, some senior
recursion theorists resented my insistence on the importance of issues
and programs in f.o.m. and on open forums such as the FOM list.

As a result of the aftermath of this talk, I have begun to wonder how
much my insistence on f.o.m. values is costing me.  I will post more
on this later.

During my talk, Martin Davis commented that there is a large contrast
between my mild-mannered personal demeanor and my outrageous behavior
on the FOM list.  I replied that this is an instance of a well-known
Internet phenomenon.

 >     8:30-9:15   Ted Slaman, Berkeley        applications of recursion
 >                                      theoretic methods in set theory   

This was a very nice survey of recent results arising in answer to a
question of Sierpinski, about 1-1 continuous images in descriptive set
theory.  Slaman invited recursion theorists to get interested in set
theory and apply recursion-theoretic techniques.

 >     10:20-10:50 Alekos Kechris, Cal Tech    Borel equivalence relations

Unfortunately Kechris didn't show up at the meeting, so his talk was
cancelled.  However, he has written a truly excellent survey paper:
``New Directions in Descriptive Set Theory''.  I highly recommend this
paper, especially to recursion theorists.

 >     11:00-11:20 Marcia Groszek, Dartmouth   independence results (from ZFC)
 >                                             in recursion theory  

A nice talk on some mostly old and apparently difficult problems about
uncountable sets of Turing degrees.  Closely related problems are
known to have answers that are independent of ZFC.

 >     1:30-2:15   Manny Lerman, Connecticut   lattice embeddings into the  
 >                                             computably enumerable degrees

A ``pure recursion theory'' talk, about the old problem of deciding
when a given finite lattice is lattice-embeddable in the partial
ordering of r.e. degrees.  Remarkably, Lerman suggests that this
problem may be undecidable!  He has a conjectured pinball-machine
characterization of such lattices, and the characterization involves
an AE condition.

 >     3:30-3:50   Andrea Sorbi, Siena         enumeration degrees     
 
A ``pure recursion theory'' talk, on results and problems in the
e-degrees.

 >     4:00-4:20   Marat Arslanov, Kazan       d.c.e. and n-c.e. degrees 

Another ``pure recursion theory'' talk.

-- Steve