David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 71 (4):1394 - 1410 (2006)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Adam R. Day (2010). The Computable Lipschitz Degrees of Computably Enumerable Sets Are Not Dense. Annals of Pure and Applied Logic 161 (12):1588-1602.
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.
Added to index2010-08-24
Total downloads2 ( #385,036 of 1,413,179 )
Recent downloads (6 months)1 ( #153,719 of 1,413,179 )
How can I increase my downloads?