About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Indexings of subrecursive classes
Abstract
A subrecursive indexing is a programming language or Gödel numbering for a class of total recursive functions. Several properties of subrecursive indexings, such as effective composition and generation of constant functions, are investigated from an axiomatic point of view. The result is a theory akin to the axiomatic treatment of recursive function theory of Strong and Wagner. Using this formalism, we prove results relating the complexity of uniform simulation, diagonalization, deciding membership, and deciding halting; we give a subrecursive analog of Rice's theorem; we give a characterization of the combinatorial power of subrecursive indexings analogous to the combinatorial completeness of the lambda calculus; finally, we give a characterization the power of diagonalization over subrecursive classes and show that if P≠NP is provable at all, then it is provable by diagonalization. © 1980, All rights reserved.