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,
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
More information about the FOM
mailing list