Accession Number : AD0736960

Title :   Economy of Descriptions and Minimal Indices.

Descriptive Note : Technical memo.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s) : Bagchi,Amitava

Report Date : JAN 1972

Pagination or Media Count : 43

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)

Descriptors :   (*PROGRAMMING LANGUAGES, MATHEMATICAL LOGIC), SET THEORY, RECURSIVE FUNCTIONS, GRAMMARS, THEOREMS

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE