
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