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.