FOM: brief comment

Rod Downey Rod.Downey at MCS.VUW.AC.NZ
Wed Jul 21 20:17:13 EDT 1999

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,
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 

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


~~c downey

More information about the FOM mailing list