"Computability Theory and Differential Geometry"

Abstract: In their preprint, {\em The Fractal Nature of Reim/Diff}, the authors 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 Reim(M), for $M$ a smooth, compact manifold of dimension $\geq 4$ and curvature $|k| \leq 1$.) Part of this richness is due to the connection of computability, and in particular of computably enumerable (c.e.) sets, to the geometry, as we will explain in this talk. Using a wide variety of mathematics, the authors prove roughly that for any c.e.\ set $A$ (one recognized by a Turing machine) there is a sequence of manifolds $\Gamma_n$ such that $n\in A$ iff $\Gamma_n$ determines a local minimum and the depth of the local mimimum is roughly equal to the halting time of the Turing machine. Combining this with a result of Soare about the existence of a sequence of c.e.\ sets $\{A_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 {\em complexity} of the geometry, whereas most other applications of c.e.\ sets, such at Hilbert's tenth problem and the word problem for groups, have only been about undecidability; and (2) they use nontrivial facts about c.e.\ sets, while most other results use only the existence of a noncomputable c.e.\ set like $K$ known in the 1930's.
 

Back to Talks Page