Journal of Symbolic Logic 71 (4):1394 - 1410 (2006)
|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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Robert I. Soare (2004). Computability Theory and Differential Geometry. Bulletin of Symbolic Logic 10 (4):457-486.
Leo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
Leo Harrington & Robert I. Soare (1996). Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets. Bulletin of Symbolic Logic 2 (2):199-213.
Kevin Wald (2002). On Orbits of Prompt and Low Computably Enumerable Sets. Journal of Symbolic Logic 67 (2):649-678.
Michael A. Jahn (1999). Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets. Journal of Symbolic Logic 64 (3):1037-1064.
John L. Bell, Two Approaches to Modelling the Universe: Synthetic Differential Geometry and Frame-Valued Sets.
John P. Burgess (1988). Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
E. Börger (1989). Computability, Complexity, Logic. New York, N.Y., U.S.A.Elsevier Science Pub. Co..
Piergiorgio Odifreddi (1989). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) (1996). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press.
Roland SH Omanadze (2004). Splittings of Effectively Speedable Sets and Effectively Levelable Sets. Journal of Symbolic Logic 69 (1):143-158.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
Sorry, there are not enough data points to plot this chart.
Added to index2010-08-24
Total downloads1 ( #290,877 of 722,698 )
Recent downloads (6 months)1 ( #60,006 of 722,698 )
How can I increase my downloads?