IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Search/Index  
    Orders  
    Description  
    Patents  
    Recent publications  
    Author's Guide  
  Staff  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 12, Number 6, Page 465 (1968)
Nontopical Issue
  Full article: arrowPDF   arrowCopyright info





   

Algebraically Generalized Recursive Function Theory

by H. R. Strong
The Uniformly Reflexive Structure (URS) introduced by E. G. Wagner is, for this paper, a nonassociative algebra consisting of a domain and a binary operation satisfying the following axioms:

0. (∃ *) (∀ a) [ a • * = * • a = * ];
1. (∃ ψ) (∀ a,b,c,d) × [ψ ≠ * & ((a ≠ * & b ≠ * & c ≠ * & d ≠ *) →
((a = d & (((ψ • a) • b) • c) • d = b) or
(a ≠ d & (((ψ • a) • b) • c) • d = c))) ] ; and
2. (∃ α)(∀ b,c,d) [α ≠ ψ & ((b ≠ * & c ≠ * & d ≠ *) →
((α • b) • c ≠ * & ((α • b) • c) • d = (b • d) • (c • d))) ] .

Wagner showed that these structures generalize much of Recursive Function Theory (RFT).

In this paper the functions “computed” by a URS are the functions given by left multiplications by elements of the URS. A family of functions is said to form a URS if it is the family of left multiplications of some URS. Axioms for Basic Recursive Function Theory are given characterizing those families of functions which form URS’s. The Partial Metarecursive Functions and the Computable Functionals of McCarthy are shown to form URS’s.

An investigation of notions analogous to the “recursively enumerable” notion in RFT shows that if any splinter (“successor set”) of a URS is semicomputable, then all are. A partial analogue to the Rice–Myhill–Shapiro Theorem is proved for URS’s satisfying an axiom corresponding to Kleene’s “indefinite description.” Finally, a study of pairing functions leads to work analogous to Rogers’ on Gödel numberings and generalizes similar work of Wagner.

Related Subjects: Mathematics