Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- Some results on ℝ-computable structures
- Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
- Computable structure theory using admissible recursion theory on ω1 using admissibility
- Local computability and uncountable structures
- Borel structures: a brief survey
- E-recursive intuitions
- Reverse mathematics, countable and uncountable: a computational approach
- Effective model theory: approach via σ-definability
- References
Some results on ℝ-computable structures
Published online by Cambridge University Press: 05 December 2013
Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- Some results on ℝ-computable structures
- Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
- Computable structure theory using admissible recursion theory on ω1 using admissibility
- Local computability and uncountable structures
- Borel structures: a brief survey
- E-recursive intuitions
- Reverse mathematics, countable and uncountable: a computational approach
- Effective model theory: approach via σ-definability
- References
Summary
§1. Introduction. The theory of effectiveness properties on countable structures whose atomic diagrams are Turing computable is well-studied (see, for instance, [1, 15]). Typical results describe which structures in various classes are computable (or have isomorphic copies that are) [19], or the potential degree of unsolvability of various definable subsets of the structure [16]. The goal of the present paper is to survey some initial results investigating similar concerns on structures which are effective in a different sense.
A rather severe limitation of the Turing model of computability is its traditional restriction to the countable. Of course, many successful generalizations have been made (see, for instance, [28, 12, 13, 23, 24, 26] and the other chapters in the present volume). The generalization that will be treated here is based on the observation that while there is obviously no Turing machine for addition and multiplication of real numbers, there is strong intuition that these operations are “computable.” The BSS model of computation, first introduced in [5], approximately takes this to be the definition of computation on a given ring (a more formal definition is forthcoming). This allows several problems of computation in numerical analysis and continuous geometry to be treated rigorously. The monograph [4] gives the examples of the “decision problem” of the points for which Newton's method will converge to a root, and determining whether a given point is in the Mandelbrot set.
Information
- Type
- Chapter
- Information
- Effective Mathematics of the Uncountable , pp. 14 - 32Publisher: Cambridge University PressPrint publication year: 2013
References
[1] and , Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, Elsevier, 2000.
[2] , Priority method in generalized computation. In Recursion Theory and Complexity: Proceedings of the Kazan ′97 Workshop, de Gruyter, 1999, 1–13.
[3] , Admissible Sets and Structures: an Approach to Definability Theory,Springer, 1975.
[4] , , , and , Complexity and Real Computation, Springer, 1997.
[5] , , and , On a theory of computation and complexity over the real numbers, Bulletin of the American Mathematical Society (New Series) 21 (1989), 1–16.Google Scholar
[7] , On three notions of effective computation over ℝ, preprint, 2009.
[8] , , , and , Comparing classes of finite structures, Algebra and Logic 43 (2004), 374–392.Google Scholar
[9] and , Real computable manifolds and homotopy groups. In Unconventional Computation 2009, Lecture Notes in Computer Science, no. 5715, Springer, 2009, 98–109.
[10] , The arithmetical hierarchy over the reals, Journal of Logic and Computation 2 (1992), 375–395.Google Scholar
[11] , Определимость и Вичислимость, Сибирская Школа Алгебры и Логики, Научная Книга, 1996.
[12] and (editors), Generalized Recursion Theory, Studies in Logic and the Foundations of Mathematics, no. 79, North-Holland, 1974.
[13] , , and (editors), Generalized Recursion Theory ii, Studies in Logic and the Foundations of Mathematics, no. 94, North-Holland, 1978.
[14] and , A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic 54 (1989), 894–914.Google Scholar
[15] , Pure computable model theory. In Handbook of Recursive Mathematics, vol. 1, Studies in Logic and the Foundations of Mathematics, no. 138, North-Holland, 1998, 3–114.
[16] , Turing degrees of certain isomorphic images of computable relations, Annals of Pure and Applied Logic 93 (1998), 103–113.Google Scholar
[17] and , Analytic equivalence relations and Ulm-type classifications, Journal of Symbolic Logic 60 (1995), 1273–1300.Google Scholar
[18] , Classical Descriptive Set Theory, Graduate Texts in Mathematics, no. 156, Springer, 1995.
[19] , Constructive Abelian groups. In Handbook of Recursive Mathematics, vol. 2, Studies in Logic and the Foundations of Mathematics, no. 139, North-Holland, 1998, 1177–1231.
[21] , Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer, 1983.
[22] and , An explicit solution to Post's problem over the reals. In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 3623, Springer, 2005, 467–478.
[23] , Locally computable structures. Computation and Logic in the Real World, Lecture Notes in Computer Science, vol. 4497, Springer, 2007, 575–584.
[24] and , On Σ-definability of countable structures over real, complex numbers, and quaternions, Algebra and Logic 47 (2008), 193–209.Google Scholar
[25] , On elementary submodels of F-parameterizable models, Bulletin of Symbolic Logic 12 (2006), 146, Abstract of invited talk in 2005 Annual Meeting of the Association for Symbolic Logic, Stanford University, Stanford, California, March 19–22, 2005.Google Scholar
[26] , Элементарные подмодели параметризуемых моделеи, Сибирскии Математическии Журнал 47 (2006), 595–612.Google Scholar
[27] , Strong and weak constructivizations and computable families, Algebra and Logic 13 (1974), 177–184.Google Scholar
[28] , Higher Recursion Theory, Perspectives in Mathematical Logic, Springer, 1990.
[30] , (Short) survey of real hypercomputation. In Computation and Logic in the Real World, Lecture Notes in Computer Science, vol. 4497, Springer, 2007, 809–824.
Accessibility standard: Unknown
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.