Subrecursive Programming Languages Part I: Efficiency and Program Structure

ABSTRACT. The structural complexity of programming languages, and therefore of programs as well, can be measured by the subrecursive class of functions which characterize the language. Using such a measure of structural complexity, we examine the trade-off relationship between structural and computational complexity. Since measures of structural complexity directly related to high level languages interest us most, we use abstract language models which approximate highly structured languages like Algol. KEY WORDS AND PHRASES: programming languages, universal machine, computational com-plexity, complexity class, subrecursive hierarchy, program size, primitive recursive functions