{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:13:29Z","timestamp":1778901209174,"version":"3.51.4"},"reference-count":57,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":3332,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2004,12]]},"abstract":"<jats:p><jats:bold>Abstract<\/jats:bold>. Let<jats:italic>M<\/jats:italic>be a smooth, compact manifold of dimension<jats:italic>n<\/jats:italic>\u2265 5 and sectional curvature \u2223<jats:italic>K<\/jats:italic>\u2223 \u2264 1. Let Met(<jats:italic>M<\/jats:italic>) = Riem(<jats:italic>M<\/jats:italic>)\/Diff(<jats:italic>M<\/jats:italic>) be the space of Riemannian metrics on<jats:italic>M<\/jats:italic>modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met(<jats:italic>M<\/jats:italic>) such as the diameter. They showed that for every Turing machine<jats:italic>T<\/jats:italic><jats:sub><jats:italic>e<\/jats:italic><\/jats:sub>,<jats:italic>e<\/jats:italic>\u03f5 \u03c9, there is a sequence (uniformly effective in<jats:italic>e<\/jats:italic>) of homology<jats:italic>n<\/jats:italic>-spheres<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline1\"\/>which are also hypersurfaces, such that<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline2\"\/>is diffeomorphic to the standard<jats:italic>n<\/jats:italic>-sphere<jats:italic>S<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>(denoted<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline3\"\/>)iff<jats:italic>T<\/jats:italic><jats:sub><jats:italic>e<\/jats:italic><\/jats:sub>halts on input<jats:italic>k<\/jats:italic>, and in this case the connected sum<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline4\"\/>, so<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline5\"\/>, and<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600003589_inline6\"\/>is associated with a local minimum of the diameter function on Met(<jats:italic>M<\/jats:italic>) whose depth is roughly equal to the settling time ae \u03c3<jats:sub><jats:italic>e<\/jats:italic><\/jats:sub>(<jats:italic>k<\/jats:italic>)of<jats:italic>T<\/jats:italic><jats:sub><jats:italic>e<\/jats:italic><\/jats:sub>on inputs<jats:italic>y<\/jats:italic>&lt;<jats:italic>k<\/jats:italic>.<\/jats:p><jats:p>At their request Soare constructed a particular infinite sequence {<jats:italic>A<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>}<jats:sub>\u03f5\u03c9<\/jats:sub>of c.e. sets so that for all<jats:italic>i<\/jats:italic>the settling time of the associated Turing machine for<jats:italic>A<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>dominates that for<jats:italic>A<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic>+1<\/jats:sub>, even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a \u201cfractal\u201d like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as \u201cthe astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.\u201d From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural<jats:italic>complexity<\/jats:italic>of the geometry and topology, not merely<jats:italic>undecidability<\/jats:italic>results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use<jats:italic>nontrivial<\/jats:italic>information about c.e. sets, the Soare sequence {<jats:italic>A<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>}<jats:sub><jats:italic>i<\/jats:italic>\u03f5\u03c9<\/jats:sub>above, not merely G\u00f6del's c.e. noncomputable set K of the 1930's; and (3)<jats:italic>without<\/jats:italic>using computability theory there is no known proof that local minima exist even for simple manifolds like the torus<jats:italic>T<\/jats:italic><jats:sup>5<\/jats:sup>(see \u00a79.5).<\/jats:p>","DOI":"10.2178\/bsl\/1102083758","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T20:47:02Z","timestamp":1109796422000},"page":"457-486","source":"Crossref","is-referenced-by-count":29,"title":["Computability Theory and Differential Geometry"],"prefix":"10.1017","volume":"10","author":[{"given":"Robert I.","family":"Soare","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600003589_ref049","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4176-8"},{"key":"S1079898600003589_ref038","doi-asserted-by":"publisher","DOI":"10.1007\/BF02566428"},{"key":"S1079898600003589_ref044","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/054.3\/1216641"},{"key":"S1079898600003589_ref002","first-page":"13","article-title":"On algorithmic problems in effectively complete classes of groups","volume":"123","author":"Adjan","year":"1958","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S1079898600003589_ref032","volume-title":"Topology from a differential viewpoint","author":"Milnor","year":"1965"},{"key":"S1079898600003589_ref027","volume-title":"Algebraic topology: An introduction","author":"Massey","year":"1967"},{"key":"S1079898600003589_ref053","volume-title":"Calculus on manifolds","author":"Spivak","year":"1965"},{"key":"S1079898600003589_ref034","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160480402"},{"key":"S1079898600003589_ref039","first-page":"145","volume-title":"Rothenberg Festschrift","volume":"231","author":"Nabutovsky","year":"1999"},{"key":"S1079898600003589_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71911-6"},{"key":"S1079898600003589_ref013","unstructured":"Csima B. F. [2003], Computable model theory, Ph.D. thesis , The University of Chicago."},{"key":"S1079898600003589_ref011","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"S1079898600003589_ref051","doi-asserted-by":"publisher","DOI":"10.2307\/1970239"},{"key":"S1079898600003589_ref029","first-page":"1","volume-title":"Combinatorial grouptheory","author":"Miller","year":"1989"},{"key":"S1079898600003589_ref021","volume-title":"Differential topology","author":"Guillemin","year":"1974"},{"key":"S1079898600003589_ref031","doi-asserted-by":"publisher","DOI":"10.1515\/9781400878055"},{"key":"S1079898600003589_ref033","doi-asserted-by":"publisher","DOI":"10.1007\/BF01928216"},{"key":"S1079898600003589_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2201-7"},{"key":"S1079898600003589_ref043","volume-title":"Trudy Matematicheskogo Instituta Imeni V. A. Steklova, 44 Izdat Akad. Nauk SSSR, Moscow","author":"Novikov","year":"1955"},{"key":"S1079898600003589_ref047","doi-asserted-by":"publisher","DOI":"10.2307\/1969933"},{"key":"S1079898600003589_ref007","volume-title":"Contributions to mathematical logic","author":"Boone","year":"1968"},{"key":"S1079898600003589_ref050","doi-asserted-by":"publisher","DOI":"10.2307\/3597195"},{"key":"S1079898600003589_ref012","first-page":"109","volume-title":"Geometric Algebrique Reelle et formes quadratiques, Journees S.M.F. Universite de Rennes","author":"Coste","year":"1982"},{"key":"S1079898600003589_ref016","doi-asserted-by":"publisher","DOI":"10.2307\/2318447"},{"key":"S1079898600003589_ref055","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1960-10511-3"},{"key":"S1079898600003589_ref048","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-28615-9"},{"key":"S1079898600003589_ref042","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026358815492"},{"key":"S1079898600003589_ref001","first-page":"533","article-title":"The algorithmic unsolvability of checking certain properties of groups","volume":"103","author":"Adjan","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S1079898600003589_ref010","doi-asserted-by":"publisher","DOI":"10.2307\/2373498"},{"key":"S1079898600003589_ref015","volume-title":"The undecidable","author":"Davis","year":"1965"},{"key":"S1079898600003589_ref023","doi-asserted-by":"publisher","DOI":"10.2307\/1970128"},{"key":"S1079898600003589_ref008","doi-asserted-by":"publisher","DOI":"10.2307\/1970200"},{"key":"S1079898600003589_ref020","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1515\/9781400881550-016","volume-title":"Riemannian surfaces and related topics","volume":"97","author":"Gromov","year":"1981"},{"key":"S1079898600003589_ref045","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6434-5"},{"key":"S1079898600003589_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/BF02247118"},{"key":"S1079898600003589_ref040","first-page":"5","article-title":"Critical points of Riemannian functionals and arithmetic groups","volume":"92","author":"Nabutovsky","year":"2000","journal-title":"Publications Math\u00e9matiques. Institut de Hautes \u00cbtudes Scientifiques"},{"key":"S1079898600003589_ref017","volume-title":"Foundations of modern analysis","author":"Dieudonn\u00e9","year":"1960"},{"key":"S1079898600003589_ref056","first-page":"230","volume":"42","author":"Turing","journal-title":"Proceedings ofthe London Mathematical Society"},{"key":"S1079898600003589_ref052","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600003589_ref046","first-page":"1","volume-title":"Journal de l'\u00cacole Polytechnique, Paris (2)","volume":"1","author":"Poincar\u00e9","year":"1895"},{"key":"S1079898600003589_ref028","volume-title":"On group-theoretic decision problems and their classification","volume":"68","author":"Miller","year":"1971"},{"key":"S1079898600003589_ref019","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214437136"},{"key":"S1079898600003589_ref054","volume-title":"A comprehensive introduction to differential geometry","volume":"I\u2013V","author":"Spivak","year":"1979"},{"key":"S1079898600003589_ref036","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0312(199612)49:12<1257::AID-CPA1>3.0.CO;2-9"},{"key":"S1079898600003589_ref004","first-page":"227","article-title":"Certain simple unsolvable problems of group theory","volume":"19","author":"Boone","year":"1957","journal-title":"Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae"},{"key":"S1079898600003589_ref005","doi-asserted-by":"publisher","DOI":"10.2307\/1970103"},{"key":"S1079898600003589_ref037","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101007"},{"key":"S1079898600003589_ref030","doi-asserted-by":"crossref","DOI":"10.1515\/9781400881802","volume-title":"Morse theory","author":"Milnor","year":"1963"},{"key":"S1079898600003589_ref057","volume-title":"Computers, rigidity, and moduli: Computation and the large scale geometry of moduli spaces","author":"Weinberger"},{"key":"S1079898600003589_ref014","unstructured":"Csima B. F. and Soare R. I. [to appear], Applications of computability to differential geometry."},{"key":"S1079898600003589_ref026","first-page":"300","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Markov","year":"1958"},{"key":"S1079898600003589_ref025","first-page":"953","article-title":"Impossibility of algorithms for recognizing some properties of associative systems","volume":"77","author":"Markov","year":"1951","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S1079898600003589_ref006","doi-asserted-by":"publisher","DOI":"10.2307\/1970530"},{"key":"S1079898600003589_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0074439"},{"key":"S1079898600003589_ref009","volume-title":"Riemannian geometry\u2014A modern introduction","author":"Chavel","year":"1993"},{"key":"S1079898600003589_ref003","volume-title":"Geometrie alg\u00e9brique r\u00e9ele","author":"Bochnak","year":"1987"},{"key":"S1079898600003589_ref041","first-page":"5","article-title":"Variational problems for Riemannian functionals and arithmetic groups","volume":"92","author":"Nabutovsky","year":"2000","journal-title":"Publications Math\u00e9matiques, Institut des Hautes \u00c9tudes Scientifiques"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600003589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T02:27:10Z","timestamp":1586140030000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600003589\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12]]}},"alternative-id":["S1079898600003589"],"URL":"https:\/\/doi.org\/10.2178\/bsl\/1102083758","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12]]}}}