G. Ramalingam
Theoretical Computer Science
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.
G. Ramalingam
Theoretical Computer Science
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
Pradip Bose
VTS 1998