Computability Results Used in Differential Geometry

Journal of Symbolic Logic 71 (4):1394 - 1410 (2006)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 93,296

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computability theory and differential geometry.Robert I. Soare - 2004 - Bulletin of Symbolic Logic 10 (4):457-486.
The Settling-Time Reducibility Ordering.Barbara F. Csima & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (3):1055 - 1071.
Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
Bounded-low sets and the high/low hierarchy.Huishan Wu - 2020 - Archive for Mathematical Logic 59 (7-8):925-938.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
On supersets of non-low sets.Klaus Ambos-Spies, Rod G. Downey & Martin Monath - 2021 - Journal of Symbolic Logic 86 (3):1282-1292.
Orbits of computably enumerable sets: low sets can avoid an upper cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.


Added to PP

5 (#1,562,871)

6 months
76 (#69,901)

Historical graph of downloads
How can I increase my downloads?