Computability over arbitrary fields
Pages 149 - 153
Abstract
In most attempts to make precise the concept of a computable function, or decidable predicate, over a field F, it is considered necessary that the elements of F should be in some sense effectively describable, and hence that F itself should be countable. This is the attitude taken in the study of computable fields (see Rabin1).
Our proposed definition of computability over arbitrary fields is based on the Shepherdson - Sturgis2 concept of an unlimited register machine.
References
[1]
Rabin, M.O. "Computable algebra, general theory and theory of computable fields", Trans. Amer. Math. Soc, 87, (1960), 341-360.
[2]
Shepherdson, J.C. & Sturgis, H.E. "Computability of recursive functions", J. Assoc. Comp. Mach., 10, (1963), 217-255.
[3]
Gallaire, H., Gray, J.N., Harrison, M.A. & Herman, G.T. "Infinite linear sequential machines", Journal of Computer and System Sciences, 2, (1968), 381-419.
[4]
Tarski, A. A decision method for elementary algebra and geometry, 2nd edition, Berkeley and Los Angeles, 1951, VI + 63 pp.
Index Terms
- Computability over arbitrary fields
Recommendations
Computability over an arbitrary structure: sequential and parallel polynomial time
FOSSACS'03/ETAPS'03: Proceedings of the 6th International conference on Foundations of Software Science and Computation Structures and joint European conference on Theory and practice of softwareWe provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 1969
267 pages
ISBN:9781450374781
DOI:10.1145/800169
Copyright © 1969 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 May 1969
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 242Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)5
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in