Programming languages which express programs for all computable (recursive) functions are called universal, those expressing programs only for a subset are called subrecursive programming languages, SPL's. M. Blum has shown that for certain SPL's any universal programming language (UPL) contains programs which are arbitrarily shorter and nearly as efficient as the shortest SPL program for the same function. We offer new proofs of this theorem to make the relationship between size and efficiency more revealing and to show that finitely often efficiency is the price of economy of size.
From the new proof we derive refinements of the basic theorem. In particular, we consider the size-efficiency exchange for the task of computing constants, and derive a measure of the relative expressive power of SPL's. The results are illustrated with some new programming language models. * The material in this paper is a portion of that presented in "On the Size of Programs in Subrecursive Formalisms" which appears in the Conference Record of the 2nd Annual ACM Symposium on Theory of Computing. Northampton, Mass., 1970, 1-9. The research was supported in part by NSF Grant GJ-579.
One can argue that only finite functions are "actually computed". However, for reasons of mathematical application a first approximation to actual computing should allow for the computability of infinite functions such as x + y, x 9 y, etc. See Elgot and Robinson [12] and McCarthy [18] for a discussion of this point. It is, in fact, one of the tasks of computing theory