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

*To*: fom@math.psu.edu*Subject*: FOM: brief comment*From*: Rod Downey <Rod.Downey@MCS.VUW.AC.NZ>*Date*: Thu, 22 Jul 1999 12:17:13 +1200 (NZST)*Cc*: downey@MCS.VUW.AC.NZ*Sender*: owner-fom@math.psu.edu

I am very reluctant to post to things like this, not because I do not have opinions, (as many of you know I could be more described as opinionated), but because of my feeling for the value of newsgroups, filling the airwaves with people shooting from the lip. however, I nwould like to comment non steve's remarks that the priority method is almost completly absent from ``applied '' recursion This might have bee true in the past, and certainly remains true for some areas such as combinatorial group theory, but it is certainly now false. Virtually all results in computable linear orderings and recent computable model theory use priority argument, most infinitary, and some even worker arguments. For instance, the recent work by Cholak, Shore Goncharov etc on degree spectra are all infinitary arguments, and the isomorphisms constructed are necessarilt delta _3. I find it hard to imagine easy ways to construct such things without priority. Even in combinaorial group theory there have been applications. some by Higman 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. The material on effective boolean algebras all uses the priority method, as of course the work on jump degrees of structures. Enormous amounts of work in inductive inference, particularly by Kummer, use the PM. There is no point in continuing with the examkples above, there are so many more. This is only to be expected. In some sense, the older coding methodfs ran out of steam and more recent problems either need deepeer understanding of the structures at hand, or they needed deeper use of the peiority method. It is like classical complexity used simple delayed diagonalization and direct diagonalization. recent work has used very sophisticated arguments from probability, coding theory, forcing, priority aguemtns, etc. this just indicated more maturity in the area. I think the biggest problem logicians have is that they ask differnet questions than most mathematicains. we are concerned with definability and the like. this is not the usual concern of classical mathematicains. Would, for instance, a natural transformation be formualted by a logician in the same way as it was done, or would it be more like definable in ZFC.... anyway, CRT as a model has been enormously successful. complexity etc and the notions of completeness and reductions have proven paradigms. 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. Obviously we are in fact doing things about online algorithms. In an online situation, even though atrustures are finite, like DEAMONS in somputers, the can be modelled by infinite processes. we are exploring these things. See the article by Keirstead in the Handbook. anyeway, I am in singapore, and this is a very slow telnet connection. I cannot seem to correct my typing and the family are agitating for breakfast. The above is towards some ideas, and correcting n, at least in my view, steve;s comment about the use of PM in applied recursion. also I hope that it corrects the view that bob speaks for workers in the area. This is not true. it is just that we may weel be reluctant to get involved ion things that become so time consuming. sorry about the typing. but again I ncannot seem to correct by rod ~~c downey

**Follow-Ups**:**Stephen G Simpson**- FOM: priority arguments in applied recursion theory

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

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