Topologists Nabutovsky and Weinberger discovered how to embed
computably enumerable (c.e.) sets into the geometry of Riemannian
metrics modulo diffeomorphisms. They used the complexity of the
settling times of the c.e. sets to exhibit a much greater complexity
of the depth and density of local minima for the diameter function
than previously imagined. Their results depended on the existence of
certain sequences of c.e. sets, constructed at their request by Csima
and Soare, whose settling times had the necessary dominating
properties. Although these computability results had been announced
earlier, their proofs have been deferred until this paper.
¶
Computably enumerable sets have long been used to prove
undecidability of mathematical problems such as the word
problem for groups and Hilbert’s Tenth Problem. However, this example
by Nabutovsky and Weinberger is perhaps the first example of the use
of c.e. sets to demonstrate specific mathematical or geometric
complexity of a mathematical structure such as the depth and
distribution of local minima.