FOM: priority arguments in applied recursion theory
Stephen G Simpson
simpson at math.psu.edu
Tue Aug 3 15:25:04 EDT 1999
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?
More information about the FOM