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

*To*: fom@math.psu.edu, Rod Downey <Rod.Downey@MCS.VUW.AC.NZ>*Subject*: FOM: priority arguments in applied recursion theory*From*: Stephen G Simpson <simpson@math.psu.edu>*Date*: Thu, 22 Jul 1999 20:32:42 -0400 (EDT)*In-Reply-To*: <199907220017.MAA20208@bats.mcs.vuw.ac.nz>*Organization*: Department of Mathematics, Pennsylvania State University*References*: <199907220017.MAA20208@bats.mcs.vuw.ac.nz>*Reply-To*: simpson@math.psu.edu*Sender*: owner-fom@math.psu.edu

Rod Downey (FOM, 22 Jul 1999 12:17:13) argues against what has now come to be called Simpson's Thesis, i.e., my observation (FOM, 21 Jun 1999 21:36:37) that ``priority methods are almost completely absent from applied recursion theory.'' Thank you, Rod, for a valuable FOM posting. I hope this will be the start of a thorough discussion, and I hope recursion/computability theorists will view it as an opportunity to explain what they mean by ``applied recursion/computability theory'' and how various recursion-theoretic concepts/results/methods (including priority methods) come in. First of all, I think everyone agrees that priority arguments are *much less* prevalent in ``applied recursion theory'' than in the ``pure'' theory of r.e. sets, r.e. degrees, etc. That contrast was my original point in stating Simpson's Thesis, and I think it is a valid and important point for anyone interested in recursion/computability theory to keep in mind. Nevertheless, it may still be worthwhile to examine Simpson's Thesis as an isolated proposition, apart from ``pure'' recursion theory. First, let's get clearer on what we mean by ``applications''. In my original remarks (FOM, 21 Jun 1999 21:36:37), there was room for misunderstanding because my definition of ``applied recursion theory'' was not very precise. I defined it as > 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. and this was not perfect because, in the first place, the ``etc'' could conceivably cover a lot of other areas that might be called application areas. Furthermore, my reference to ``recursive mathematics'' was ambiguous, because there are various schools (the Russian school, etc.), with various goals and programs. What I had in mind by ``recursive mathematics'' is what is sometimes called *recursive analysis*, i.e., analysis done in a recursive functions framework replacing the real number system by the recursive real number system, etc., the goal being to prove recursive analogs of the theorems of ``classical analysis'' when possible, and to give recursive counterexamples otherwise. This subject is expounded in two books that I am familiar with: O. Aberth, Computable Analysis, McGraw-Hill 1980 M. B. Pour-El and I. Richards, Computability in Analysis and Physics, Springer, 1988. Now, with that clarification in mind, I think it's correct to say that there are no priority arguments in these two books and few if any priority arguments in this general area, recursive analysis. (Are there more recent books or results in recursive analysis which use priority arguments? If so, I would like to hear about them.) Furthermore, priority arguments also seem to play a very small or nonexistent role in the other ``applied'' areas that I mentioned: intuitionistic mathematics (Kleene realizability, etc; see Troelstra/van Dalen, 1988) constructive analysis (see Bishop/Bridges 1985.) constructive algebra (Richman et al, ...) reverse mathematics (see my book ``Subsystems of Second Order Arithmetic'' <http://www.math.psu.edu/simpson/sosoa/>, 1999) theoretical computer science (At least the standard textbooks on computational complexity etc do not use priority arguments.) undecidable problems in mathematics (Diophantine problems, combinatorial group theory, etc.) But the recursion/computability theorists may want to dispute at least some of this, and I welcome further discussion. In order to deal seriously with the issues raised by the so-called Simpson's Thesis, we need a breakdown of the areas that might be called ``applied recursion theory'', and then an examination of where and how priority arguments are used in those areas. We must also be careful to distinguish different *types* of ``applications''. To quote from my message of a few days ago (FOM, 15 Jul 1999 22:33:53): If we are going to compile lists of ``applications'' of recursion theory, [...] then we ought to classify them carefully and distinguish various features, just as the applied model theorists do. For each ``application'' of recursion theory, we need to say what the field of application is, whether the statement of the result or only the proof involves recursion-theoretic concepts, which recursion-theoretic concepts and/or methods and/or results are used, whether the recursion-theoretic concepts and/or methods and/or results can be eliminated, what are the costs of eliminating them, etc. There are many distinctions to be made, and these distinctions are of essential scientific importance. It is misleading to lump everything together as ``applications'' without further qualification. For example, Downey mentioned computable model theory computable linear orderings computable Boolean algebras jump degrees of structures and it is true that priority arguments are used extensively in these areas. For instance, in computable model theory, there is Harrington's old result characterizing when a decidable theory has a decidable prime model, proved by means of a priority argument, which I always present in my model theory course; see <http://www.math.psu.edu/simpson/courses/math563/>. However, there is a serious and legitimate question of whether results in these areas are properly called *applications* of recursion theory. This is because the results themselves, and even the questions answered by the results, always mention recursion-theoretic concepts and often even mention advanced recursion-theoretic concepts. Contrast this with applied model theory, where one does not speak of an ``application'' unless first-order formulas and other logical or model-theoretic concepts are absent from the statement of the result. In the present context, it seems more legitimate to speak of ``connections'' between recursion theory and other parts of mathematics, rather than ``applications'' of recursion theory. In any case, the distinctions that I drew above are obviously relevant. See also Harvey Friedman's discussion of the so-called ``Simpson's Thesis'' (FOM, 19 Jul 1999 12:33:44). Another ``applied'' area is recursive algebra a la Metakides/Nerode, Remmel, Kalantari, Smith, et al. Here my experience has been that priority arguments are often eliminable and in these cases the proofs are presented more clearly without them. For example, Metakides/Nerode (Annals of Math Logic 1979) used a priority argument to construct a recursive infinite-dimensional vector space over the rationals with no infinite recursive linearly independent set. This is a very nice recursive algebra result, but it turns out that a stronger reverse mathematics result can be proved more clearly without a priority argument; see section III.4 of my book <http://www.math.psu.edu/simpson/sosoa/>. More on the relationship between reverse mathematics and recursive algebra is in my book and in my FOM posting of 18 Aug 1998 14:10:44. Additional ``applied'' areas that according to Downey use priority arguments are combinatorial group theory inductive inference complexity theory and here I confess that I am at a loss. Most textbooks of combinatorial group theory (Magnus/Karrass/Solitar, Lyndon/Schupp, ...) do not even prove the unsolvability of the word problem for finitely presented groups. But Downey mentions results of Higman (which results???), and > Khisamiev's msolution to the problem of Baumslag et al showing that > a recursively presented torsion free abelian group'' (in the > combinatirial classical nomenclature) is isomorphis to one with a > solvable word problem uses a finite injury arument. I don't know about this. Could somebody please provide a reference? In inductive inference Downey says that there are large numbers of priority arguments, but again I don't know this area. Do the results themselves mention recursion-theoretic concepts? Are the priority arguments eliminable? As for computer science, obviously the standard textbooks do not use priority arguments (look in the computer science section in your campus bookstore), but Downey says there is newer work: > A recent example is by Toueg and Chandra in the use of > failure detectors in asynchronous distribited computing. (Look up > failure detector on the web). This came from Chandra > attending a course on CRT by oDIFREDDI. it is seen as > some of the most important work in years. I think we could offer > a lot in thiat area. I followed Downey's suggestion and found titles of papers such as ``Unreliable Failure Detectors for Reliable Distributed Systems''. But the fact that one of the authors of a paper attended a course by Odifreddi doesn't tell us whether priority arguments are used in the paper, whether they are eliminable, etc. Could someone please clarify this situation? By the way, we have had some pretty good discussions of recursion theory and computer science here on FOM some months ago. Anyway, that's enough for now. I hope to continue this discussion later. -- Steve

**Follow-Ups**:**Stephen Fenner**- Re: FOM: priority arguments in applied recursion theory

**References**:**Rod Downey**- FOM: brief comment

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

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