Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-22T21:10:40.656Z Has data issue: false hasContentIssue false
  • English
  • Français

Computability Results Used in Differential Geometry

Published online by Cambridge University Press:  12 March 2014

Barbara F. Csima  and
Robert I. Soare
Barbara F. Csima
Affiliation:
Department of Pure Mathematics, University of Waterloo, 200 University Ave. W. Waterloo, ON. N2L 3G1.Canada, E-mail: [email protected], URL: http://www.math.uwaterloo.ca/~csima
Robert I. Soare
Affiliation:
Department of Mathematics, University Of Chicago, Chicago, Illinois 60637-1546. USA, E-mail: [email protected] URL: http://www.people.cs.uchicago.edu/~soare/
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 71 , Issue 4 , December 2006 , pp. 1394 - 1410
Copyright
Copyright © Association for Symbolic Logic 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Barmpalias, G. and Lewis, E. M., The ibT degrees of computably enumerable sets are not dense, Annals of Pure and Applied Logic, vol. 141 (2006), pp. 51–60.CrossRefGoogle Scholar
[2]Barmpalias, G. and Lewis, E. M., Randomness and the Lipschitz degrees of computability, to appear.Google Scholar
[3]Cooper, S. B., Computablility theory, Chapman & Hall/CRC Mathematics, London, New York, 2004.Google Scholar
[4]Csima, B. F., Applications of computability theory to prime models and differential geometry, Ph.D. thesis, The University of Chicago, 2003.Google Scholar
[5]Csima, B. F. and Shore, R. A., The settling-time reducihility ordering, to appear.Google Scholar
[6]Downey, R., Hirschfeldt, D., and LaForte, G., Randomness and reducibility, Mathematical foundations of computer science, MFCS 2001 (Sgall, J., Pultr, A., and Kolman, P., editors), Lecture Notes in Computer Science, vol. 2136, Springer, Berlin, 2001, pp. 316–327.CrossRefGoogle Scholar
[7]Downey, R., Hirschfeldt, D., and LaForte, G., Randomness and reducibility, Journal of Computer and System Sciences, vol. 68 (2004), pp. 96–114.CrossRefGoogle Scholar
[8]Nabutovsky, A. and Weinberger, S., Variational problems for Riemannian functionals and arithmetic groups, Publications Mathématiques, Institut des Hautes Études Scientifiques, vol. 92 (2000), pp. 5–62.Google Scholar
[9]Nabutovsky, A. and Weinberger, S., The fractal nature of Riem/Diff I, Geometrica Dedicata, vol. 101 (2003), pp. 1–54.CrossRefGoogle Scholar
[10]Soare, R. I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar
[11]Soare, R. I., Computability theory and differential geometry, The Bulletin of Symbolic Logic, vol. 10 (2004), pp. 457–486.CrossRefGoogle Scholar
[12]Soare, R. I., Computability theory and applications, Springer-Verlag, Heidelberg, to appear.Google Scholar
[13]Weinberger, S., Computers, rigidity, and moduli. The large-scale frcatal geometry of Riemannian moduli space, M. B. Porter Lectures, Princeton University Press, Princeton, NJ, 2005.CrossRefGoogle Scholar