Subrecursive programming languages II on program size

摘要

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 beteeen 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-efficency 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.