From: "Robert I. Soare" Sender: Computability Theory To: COMP-THY@LISTSERV.ND.EDU Subject: announcement and corrections Date: Fri, 9 Jul 1999 17:16:43 -0500 TO: Researchers in Computability Theory and Mathematical Logic RE: AMS Meeting, Computability Theory and Applications, Boulder DATE: July 9, 1999 POSTED: This message is posted on the WEB page: http://cs.uchicago.edu/~soare/lectures/corrections.html As you may, know an excellently organized theory was held in Boulder, Colorado in June. Steven Simpson immediately circulated a summary and review of the meeting. Although he gave a full account of the "reverse mathematics" part, there were some mistakes and omissions in other parts, particularly the new material on applications of computability theory to topology and geometry. We now correct these. See especially the conclusion in the last section, section 5. This message also contains comments and references for some exciting new work by Nabutovsky and Weinberger on applications of computability theory and computably enumerable (c.e.) sets to topology and differential geometry. These may be the MOST IMPORTANT and interesting applications of computability theory to topology IN TWENTY FIVE YEARS. (See section 4.) [I apologize if you receive multiple copies of this msg because you may be on several email lists.] ************************************************************************* Robert I. Soare Paul Snowden Russell Distinguished Service Professor Department of Mathematics The University of Chicago E-MAIL: soare@cs.uchicago.edu 5734 University Avenue WEB: http://www.cs.uchicago.edu/~soare Chicago, IL 60637-1546 USA ************************************************************************** ******* SECTION 1. AN OVERLY SHARP DICHOTOMY ************************* QUESTION 1. How did Simpson characterize the meeting? ANSWER 1. Simpson divided up the meeting into the categories of "pure" and "applied" computability theory, and placed every talk in one category or the other. This is a stronger distinction than most computability researchers would have made. QUESTION 2. How does Simpson characterize the "pure" computability theory? ANSWER 2. Simpson stated that a hallmark of this area has been priority arguments and claimed, "But priority arguments are almost completely absent from applied computability theory." Simpson saw, "very little actual connection between the two domains." These views are not supported by the evidence in the field (see Sections 2-3), and are dramatically contradicted by latest applications of computability theory to topology (see Section 4), which was one of the highlights of the Boulder conference. Carl Jockusch has thoughtfully suggested that a more accurate classification of results in computability theory including three areas, which we slightly modify and expand here. AREA I: CORE ("PURE") COMPUTABILITY THEORY. This area includes primitive recursive functions, general recursive functions (Godel), Turing computable functions, Turing reducibilities, Turing degrees and strong reducibilities; Kleene recursion theorem, Post's papers and dynamic construction of c.e. sets; the lattice of c.e. sets including the Friedberg splitting theorem and maximal sets, the upper semilattices of c.e. degrees and the Turing degrees and other degree structures; other reducibilities including strong reducibilities, and enumeration reducibility; numeration theory (Novosibirsk School), the Post program of finding the relationship between the algebraic structure of a c.e. set and its degree, automorphisms, definable properties, model theoretic properties (such as homogeneity and elementary types) of c.e. sets and of c.e. or Turing degrees or other degree structures; global degree theory; questions of homogeneity, elementary types, and undecidability for all c.e. set and degree structures; higher computability theory (Alpha and Beta computability, computability in higher types; and other such topics. Area I includes the material from such standard reference books for core computability as: Rogers [1967], Lerman [1983], Soare [1987], Sacks [1963] and [1991] and others. AREA II: "INTERACTIVE" COMPUTABILITY THEORY This includes the interaction of computability theory with other areas in logic and established mathematical areas where methods from computability and logic are used to analyze the computable content, logical setting, underlying axioms, and other effective or logical aspects of these fields. This includes: computable model theory, computable algebra: computable Boolean algebras, degree and spectrum of linear orderings, groups, fields, vector spaces; intuitionistic mathematics, computable analysis and computable topology (finding a computable systems of differential equations with no computable solution), constructive mathematics, reverse mathematics, computable aspects of foundations of mathematics (FOM), models of Peano arithmetic and true arithmetic, intrinsic c.e. relations, determining the degree spectrum of an algebraic structure, e.g. a linear ordering; computable categoricity, especially for omega_1 categorical structures; computable anologues or lack thereof for classical model theoretic results, numeration theory applied to algebraic structures; finitely axiomatizable theories and Lindenbaum algebras; and many more. AREA III: COMPUTABILITY APPLIED TO AREAS OUTSIDE LOGIC TO GIVE NEW MATHEMATICAL RESULTS IN THOSE AREAS. This is the computability theoretic analogue of Hrushovski's application of Shelah's stability theory to solve the Mordell-Lang conjecture in algebraic geometry. Both Areas II and III are interesting and important. The difference between AREAS II and III is it that Area II is concerned with the computational and logical content of some KNOWN results in another area, Area III contributes NEW results to that other field. Area III includes: the solution of Hilbert's Tenth Problem (Davis, Putnam, Robinson, Matijasevic); the unsolvability of the word problem for finitely presented groups, and the fact that every c.e. degree is represented as the degree of such a word problem (Boone-Novikov); applications of computability to problems in theoretical science (particularly structural complexity theory which grew mainly out of Area I); undecidable problems in several area of mathematics; the recent applications by Nabutovsky and Weinberger of computably enumerable sets and degrees to topology (see Section 4). THE MAIN POINT: The main point is that most researchers in the subject see these three areas as an interwoven whole, not as separate parts. They are delighted if they can apply results from another to advance their research, and those in the first area are stimulated to develop more tools for the second area. They believe that computability as a whole is a very beautiful and natural area of mathematics worth studying for its own right without justification by any "applications," but which has had and will continue to have many uses in other areas inside and outside of logic. They usually work in more than one of these areas, and are glad to hear and master methods and results even in those areas where they have not worked previously. They would not divide the invited talks for a major conference in to two or three area, and deprecate and dismiss those in areas other than their own. To depreciate any single area of computability or any method is pointless, unwarranted, and needlessly diminishes our field. (See the remarks in section 5.) ******* SECTION 2. SIMPSON'S PRESENTATION OF THESE AREAS ******************* Simpson gave a fairly complete and sympathetic account of the Boulder lectures in Area II, especially those in reverse mathematics, FOM, and his mailing list. He dismissed several of the talks in Area I and downgraded their interest and importance. For example, he dismissed the Boulder lectures by two senior invited speakers from Europe and Russia, respectively, with the curt epithets: "A pure recursion theory talk," and "Another pure recursion theory talk;" and wrote of a second European researcher with a first rate result, "I missed this talk and don't know what it was about." After giving such short shrift to these internationally respected senior speakers, Simpson found space to describe his OWN lecture and followup session to which he gave fulsome praise, "this took place in a separate room, which was packed with distinguished people, even if I do say so myself." Simpson then presented and circulated his summary to the many readers of his FOM list as a factual account of the Boulder meeting. As for Area III, Simpson misquoted the first paper by Nabutovsky-Weinberger on very recent applications of computability to topology, and omitted any reference to the results from second paper. Is Simpson's goal to inform his readers in a balanced, fair, honest manner, or to tailor the facts selectively to support a long held, preconceived view that the importance of an area in computability theory is inversely proportional to its distance from Simpson's own interests? Further comments by senior members of the community may be found in the last section, section 5. QUESTION 3. Is there any application of a priority argument which Simpson *does* recognize? ANSWER 3. Yes. Simpson is enthusiastic about a result of Kucera that there is a pair of disjoint c.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 c.e. set is computable in the pair (X,Y). Simpson writes that he included no priority arguments in his book (1998), but would have included this one had he known of it. His Boulder report even gives a proof: choose a maximal set C whose complement dominates every partial computable function, and then Friedberg split C into A and B. QUESTION 4. WHEN was this theorem proved? ANSWER 4. The existence of such a maximal set C was proved in 1965 by Yates, using one of the first 0''-priority arguments, and the Kucera Friedberg splitting and application was proved in: [Logic Colloquium'86, North Holland 1988, 133-141]. ****** SECTION 3. OTHER APPLICATIONS OF "PURE" METHODS *************** QUESTION 5. Are there any other people who are also unaware of the applications of priority arguments? ANSWER 5. If so they should check the web site: www.cs.uchicago.edu/~soare/lectures/applications.html where these will be gathered and listed for information. In only two days over seventy-five such references have been received from only five people. Many more are expected. (Please send them to Soare.) QUESTION 6. Are there any OTHER tools from "pure" computability theory which have been applied elsewhere? ANSWER 6. Yes. There are are a number of such tools, including Lachlan games, multiple strategies, the tree of strategies method, and others. A recent example is Russell Miller's use of the tree of strategies method to answer a question of Downey about the spectrum of some algebraic structure. See: www.cs.uchicago.edu/~soare/lectures/applications.html ***** SECTION 4. COMPUTABILITY AND TOPOLOGY ********************* QUESTION 7. What are the recent results in topology which use results from computability theory? ANSWER 7. There are two papers on recent applications of computability theory and computably enumerable (c.e.) sets and degrees to differential geometry and the space Met(M) = Riem(M)/Diff(M) of Riemannian metrics on a manifold M of dimension greater than four. The two recent papers are: PAPER (1): Variational problems for Riemannian functionals and arithmetic groups, (submitted for publication). [Available from the author: weinberger@math.uchicago.edu/~shmuel] PAPER (2): The fractal nature of Riem/Diff I. (Draft: Work in Progress). Paper (2) was discussed in a talk Wednesday evening at Boulder, and Paper (1) in a longer talk on Thursday morning. QUESTION 8. What did Simpson report about this new application to topology? ANSWER 8. Simpson wrote that the, "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, ... " QUESTION 9. Is Simpson's account mathematically correct? ANSWER 9. No. One of co-authors of the topology papers responds that Simpson, "misquotes Markov's theorem, which is about 4-manifolds, not 5-manifolds. The relevant precedent theorem in that direction is due to Novikov, who showed that the 5-sphere is not recognizable. The key new aspect in this type of work is showing that the sphere can't be distinguished from other manifolds which can be proved to have very strong (differential geometric) properties that the sphere does not have...and then use that to study the sphere. Our main result is *not* an undecidability result, although we *do* have a new undecidability result that is crucial for the proof of the main theorem." QUESTION 10. Paper (2), presented Wednesday evening at Boulder, contains the main connection between fractals, their local minima, and computably enumerable sets. What does Simpson say about these topics? ANSWER 10. Nothing. QUESTION 11. But Simpson's report stresses *applications*. These results constitute one of the most important and exciting applications of computably enumerable sets to topology in 25 years. The talk showed how the Sacks Density Theorem for the computably enumerable degrees was used to compare the depth of local minima at different levels. What summary does Simpson give of the application of the Sacks Density Theorem on c.e. degrees to give comparative depth estimates for local minima of different levels? ANSWER 11. Nothing. QUESTION 12. How do the authors use computably enumerable (c.e.) degrees? ANSWER 12. They write, "Informally, each c.e. degree determines a scale, and at that scale there are many distinguished local minima of diameter, that are deep at that scale. At smaller scales, of course, there will be smaller `basins' that `come off' this one." QUESTION 13. What other constructs of pure computability theory are used. ANSWER 13. The authors write, "... in addition to Turing machines being useful as a measure of rates of growth, we also find them useful in the description of types of subsets on the integers ..." QUESTION 14. What of the degrees of unsolvability? ANSWER 14. They write, "In order to space out critical points suitably around Met(M), we will also vary the `seed' group in terms of the degree of undecidability." For more information about Paper (2) see: http://cs.uchicago.edu/lectures/geometry.html For this message see: http://cs.uchicago.edu/lectures/corrections.html ========================================================================= ************* SECTION 5. COMMUNITY OPINION *************************** The following comments were made by several of the most respected and influential senior researchers after seeing Simpson's summary. ------------------------------------------------------------------------ RESEARCHER 1: "What disturbs me about Simpson's comments is that he seems to feel that pure computability theory is without interest, or at least this is the implication I get from it. My opinion is that computability is a beautiful and natural object of study. However, tastes and opinions differ, and this is basically a subjective decision." "Overall, I don't really understand why Simpson circulated his report about the meeting. People who were at the meeting could form their own impressions, while others are unlikely to be interested in such a detailed report." --------------------------------------------------------------------------- RESEARCHER 2: "I agree that his comments were inaccurate and unfair but my unwillingness (inability) to deal with these issues as an ongoing online daily argument is the reason I don't read FOM." --------------------------------------------------------------------------- RESEARCHER 3: "I was annoyed by his inaccuracies, unfairness, and the tone of his report, but he does not have an open mind so I do not want to get into an open debate with him because it is pointless to try to change his mind, and a debate is exactly what he wants." ------------------------------------------------------------------------- RESEARCHER 4: "I looked at Simpson's site. The following are some of my impressions." "Simpson's FOM mailing list is a pretty wild place. I looked at a thread from an earlier month and there is a of lot name calling, hot responses made within minutes of the previous message, and just plain unfiltered (despite its moderation!) speculation. For what its worth, it does seem that occasionally people do change their minds (slightly) from one message to another, so I guess it's not all heat. But, I doubt that anyone who reads it regularly will view it as a canonical source of received wisdom. "It's really a wild place." ------------------------------------------------------------------------- CONCLUSION: Is it not time that we recognize the mathematical merit, beauty, and importance of ALL the components of computability theory as listed in the three areas above, and including more topics as well? Can we not celebrate together the inherent beauty of the results and rejoice in their application and interaction with other areas of logic and mathematics? Can we not agree that foundations of mathematics and reverse mathematics are beautiful and important parts of the subject without also denigrating and dismissing other parts? Can we not develop and explain our own results without deprecating the importance and interest of results by others? Can we not recognize that the ideas and methods of one part of computability stimulate other parts and enrich the whole? The subject of computability stands much stronger and more interesting than even a decade ago, both internally and in its interactions and applications to other areas. The scientific community and mathematical community in general and the logic community in particular are becoming more aware of the role that the concept of computability in the sense of Godel and Turing can play. Let us work together to ensure that these advances and applications continue and expand.