No CrossRef data available.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 12 March 2014
Given a class U which is the result of closing a finite class of expressions with respect to a binary mode of combination, there exists, according to RFBL,1 a recursively enumerable subclass K* of U, and concepts of representation (5.3) and complete representation (6.2) such that:
(a) A relation among members of U is recursively enumerable if and only if it is represented in K*. (6.7.)
(b) A relation among members of U is recursive if and only if it is completely represented in K*. (6.10.)
1 Fitch, F. B., Recursive functions in basic logic, this Journal, vol. 21 (1956), pp. 337–346Google Scholar. Familiarity with the terminology of this paper is presupposed. For an alternative presentation of the same system, see Hermes, H., Enumerability, decidability, computability, Springer-Verlag, Berlin, 1965, pp. 219–231.CrossRefGoogle Scholar The research in the present paper was supported by NSF-GP-3899.
2 There is, however, a typographical error in line 4 of page 340. The symbol ‘φ’ should appear as part of a subscript expression ‘φ(x1, …, xn)’ to the left of and slightly below the symbol ‘a’, and should not appear, as it does, on the same level as ‘a’.