Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Prime and search computability, characterized as definability in certain sublanguages of constructible $ L\sb{\omega }{}\sb{1,\omega }$

Author: Carl E. Gordon
Journal: Trans. Amer. Math. Soc. 197 (1974), 391-407
MSC: Primary 02F27; Secondary 02B25
MathSciNet review: 0416882
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The prime computable (respectively, search computable) relations of an arbitrary mathematical structure are shown to be those relations R such that both R and its complement are definable by disjunctions of recursively enumerable sets of quantifier free (respectively, existential) formulas of the first order language for the structure. The prime and search computable functions are also characterized in terms of recursive sequences of terms and formulas of this language.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F27, 02B25

Retrieve articles in all journals with MSC: 02F27, 02B25

Additional Information

Keywords: Primitive computable, prime computable, search computable, infinitary language
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society