[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: an unusual recursion theory meeting; impressions of CTA talks*From*: Stephen G Simpson <simpson@math.psu.edu>*Date*: Mon, 21 Jun 1999 21:36:37 -0400 (EDT)*Cc*: shore@math.cornell.edu, mlerman@math.uconn.edu, cholak@nd.edu, lempp@math.wisc.edu, soare@math.uchicago.edu*In-Reply-To*: <14190.35381.262919.979651@mordred.cs.utk.edu>*Organization*: Department of Mathematics, Pennsylvania State University*References*: <14190.35381.262919.979651@mordred.cs.utk.edu>*Reply-To*: simpson@math.psu.edu*Sender*: owner-fom@math.psu.edu

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

**References**:**Stephen G Simpson**- FOM: an unusual recursion theory meeting

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]