On the size of programs in subrecursive formalisms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the size of programs in subrecursive formalisms

Full text

Pdf (700 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the second annual ACM symposium on Theory of computing table of contents

Northampton, Massachusetts, United States

Pages: 1 - 9

Year of Publication: 1970

Author

Robert L. Constable

Department of Computer Science, Cornell University, Ithaca, N.Y.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 10, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800161.805143 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Axt, Paul "Enumeration and the Grzegorczyk hierarchy," Z. Math Logik Grund.Math 9 (1963), 53-65.
	2	Axt, Paul #"Iteration of primitive recursion," abstract 597-182, Notices A.M.S., Jan. 1963.
	3	Blum, M. "On the Size of Machines," Information and Control, II, (1967), 257-265.
	4	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	5	Cleave, John P., "A Hierarchy of Primitive Recursive Functions," Zeitschr. F. Math Logik and Grund. D. Math., 9, (1963), 331-345.
	6	Cobham, Alan "The Intrinsic Computational Difficulty of Functions," Logic, Methodology and Philosophy of Science, Amsterdam, 1965.
	7	Constable, Robert L. Extending and Refining Hierarchies of Computable Functions. Comp. Sci. Tech. Report #25, Univ. of Wisc., 1968.
	8	Constable, Robert L. "Subrecursive programming languages for @@@@n," Comp. Sci. Tech. Report 70-53, Cornell Univ., 1970.
	9	Constable, Robert L. and Allan B. Borodin "On the efficiency of programs in subrecursive formalisms," Comp. Sci. Tech. Report 70-54, Cornell Univ., 1970.
	10	Calvin C. Elgot , Abraham Robinson, Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the ACM (JACM), v.11 n.4, p.365-399, Oct. 1964 [doi>10.1145/321239.321240]
	11	Fabian, Robert J. Hierarchies of general recursive functions and ordinal recursion, Ph.D. Diss. Case Inst. of Tech., 1965.
	12	Grzegorczyk, A. "Some Classes of Recursive Functions," Rozprawy Matematcyzne, (1953), 1-45.
	13	Hartmanis, J. and R. E. Stearns "On the Computational Complexity of Algorithms," Trans. AMC, 117, 5, (1965), 285-306.
	14	Kleene, S.C. Introduction to Metamathematics, Princeton, 1952.
	15	Kleene, S. C. "Extension of an Effectively Generated Class of Functions by Enumeration," Collog, Math. 6, (1958), pp. 67-78.
	16	McCarthy, John "A Basis for a Mathematical Theory of Computation," Computer Programming and Formal Systems, Amsterdam, 1963, pp. 30-70.
	17	E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
	18	Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
	19	Péter, Roze Recursive Functions, 3d ed., New York, 1967.
	20	Ritchie, Robert W. "Classes of Predictably Computable Functions, Trans." A.M.S., 106, 1963, pp. 139-173.
	21	Robbin, Joel Subrecursive hierarchies, Ph.D., Diss, Princeton, 1965.
	22	Robinson, R. M. "Primitive recursive functions," Bull AMS, 53, (1947), 915-942.
	23	Rogers, H. "Gödel numberings of partial recursive functions," J. SL, 23, 3, (1958), 331-341.
	24	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	25	Scott, Dana Some Definitional Suggestions for Automata Theory, J. Compts., & Syst. Sci., 1, (1967), pp. 187-212.
	26	J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]

CITED BY 2

	Robert L. Constable , Allan B. Borodin, Subrecursive Programming Languages, Part I: efficiency and program structure, Journal of the ACM (JACM), v.19 n.3, p.526-568, July 1972
	Michael Machtey, Classification of computable functions by primitive recursive classes, Proceedings of the third annual ACM symposium on Theory of computing, p.251-257, May 03-05, 1971, Shaker Heights, Ohio, United States