Chicago Logic Seminar - Wednesday, 28 February

[Margery Ishmael]

UNIVERSITY OF CHICAGO LOGIC SEMINAR

WEB SITE:  for current information:
http//:www.cs.uchicago.edu/~soare/Seminars/
-----------------------------------------------------------------------------

DATE:  Wednesday, February 28, 2001.
TIME:  3:30-5:00
PLACE: Ryerson  251.

TITLE: Computability Theory and Differential Geometry

SPEAKER:  Robert Soare
	  The University of Chicago

PREREQUISITES: All concepts from differential geometry and
computability will be defined and explained.  No extensive knowledge
of either is necessary.

-----------------------------------------------------------------------------
ABSTRACT:

We trace the diverse mathematical traditions of Poincare (fundamental
groups) and Hilbert (the Entscheidungsproblem) to their unlikely
blending in the following results about computability and differential
geometry.

In their recent preprint, "The Fractal Nature of Riem/Diff,"
topologists Alex Nabutovsky and Shmuel Weinberger (NW), begin, ``In
this paper we would like to expose some of the astonishing richness of
the space of Riemannian metrics on a smooth manifold, up to
reparametrization.''  (This space is called Riem(M), for $M$ a smooth,
compact manifold of dimension $\geq 5$ and curvature $|k| \leq 1$.)
Part of this richness is due to the connection with computability, and
in particular with computably enumerable (c.e.) sets, as we will
explain in this talk.  Using a wide variety of mathematics, the
authors NW prove roughly that for any c.e. set A (i.e. one recognized
by a Turing machine) there is a sequence of manifolds (indeed
hypersurfaces) \Gamma_n such that n\in A iff \Gamma_n determines a
local minimum, and that the depth of the local minimum is roughly
equal to the halting time of the Turing machine.  Combining this with
a recent result of Soare about the existence of a sequence of c.e.
sets {A_n: n \in N} with certain properties on the halting times of
A_n relative to A_{n+1}, NW obtain unexpected results about the depth
and distribution of local minima and their fractal nature.

 From the point of view of computability and logic these results are
interesting because:

(1) They are about the mathematical *complexity* of the geometry,
whereas most other applications of c.e. sets, such as Hilbert's tenth
problem, or the word problem for groups, have only been about
*undecidability*, something not usually studied by the working
mathematician.

(2) They use nontrivial results about c.e. sets, like the Soare
sequence {A_n} above, while most other results use only the existence
of a noncomputable c.e. set like Godel's set K, a elementary fact
known in the 1930's.

(3) The only known method for obtaining these results is via logic and
computability.


Embedding Turing machines in a structure shows vast complexity.  Can
this be used elsewhere in geometry, topology, and algebra to obtain
new results about the natural complexity of the structure, as
regularly studied by mathematicians, and not merely its
undecidability, results not obtainable by the standard methods?
-- 
Margery Ishmael
Department of Computer Science
The University of Chicago
1100 E. 58th Street
Chicago, IL. 60637

Tel. 773-834-8977  Fax. 773-702-8487