Prime and search computability, characterized as definability in certain sublanguages of constructible πΏ_{π}_{1,π}
Carl E. Gordon Β· Transactions of the American Mathematical Society Β· 1974
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.