Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Size of Programs in Subrecursive Formalisms

On the Size of Programs in Subrecursive Formalisms

File(s)
70-58.ps (361.95 KB)
70-58.pdf (936.7 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5917
Collections
Computer Science Technical Reports
Author
Constable, Robert L.
Abstract

This paper gives an overview of subrecursive hierarchy theory as it relates to computational complexity and applies some of the concepts to questions about the size of programs in subrecursive programming languages. The purpose is three-fold, to reveal in simple terms the workings of subrecursive hierarchies, to indicate new results in the area, and to point out ways that the fundamental ideas in hierarchy theory can lead to interesting questions about programming languages. A specific application yields new information about Blum's results on the size of programs and about the relationship between size and efficiency.

Date Issued
1970-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR70-58
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance