FOM: from Soare-Computability Theory and Differential Geometry
Martin Davis
martin at eipye.com
Mon Jul 10 17:46:51 EDT 2000
I am forwarding the following contribution from Robert Soare.
Soare is not a member of FOM even though he was a coauthor and
signatory of "Agreement about FOM". See the fom web site:
http://www.math.psu.edu/simpson/fom/deal.html
Three FOM postings in June mentioned Professor Soare and his work on
Computability Theory and Geometry and his invited lecture at the ASL
meeting in Urbana, in June, 2000. Professor Soare is entitled to
respond under the Agreement, Clause 5.1.
Martin Davis
FOM Referee
==========================================================================
1. GROMOV'S THEOREM
Matthew Frank Sun, 11 Jun 2000 10:11:16 -0500 (CDT) wrote:
>
> Soare mentioned a theorem that a compact Riemannian manifold with
> an unsolvable word problem has only finitely many closed contractible
> geodesics, characterizing this as logic coming in and geometry coming out.
> I think it is more helpful to look at the theorem as showing that, on a
> compact Riemannian manifold with only finitely many closed contractible
> geodesics, one can determine whether an arbitrary curve is contractible
> (and so the manifold's word problem is solvable). The theorem is proved
> in this form, showing geometry coming in and computability coming out.
In my Urbana ASL lecture I stated the following theorem announced
without proof by Gromov, and later proved by Nabutovsky [1996d].
Thm [Gromov]. Let M be a smooth manifold whose fundamental group
has an unsolvable word problem. Then there exist infinitely many
contractible, closed, geodesics on M.
Whether one states it in the form above (as Nabutovsky does in his
paper) or the contrapositive, Matt is right that it shows an
unexpected connection between computability and geometry, one going in
and the other coming out. However, the proof is much more complex
than the statement in contrapositive form might suggest.
Stephen Simpson 16 June 2000 wrote:
> According to my notes taken at Soare's ASL 2000 talk on the
> Nabutovsky/Weinberger stuff, this is a statement that Soare attributed
> to Nabutovsky. ...
Both Soare in his ASL lecture whose slide is contained in,
http://www.cs.uchicago.edu/~soare/FOM/gromov.ps
and Josh Maher in his University of Chicago lecture,
http://www.cs.uchicago.edu/~soare/Seminars/Seminar.html
and Nabutovsky in his proof of the theorem [1996d], and all other
references I know have clearly identified this as "Gromov's Theorem."
See also a statement of Gromov's Theorem as Theorem 5.1 p. 12 line -2
of Nabutovsky Weinberger Fractal.ps in:
http://www.cs.uchicago.edu/~soare/Geometry/fractal.ps
where you can check it on line. Notice the attribution to Gromov [0],
his 1981 Annals of Math Studies reference.
Stephen Simpson 16 June 2000 wrote:
> However, the statement seems to be running the wrong way. Shouldn't "only
> finitely many" be replaced by "infinitely many"? This way it seems to
> make a lot more sense.
If we take the contrapositive as Matt Frank suggests, then "finitely
many" is correct.
------------------------------------------------------------------------------
2. TWO COMPUTABILITY THEORY RESULTS:
Matthew Frank Sun, 11 Jun 2000 10:11:16 -0500 (CDT) wrote:
> Only when I got the abstract for Soare's talk did I learn that Nabutovsky
> and Weinberger had needed some new results in computability (which Soare
> then provided) for their proofs. This convinces me (as I had not been
> convinced before) that there will be a fruitful interaction between the
> two fields of Soare's talk.
Stephen Simpson 16 June 2000 wrote:
> Ummm, well, .... My understanding of it (I have been reading up on
> the Nabutovsky/Weinberger stuff) is that Nabutovsky and Weinberger
> originally cited an old theorem about r.e. degrees, the Sacks Density
> Theorem. But then, after discussing the matter with Soare, they found
> that they could get a slightly better geometrical result by applying a
> much easier, tailor-made theorem about r.e. sets, which Soare
> provided. The easier theorem, due to Soare (see also Soare's ASL 2000
> abstract), is that there exists a sequence of r.e. sets such that any
> settling-down function for any one of the sets in the sequence
> dominates any recursive function composed with any settling-down
> function for the next set in the sequence.
The Sacks Density Theorem is not necessary here, and indeed its proof
is somewhat misleading for the theorem needed. It is well known and
easy to prove by any of a variety of methods (including several finite
injury priority arguments) that there is an infinite descending chain
of computably enumerable (c.e.) degrees. (This was probably already
known to Friedberg and Muchnik.) From this immediately follows:
THEOREM 1. There is a sequence of c.e. sets A_i, i \in \omega such that
(1) (there are infinitely many x)[M(i,i+1,x)]
where M(i,i+1,x) expresses that the settling function for A_i
dominates that for A_{i+1} even when the latter is composed
with any computable function.
Although they were aware of Theorem 1, they found that it did not
prove the geometry results they wanted, so they asked Soare to prove a
much stronger result (which required a different approach.). Soare
proved,
THEOREM 2 (Soare). There is a sequence of c.e. sets A_i, i \in \omega
such that
(1) (\exists y)(\forall x > y)[M(i,i+1,x)]
where M is as above. The difference between (2) and (1) is exactly the
quantifier:
"for almost every x" in (2), versus "there exist infinitely many x" in (1).
Theorem 2 is proved and used in a much stronger form Theorem 2' which
is independent of any enumerations for A_i and A_{i+1}, and where
we control the set of i such that deg(A_i) > deg(A_{i+1}).
The proof uses a priority argument.
-----------------------------------------------------------------------------
3. THE GEOMETRICAL SIGNIFICANCE.
The geometers explain it this way. The depths of basins on a certain
topological space correspond to halting times of Turing machines which
recognize certain c.e. sets. Weinberger explained that if he wants to
compare two depths, say a and b, he might tell an audience of
topologists that,
a > exp(b)
where exp(x) denotes 10 to the power x. If so, the audience will think
that it comes from Smith's theorem, where "Smith" is some well-known
topologist.
If Weinberger continues that,
a> exp(exp(b))
then the audience will think of Jones theorem, where "Jones" is another
topologist.
But if he says that
a> exp(exp(exp(exp(exp(b)))))
the topologists will be bewildered, not having any topology theorem to fall
back on.
Computability Theory can give such a bound, providing we are looking
at *sequences* of large depths {a(i): i \in omega} and small depths
{b(i): b \in \omega} and providing that we can show,
(3) (for almost every i) (\forall computable f)[a(i) > f(b(i)) ],
namely that the smaller quantity, b(i), remains smaller than a(i),
even when composed with an arbitrary computable function, such as the
exp function iterated as many times as you like. This is exactly what
the geometers wanted and gives a beautiful application of
computability theory to geometry.
Stephen Simpson 16 June 2000 wrote:
> Ummm, well, .... My understanding of it (I have been reading up on
> the Nabutovsky/Weinberger stuff) is that Nabutovsky and Weinberger
> originally cited an old theorem about r.e. degrees, the Sacks Density
> Theorem. But then, after discussing the matter with Soare, they found
> that they could get a slightly better geometrical result by applying a
> much easier, tailor-made theorem about r.e. sets, which Soare
> provided. The easier theorem, due to Soare (see also Soare's ASL 2000
> abstract), is that there exists a sequence of r.e. sets such that any
> settling-down function for any one of the sets in the sequence
> dominates any recursive function composed with any settling-down
> function for the next set in the sequence.
Not exactly.
>the Sacks Density Theorem
The Sacks Density Theorem is unnecessary here. The Theorem 1 can
be done as an exercise in a computability theory course using a
finite injury method to get the chain of c.e. degrees from which
Theorem 1 immediately follows. [Use the methods of Chapter 7 of
[Soare, 1987], the Springer-Verlag book on Computability Theory.]
Stephen Simpson 16 June 2000 wrote:
> But then, after discussing the matter with Soare, they found
> that they could get a slightly better geometrical result by applying a
> much easier, tailor-made theorem about r.e. sets, which Soare
> provided.
Weinberger came to Soare in February of 1999 in search of Theorem 2.
Notice that the comparison of depths of basins requires "almost all x"
not "infinitely many x" since the latter does not have the important
geometric significance he wanted as explained above. The new result
(Theorem 2 above) was not a slight improvement on a previous result
(Theorem 1); it was the theorem they were looking for. He also wanted
certain additional properties such as independence of enumeration, and
he has stressed Turing degrees of the sets in the sequence.
------------------------------------------------------------------------
4. ECLECTIC NW AUTHORS:
The computability result here, Theorem 2', plays an essential role in
the proof of the Nabutovsky-Weinberger (NW) result. However, there
are many other essential parts:
-Homology spheres and the Novikov Theorem on the undecidability of the
problem of recognizing the sphere;
-The Gromov-Hausdoff metric and its key properties;
-Combinatorial Group Theory and Higman Neumann Neumann extensions;
-The Gromov-Cheeger compactness for Riem(M) and the NW counterpart,
where M is a smooth compact manifold of dimension > 4 and
curvature |K| < 1;
-The connected sum of two smooth manifolds, the Generalized Poincare
Conjecture, and Smale's Theorem;
-Results in algebraic topology;
-Results in differential geometry;
-Other items.
For more information and definitions, see the NW fractal paper:
http://www.cs.uchicago.edu/~soare/html/Geometry/fractral.ps
It is the remarkable achievement of Nabutovsky and Weinberger that
they were able to recognize, modify, and synthesize such diverse parts
into a theorem like theirs. It is not unusual for such diverse
mathematical elements to play an essential role in a proof in
differential geometry, but it is more unusual for Computability Theory
to do so.
The authors Nabutovsky and Weinberger immediately recognized the value
of the ordering in Soare's Theorem 2' which had been written "A >> B."
> From alex at math.toronto.edu Wed Nov 24 12:09:58 1999
> Date: Wed, 24 Nov 1999 13:09:55 -0500 (EST)
> From: alex at math.toronto.edu (Alex Nabutovsky)
> To: alex at math.toronto.edu, soare at cs.uchicago.edu
>
> Dear Bob,
> ...
>
> I think that your result about the existence of an infinite chain of
> c.e. degrees with respect to relation >> is quite fundamental on
> its own. Here is why. For a non-logician the busy beaver function is
> the most natural and easiest to understand manifestation of
> non-computability. So, it is quite natural for a non-logician
> to think about c.e. degrees in terms of their computation (=busy beaver)
> functions.
> ...
> Our work implies that the relation << can be distinctively ``seen"
> when one looks on graphs of some Riemannian functionals: One
> gets a comparatively evenly spaced basins corresponding to a larger
> degree and inside every such basin shallower and also more or less
> evenly spaced basins of depth comparable with the computation
> function of a smaller degree.
> ...
-------------------------------------------------------------------------
5. NEW FRONTIERS
An exciting aspect of the NW results is that they open new area of
interaction between Computability Theory and Differential Geometry,
and new questions.
> Date: Mon, 13 Sep 1999 19:07:24 -0400 (EDT)
> From: alex at math.toronto.edu (Alex Nabutovsky)
> To: soare at cs.uchicago.edu, alex at math.toronto.edu
>
> Dear Bob,
>
> I looked over your book ``Recursively enumerable sets and degrees"
> and liked it very much. A very significant part of the theory
> of c.e. degrees ``immerses"
> into the geometry of (graphs of functionals on) spaces of Riemannian
> structures and related spaces (i.e. space of triangulations, space
> of hyperspheres, spaces of multidimensional knots, etc.)
>
> The most simple explanation of why does this happen is the following.
> In many branches of mathematics one deals with the fact that an object
> has many ``implicit descriptions" or ``implicit representations". The
> primary examples are descriptions of a computable function by different
Turing
> machines which compute it (or even of a number by a Turing machine
> and its input such that the number is the result of the corresponding
> computation); finite representations of a group; triangulations of a fixed
> manifold. The spaces of implicit representations of a fixed
> object are often logically complicated. For finite representations
> of a fixed group (for example, trivial group) this follows from the
> algorithmic unsolvability of the triviality problem for finitely presented
> groups.
-------------------------------------------------------------------------
6. PROOF METHODS.
6 A. COMMENT BY OTHERS ON THE PROOFS:
----------------------------------------
> Stephen Simpson 16 June 2000 wrote:
>
> This theorem of Soare is much easier because, according to some
> recursion theorists that I asked at ASL 2000, the proof does not need
> a priority argument.
The proof of Theorem 2' is *not* easier that that of Theorem 1 and is
in fact more difficult as explained above.
> Stephen Simpson 16 June 2000 wrote:
>
> Another vindication of the so-called Simpson's
> Thesis! [ This is a reference to the discussion of the role of
> priority arguments in applied recursion theory, FOM,
> July/August/September 1999. See for instance my posting of Wed, 4 Aug
> 1999 19:18:00 -0400 (EDT). ]
This is completely incorrect on all counts. See comments below.
---------------------------------------------------------------------------
> Peter Cholak 28 June 2000 wrote:
>
> N/W first used the Sacks Density Thm for their results. Then they
> (actually just W) came to Soare and asked Soare to provide them with a
> "tailor-made" theorem. This "tailor-made" result does provide N/W with a
> "better" result. I cannot judge how much better. But I would not use the
> word "slightly" since N/W asked for and were interested in Soare's result.
>
> Soare told me last spring the proof of his theorem was "easy". Today I
> sat down and thought about the proof. The proof I came up with was a
> priority argument done on a tree with Pi^0_2 branching nodes. It is a
> 0''-priority argument. I see no way this can be improved to a 0'-priority
> argument (finite injury). Sacks density is also a 0''-priority argument.
> I would say that Soare's proof is only slightly easier than the tree proof
> of Sacks density since what has to be done is more transparent. But I
> think only someone with a good working knowledge of the tree method could
> call this proof easy.
>
> I am not going to enter another debate about the "Simpson's thesis" (for
> those interested I suggest looking at the FOM archives.) But Soare's
> result does not support the "Simpson's thesis".
--------------------------------------------------------------------------
6 B. COMPARING METHODS:
It is amusing that so many people are so knowledgable about Soare's
proof because no one besides Soare has ever seen the proof (even in
outline form). There are actually several variations of the main
Soare Theorem 2' depending upon how closely you wish to control the
Turing degrees of the sets being constructed and other properties.
Soare Theorem 2' *definitely USES a priority method.* Thus, Cholak
is right above, and Simpson is wrong.
It is completely misleading, however, to judge the interest or
difficulty of a proof by the use or avoidance of the priority method.
Lachlan, the master of priority arguments, and inventor or the most
difficult ones, used nonpriority arguments of the greatest complexity,
subtlety, and elegance to prove some of the deepest and most appealing
resultsin the field. Most computability theorists would regard it as
a irrelevant whether a proof uses or does not use a particular method,
such as forcing, diagonal methods of Kleene-Post, priority methods,
the Kleene recursion theorem, etc.
As Nabutovsky relates above, a large part of the computability theory
"embeds" in differential geometry. I am now working on other results
with a graduate student on computability results with geometric
significance. Like Nabutovsky and Weinberger, we intend to be
eclectic and to use whatever methods work best.
-----------------------------------------------------------------------------
6 C. DEMONSTRATING SIMPSON'S THESIS.
> Stephen Simpson 16 June 2000 wrote:
>
> Another vindication of the so-called Simpson's
> Thesis! [ This is a reference to the discussion of the role of
> priority arguments in applied recursion theory, FOM,
> July/August/September 1999. See for instance my posting of Wed, 4 Aug
> 1999 19:18:00 -0400 (EDT). ]
"Simpson's Thesis," introduced by Simpson (FOM, 21 Jun 1999 21:36:37)
and restated by him (FOM 22 July, 1999) states that:
``priority methods are almost completely absent from applied
recursion theory.''
------------------------------------------------------------------------
GREAT THESES OF COMPUTABILITY THEORY
The great theses of Computability Theory like Turing's Thesis or
Church's Thesis are philosophical assertions requiring a philosphical
demonstration. Martin Davis, in a lovely paper (Information and
Control, 1982) explains why Godel was not convinced by Church's
argument for his thesis. Wilfried Sieg (Mechanical procedures and
mathematical experience, In: A. George (ed.), {\em Mathematics and
Mind}, Oxford Univ.\ Press, 1994.) gives a superb explanation of why
Turing's argument was convincing (and in particular to Godel, although
Sieg does not mention Godel).
Simpson's Thesis is of a completely *different* kind. It is not a
philosophical assertion but merely a claim that there are few
occurences of a certain method in a certain category of papers. This
claim can be completely settled one way or the other by simply
carefully examining each such paper, classifying it by title and
author, and determining whether or not it uses the method in question.
(There are at least several hundred papers many of which were
mentioned by researchers last year.) When all this data has been
assembled, by whomever wishes to assert or refute the thesis, then he
can present the data and we can discuss it. Before then, discussing
this claim is pure speculation without evidence. In particular, any
single new case (or even handful of cases) which either use, or do not
use, the method is no more evidence for or against the claim than the
temperature on a given day is evidence for or against global warming
over several decades. Once the researcher had gathered all this data
we could count the number of occurrences and see whether it was almost
none, few, many, or most.
Simpson's Thesis was introduced on FOM in June and July, 1999. A list
of at least 200 counterexamples was compiled by several dozen scholars
and posted on a web page cited in a FOM posting by Soare in July,
1999. Simpson challenged two of these, but that leaves approximately
200 still left, and dozens of new counter-examples have since been
supplied by Nerode, some relating to the book by Nerode, Ershov,
Goncharov, and Remmel on Recursive Mathematics.
Once we receive the full analysis from any claimant on the many
hundreds of applications, whether they contain the priority method or
not, we can turn to the real question:
Why should anyone care about Simpson's Thesis?
What mathematical information does it give? How does it help produce
new mathematics. Until these questions are answered, I believe it is
not worthwhile to discuss the details of Simpson's Thesis. I am not
going to use the fact that the latest computably-geometry *uses* a
priority argument to refute Simpson's Thesis. It is simply one more
day's temperature report in a Thesis which looks at global warming
over a decade. I am waiting for someone to analyze the data for every
day for a decade (i.e. every applied computability paper written).
-------------------------------------------------------------------------------
7. FURTHER LECTURES.
I am now working in some further open questions in this area with one
of my graduate students. I have temporarily withdrawn the Urbana ASL
slides from my web page because the html copies are missing the
diagrams and the accompanying text without which the meanings are not
clear, and because I am now improving them for future lectures:
Aug. 31 Notre Dame University
Sep. 14 Carnegie Mellon University
If anyone wants to hear the whole lecture with improved slides, he is welcome
to attend.
Information may be found on the web page:
http://www.cs.uchicago.edu/~soare/Geometry/
I will supply more information on an individual basis as needed.
============================================================================
Professor Robert Soare Phone:(773) 702-6029, Secty: 702-7100
Department of Mathematics /(or: CS) FAX: (773) 702-9787
The University of Chicago e-mail: soare at cs.uchicago.edu
5734 University Avenue WWW: http://www.cs.uchicago.edu/~soare
Chicago, IL 60637-1546
Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
martin at eipye.com
(Add 1 and get 0)
http://www.eipye.com
More information about the FOM
mailing list