A Machine-Independent Theory of the Complexity of Recursive Functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Machine-Independent Theory of the Complexity of Recursive Functions

Full text

Pdf (977 KB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 2 (April 1967) table of contents

Pages: 322 - 336

Year of Publication: 1967

ISSN:0004-5411

Author

Manuel Blum

Department of Mathematics and Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 168, Citation Count: 93

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/321386.321395 What is a DOI?

ABSTRACT

The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations. A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program. A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.

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	ARBIB, M. A., AND BLUM, M. Machine dependence of degrees of difficulty. Proc. Amer. Math. Soc. 16, 3 (June 1965), 442-447.
	2	HARTMANIS, J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 5 (May 1965), 285-306.
	3	----- ,AND ........ . Computational complexity of reeursive sequences. Proc. 5th Annual Symp. on Switching Theory and Logical Design, Princeton, N. J., 1964.
	4	MYHILL, J. Linear bounded automata. WADD Tech. Note 60-165, U. of Pennsylvania Rep. No. 60-22 (June 1960).
	5	RABIN, M. O. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. No. 2, Hebrew U., Jerusalem, Israel (April 1960).
	6	---. Real time computation. Israel J. Math. I (1963), 203-211.
	7	RITCHIE, R.W. Classes of predictably computable functions. Trans. Amer. Math. Soc. I06, 1 (June 1963), 139-173.
	8	BOOERS, It., JR. GSdel numberings of partiM reeursive functions. J. Symbolic Logic 23, 3 (Sept. 1958), 331-341.
	9	----. Recursive functions and effective computability. McGraw-Hill, New York (in press).
	10	YAMADA, H. Real-time computation and recursive functions not real-time computable. IR, E Trans. EC-11, 66 (Dec. 1962), 753-760.
	11	COBHAM, A. The intrinsic computational complexity of functions. Proc. 1964 Int. Congress on Logic, Methodology and Philosophy of Science. North-Holland, Amsterdam, 1965, 24-30.
	12	COOKE, S. A. Otl the minimum computation time of functions. Bell Labs. Rep. BL-41, 1966.
	13	WINOGRAD, S. On the time required to perform multiplication. IBM Res. Rep. RC-1564, 1966.

CITED BY 93

	Paul R. Young, Speed-ups by changing the order in which sets are enumerated (Preliminary Version), Proceedings of the first annual ACM symposium on Theory of computing, p.89-92, May 05-07, 1969, Marina del Rey, California, United States
	Paul Young, Optimization Among Provably Equivalent Programs, Journal of the ACM (JACM), v.24 n.4, p.693-700, Oct. 1977
	Juris Hartmanis, On computational complexity and the nature of computer science, ACM Computing Surveys (CSUR), v.27 n.1, p.7-16, March 1995
	Giorgio Ausiello, On bounds on the number of steps to compute functions, Proceedings of the second annual ACM symposium on Theory of computing, p.41-47, May 04-06, 1970, Northampton, Massachusetts, United States
	Robert L. Constable, The Operator Gap, Journal of the ACM (JACM), v.19 n.1, p.175-183, Jan. 1972
	F. D. Lewis, Unsolvability considerations in computational complexity, Proceedings of the second annual ACM symposium on Theory of computing, p.22-30, May 04-06, 1970, Northampton, Massachusetts, United States
	L. H. Landweber , E. L. Robertson, Recursive properties of abstract complexity classes (Preliminary Version), Proceedings of the second annual ACM symposium on Theory of computing, p.31-36, May 04-06, 1970, Northampton, Massachusetts, United States
	L. H. Landweber , E. L. Robertson, Recursive Properties of Abstract Complexity Classes, Journal of the ACM (JACM), v.19 n.2, p.296-308, April 1972
	Michael O. Rabin, Complexity of computations, Communications of the ACM, v.20 n.9, p.625-633, Sept. 1977
	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
	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
	Manuel Blum, On effective procedures for speeding up algorithms, Proceedings of the first annual ACM symposium on Theory of computing, p.43-53, May 05-07, 1969, Marina del Rey, California, United States
	Richard Edwin Stearns, Turing Award lecture: it's time to reconsider time, Communications of the ACM, v.37 n.11, p.95-99, Nov. 1994
	Juris Hartmanis, Turing Award lecture on computational complexity and the nature of computer science, Communications of the ACM, v.37 n.10, p.37-43, Oct. 1994
	A. Borodin, Computational Complexity and the Existence of Complexity Gaps, Journal of the ACM (JACM), v.19 n.1, p.158-174, Jan. 1972
	John Gill , Manuel Blum, On Almost Everywhere Complex Recursive Functions, Journal of the ACM (JACM), v.21 n.3, p.425-435, July 1974
	Mark Fulk, Inductive inference with additional information, Journal of Computer and System Sciences, v.64 n.2, p.153-159, March 2002
	Sanat K. Basu, On classes of computable functions, Proceedings of the first annual ACM symposium on Theory of computing, p.55-59, May 05-07, 1969, Marina del Rey, California, United States
	L. J. Bass , Paul R. Young, Hierarchies based on computational complexity and irregularities of class determining measured sets (Preliminary Report), Proceedings of the second annual ACM symposium on Theory of computing, p.37-40, May 04-06, 1970, Northampton, Massachusetts, United States
	Sanjay Jain , Arun Sharma, Probability is more powerful than team for language identification from positive data, Proceedings of the sixth annual conference on Computational learning theory, p.192-198, July 26-28, 1993, Santa Cruz, California, United States
	David G. Willis, Computational Complexity and Probability Constructions, Journal of the ACM (JACM), v.17 n.2, p.241-259, April 1970
	Juris Hartmanis, Turing award lecture: on computational complexity and the nature of computer science, ACM Turing award lectures, ACM, New York, NY, 2007
	Edward L. Robertson, A corrected definition of "local speed-up", ACM SIGACT News
	Ivan M. Havel, Weak complexity measures, ACM SIGACT News
	Giuseppe Longo, Axioms for time dependence of resource consumption in computing recursive functions, ACM SIGACT News
	Michael O. Rabin, Complexity of computations, ACM Turing award lectures, ACM, New York, NY, 2007
	Richard Edwin Stearns, Turing award lecture: it's time to reconsider time, ACM Turing award lectures, ACM, New York, NY, 2007
	D. Tsichritzis, Computational processes, Record of the Project MAC conference on concurrent systems and parallel computation, ACM, New York, NY, 1970
	Edward L. Robertson, Complexity classes of partial recursive functions (Preliminary Version), Proceedings of the third annual ACM symposium on Theory of computing, p.258-266, May 03-05, 1971, Shaker Heights, Ohio, United States
	David Pager, On the Efficiency of Algorithms, Journal of the ACM (JACM), v.17 n.4, p.708-714, Oct. 1970
	Manuel Blum, On Effective Procedures for Speeding Up Algorithms, Journal of the ACM (JACM), v.18 n.2, p.290-305, April 1971
	Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978
	Efim Kinber , Christophe Papazian , Carl Smith , Rolf Wiehagen, On the intrinsic complexity of learning recursive functions, Proceedings of the twelfth annual conference on Computational learning theory, p.257-266, July 07-09, 1999, Santa Cruz, California, United States
	R. G. Hamlet, A patent problem for abstract programming languages; machine-independent computations, Proceedings of the fourth annual ACM symposium on Theory of computing, p.193-197, May 01-03, 1972, Denver, Colorado, United States
	John T. Gill, III, Computational complexity of probabilistic Turing machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.91-95, April 30-May 02, 1974, Seattle, Washington, United States
	Paul R. Young, Toward a Theory of Enumerations, Journal of the ACM (JACM), v.16 n.2, p.328-348, April 1969
	Léa Meyer, Aspects of complexity of conservative probabilistic learning, Proceedings of the eleventh annual conference on Computational learning theory, p.72-78, July 24-26, 1998, Madison, Wisconsin, United States
	Robert L. Constable, Type two computational complexity, Proceedings of the fifth annual ACM symposium on Theory of computing, p.108-121, April 30-May 02, 1973, Austin, Texas, United States
	Robert P. Daley, An Example of Information and Computation Resource Trade-Off, Journal of the ACM (JACM), v.20 n.4, p.687-695, Oct. 1973
	Sanjay Jain , Efim Kinber, Intrinsic complexity of learning geometrical concepts from positive data, Journal of Computer and System Sciences, v.67 n.3, p.546-607, November 2003
	Sanjay Jain , Frank Stephan, Learning how to separate, Theoretical Computer Science, v.313 n.2, p.209-228, 17 February 2004
	Sanjay Jain , Efim Kinber, Learning multiple languages in groups, Theoretical Computer Science, v.387 n.1, p.67-76, November, 2007
	D. M. Symes, The computation of finite functions, Proceedings of the fourth annual ACM symposium on Theory of computing, p.177-182, May 01-03, 1972, Denver, Colorado, United States
	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
	Neil D. Jones, Constant time factors do matter, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.602-611, May 16-18, 1993, San Diego, California, United States
	Steffen Lange , Gunter Grieser, Variants of iterative learning, Theoretical Computer Science, v.292 n.2, p.359-376, 27 January 2003
	Sanjay Jain , Arun Sharma, On the intrinsic complexity of language identification, Proceedings of the seventh annual conference on Computational learning theory, p.278-286, July 12-15, 1994, New Brunswick, New Jersey, United States
	Leonid Levin, Theory of computation: how to start, ACM SIGACT News, v.22 n.1, p.47-56, Winter 1991
	Sanjay Jain, The Intrinsic Complexity of Learning: A Survey, Fundamenta Informaticae, v.57 n.1, p.17-37, January 2003
	Sanjay Jain , Yen Kaow Ng , Tiong Seng Tay, Learning languages in a union, Journal of Computer and System Sciences, v.73 n.1, p.89-108, February, 2007
	Sanjay Jain , Arun Sharma, Generalization and specialization strategies for learning r.e. languages, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.1-26, 1998
	Steffen Lange , Jochen Nessel , Rolf Wiehagen, Learning recursive languages from good examples, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.27-52, 1998
	Sanjay Jain , Steffen Lange , Sandra Zilles, Some natural conditions on incremental learning, Information and Computation, v.205 n.11, p.1671-1684, November, 2007
	Robert L. Constable, On the size of programs in subrecursive formalisms, Proceedings of the second annual ACM symposium on Theory of computing, p.1-9, May 04-06, 1970, Northampton, Massachusetts, United States
	D. W. Loveland, On minimal-program complexity measures, Proceedings of the first annual ACM symposium on Theory of computing, p.61-78, May 05-07, 1969, Marina del Rey, California, United States
	Leonard Bass , Paul Young, Ordinal Hierarchies and Naming Complexity Classes, Journal of the ACM (JACM), v.20 n.4, p.668-686, Oct. 1973
	Sanjay Jain , Steffen Lange , Jochen Nessel, On the learnability of recursively enumerable languages from good examples, Theoretical Computer Science, v.261 n.1, p.3-29, 06/17/2001
	Aldo de Luca, A survey of some quantitative approaches to the notion of information, Formal and natural computing, Springer-Verlag New York, Inc., New York, NY, 2002
	J. Hartmanis , J. E. Hopcroft, Independence results in computer science, ACM SIGACT News, v.8 n.4, p.13-24, October-December 1976
	La Meyer, Aspects of complexity of probabilistic learning under monotonicity constraints, Theoretical Computer Science, v.268 n.2, p.275-322, 17 October 2001
	Lorenzo Carlucci , John Case , Sanjay Jain , Frank Stephan, Results on memory-limited U-shaped learning, Information and Computation, v.205 n.10, p.1551-1573, October, 2007
	Andrea Asperti, The intensional content of Rice's theorem, ACM SIGPLAN Notices, v.43 n.1, January 2008
	John Case , Sanjay Jain , Arun Sharma, On learning limiting programs, Proceedings of the fifth annual workshop on Computational learning theory, p.193-202, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	John Case , Sanjay Jain , Mandayam Suraj, Control structures in hypothesis spaces: the influence on learning, Theoretical Computer Science, v.270 n.1-2, p.287-308, January
	Sanjay Jain , Efim Kinber , Rolf Wiehagen , Thomas Zeugmann, On learning of functions refutably, Theoretical Computer Science, v.298 n.1, p.111-143, 4 April 2003
	Frank Stephan , Thomas Zeugmann, Learning classes of approximations to non-recursive functions, Theoretical Computer Science, v.288 n.2, p.309-341, 16 October 2002
	Steffen Lange , Sandra Zilles, Relations between gold-style learning and query learning, Information and Computation, v.203 n.2, p.211-237, December 15, 2005
	Rūsiņš Freivalds , Ognian Botuscharov , Rolf Wiehagen, Identifying nearly minimal Gödel numbers from additional information, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.199-209, 1998
	J. Hartmanis, On the Complexity of Undecidable Problems in Automata Theory, Journal of the ACM (JACM), v.16 n.1, p.160-167, Jan. 1969
	Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983
	John Case , Sanjay Jain , Arun Sharma, Synthesizing noise-tolerant language learners, Theoretical Computer Science, v.261 n.1, p.31-56, 06/17/2001
	Yasuhito Mukouchi , Masako Sato, Refutable language learning with a neighbor system, Theoretical Computer Science, v.298 n.1, p.89-110, 4 April 2003
	Lorenzo Carlucci , Sanjay Jain , Efim Kinber , Frank Stephan, Variations on U-shaped learning, Information and Computation, v.204 n.8, p.1264-1294, August 2006
	Steffen Lange , Gunter Grieser , Thomas Zeugmann, Inductive inference of approximations for recursive concepts, Theoretical Computer Science, v.348 n.1, p.15-40, 2 December 2005
	Sanjay Jain , Efim Kinber, Learning and extending sublanguages, Theoretical Computer Science, v.397 n.1-3, p.233-246, May, 2008
	Sanjay Jain , Efim Kinber, Learning languages from positive data and negative counterexamples, Journal of Computer and System Sciences, v.74 n.4, p.431-456, June, 2008
	Sanjay Jain , Efim Kinber, Iterative learning from positive data and negative counterexamples, Information and Computation, v.205 n.12, p.1777-1805, December, 2007
	Stephen A. Cook, An overview of computational complexity, ACM Turing award lectures, ACM, New York, NY, 2007
	Sanjay Jain , Efim Kinber , Rolf Wiehagen, Learning all subfunctions of a function, Information and Computation, v.192 n.2, p.185-215, August 1, 2004
	Lorenzo Carlucci , John Case , Sanjay Jain , Frank Stephan, Non-U-shaped vacillatory and team learning, Journal of Computer and System Sciences, v.74 n.4, p.409-430, June, 2008
	Marian Boykan Pour-El, Computer Science And Recursion Theory, Proceedings of the 1978 annual conference, p.15-20, December 04-06, 1978, Washington, D.C., United States
	Sanjay Jain , Arun Sharma, Elementary formal systems, intrinsic complexity, and procrastination, Proceedings of the ninth annual conference on Computational learning theory, p.181-192, June 28-July 01, 1996, Desenzano del Garda, Italy
	John Case , Sanjay Jain , Frank Stephan , Rolf Wiehagen, Robust learning: rich and poor, Journal of Computer and System Sciences, v.69 n.2, p.123-165, September 2004
	A. R. Meyer , A. Bagchi, Program size and economy of descriptions: Preliminary Report, Proceedings of the fourth annual ACM symposium on Theory of computing, p.183-186, May 01-03, 1972, Denver, Colorado, United States
	Nancy Lynch , Albert Meyer , Michael Fischer, Sets that don't help, Proceedings of the fifth annual ACM symposium on Theory of computing, p.130-134, April 30-May 02, 1973, Austin, Texas, United States
	Michael Sipser, The history and status of the P versus NP question, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.603-618, May 04-06, 1992, Victoria, British Columbia, Canada
	Ganesh R. Baliga , John Case , Sanjay Jain, Synthesizing enumeration techniques for language learning, Proceedings of the ninth annual conference on Computational learning theory, p.169-180, June 28-July 01, 1996, Desenzano del Garda, Italy
	Leonid A. Levin, Fundamentals of computing (a cheatlist), ACM SIGACT News, v.27 n.3, p.89, Sept. 1996
	Gunter Grieser, Reflective inductive inference of recursive functions, Theoretical Computer Science, v.397 n.1-3, p.57-69, May, 2008
	Steffen Lange , Thomas Zeugmann , Sandra Zilles, Learning indexed families of recursive languages from positive data: A survey, Theoretical Computer Science, v.397 n.1-3, p.194-232, May, 2008
	Gregory J. Chaitin, On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers, Journal of the ACM (JACM), v.16 n.3, p.407-422, July 1969
	Thomas Zeugmann , Sandra Zilles, Learning recursive functions: A survey, Theoretical Computer Science, v.397 n.1-3, p.4-56, May, 2008
	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983