Economy of Descriptions and Minimal Indices.
Abstract
It has been known for some time that if the power of a programming language is restricted it very often tends to lose succinctness in its description of programs. A primitive recursive definition scheme for instance is frequently not as concise in describing primitive recursive functions as a double recursive definition scheme. A careful study of the problem has been made by Meyer, where he shows that as one increases the power of programming languages, one can obtain economies in program size by any recursive amount for even very simple functions. The principal objective of this part of the thesis is the generalization of the results of Meyer to sets of integers A and B related in some recursion theoretic manner, e.g. A double prime < or = (sub T) B prime. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1972
- Accession Number
- AD0736960
Entities
People
- Amitava Bagchi
Organizations
- Massachusetts Institute of Technology