FOM: priority arguments in applied recursion theory

[Stephen G Simpson]

This is a response to Rod Downey 31 Jul 1999 08:38:38.

Once again Rod, thanks for your posting.  I am delighted that you and
some other recursion theorists are getting drawn in to the FOM list.

 > I would be happy to continue this discussion over a beer, but fail
 > to see the point in getting involved in a long discusson.

Discussions over a beer are fine as far as they go.  But I also think
that extended, open, public, interactive, electronic discussions can
have a huge amount of scientific value.  This has been confirmed time
and time again here on the FOM list.

 > The references to the combinatorial argument are given in the paper
 > definability, computability and algebraic structures, available
 > from my web site.

Thanks for e-mailing the paper to me off-line.  It is a very nice
survey of a lot of topics.  Could you please post the web address for
your web site?  That way other FOM subscribers will be able to
download your paper, to use it as a basis for further discussion.

But, it's a long paper and I don't know what you are referring to by
``the combinatorial argument''.  Could you please explain?

 > Khisamiev proved that if $X$ is a ce presented torsion free group
 > then it is computably presented.

You mean Abelian groups.  Right?

This is an interesting result!  But, getting back to the topic of this
discussion, does Khisamiev's proof use a priority argument?  If so,
can the same result be proved more easily without a priority argument?

 > The Higman argument is in the Higman-Scott monograph.

I'm familiar with the Higman-Scott monograph on existentially closed
groups.  But I don't remember that it contains any priority arguments
or mentions any results that use priority arguments.  Are you saying
that it does use priority arguments?  If so, where?

 > Sorry I had thought that we were talking about computability in
 > mathematics, not priority, although many of the arguments mentioned
 > use priority.

We were definitely talking about *priority arguments*.  I thought that
was clearly understood.  You even started your FOM posting of 22 Jul
1999 12:17:13 with

  I nwould like to comment non steve's remarks that the priority
  method is almost completly absent from ``applied '' recursion

Is your FOM posting of 22 Jul 1999 12:17:13 now to be reinterpreted as
pointing to applications of recursion theory in general, rather than
specifically to *priority arguments* in applied recursion theory?

 > when a combinatorialist uses a backtracking argument as in e.g. the
 > methodology for matching in a bipartite graph, or in some
 > competitive online algorithm, or a computer scientist uses
 > e.g. methods like the decidability of S2S which, after
 > Gurevich-Harrington certainly resembles an infinite injury
 > argument, are there 'priority?'

I don't think these can be called priority arguments.

I sometimes teach an introductory graph theory course
<http://www.math.psu.edu/simpson/courses/math485/> in which I cover
the so-called Hungarian algorithm for matchings in bipartite graphs,
as well as the closely related Kuhn-Munkres algorithm for optimal
assignment.  In my opinion, there is backtracking but no priority
there.  The authors of these matching algorithms do not describe them
as priority arguments.  I don't think knowledge of Friedberg-Muchnik
or Sacks density other well-known priority arguments would help anyone
to discover or understand these matching algorithms.

As for the Gurevich-Harrington proof of decidability of S2S, I have
been through it and I don't think it is a priority argument.  Perhaps
Leo Harrington will comment?  In any case, the original Rabin proof of
this result was not a priority argument.

 > I suspect not but the ideas are very similar, as one would expect. 

Why would one expect that?

 > I remember when I taucht CS students at cornell spector forcing,
 > they immediately said ''oh that's easy, its just the proof that you
 > cannot solve consensus in a distributed environment' after
 > Fischer-Lynch Patterson.

My experience is that bright computer science students often see a lot
of similarities and analogies between things that aren't really very
similar.  So, let's temporarily put aside what the CS students said.
What do *you* say?  Is there *really* a lot of similarity between the
Fisher-Lynch-Patterson proof and Spector forcing?

In any case, Spector forcing isn't a priority argument.  Or, do you
think it is one?

-- Steve