Hostname: page-component-6bf8c574d5-2jptb Total loading time: 0 Render date: 2025-02-21T05:58:47.985Z Has data issue: false hasContentIssue false
  • English
  • Français

Construction of models for algebraically generalized recursive function theory

Published online by Cambridge University Press:  12 March 2014

H. R. Strong
Get access Rights & Permissions [Opens in a new window]

Abstract

The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter (“successor set”) is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 35 , Issue 3 , September 1970 , pp. 401 - 409
Copyright
Copyright © Association for Symbolic Logic 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[FO]Friedman, H. M., private communication.Google Scholar
[FI]Friedman, H. M., Axiomatic recursive function theory, Stanford University (not yet published).CrossRefGoogle Scholar
[H]Halmos, P. R., Lectures on Boolean algebras, Van Nostrand, Princeton, 1963.Google Scholar
[S0]Strong, H. R. Jr., An algebraic approach through uniformly reflexive structures to generalized recursive function theory, Doctoral dissertation, University of Washington, 1967.Google Scholar
[S1]Strong, H. R. Jr., Algebraically generalized recursive function theory, IBM journal research and development, 12, 6, 465—475, November, 1968.CrossRefGoogle Scholar
[W0]Wagner, E. G., Uniformly reflexive structures: Towards an abstract theory of computability, Research report RC-934, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1963. (Doctoral dissertation, Columbia University, 1963.)Google Scholar
[W1]Wagner, E. G., Uniformly reflexive structures: An axiomatic approach to computability, Logic, Computability, and Automata: Joint RADC-HAC Symposium, 1965. Trinkaus Manor, Oriskany, New York (to be published).Google Scholar
[W2]Wagner, E. G., Uniformly reflexive structures: On the nature of Gödelization and relative computability, Transactions of the American Mathematical Society, 144 (1969), pp. 1–41.Google Scholar