Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-24T18:03:41.665Z Has data issue: false hasContentIssue false
  • English
  • Français

On size vs. efficiency for programs admitting speed-ups

Published online by Cambridge University Press:  12 March 2014

John Helm  and
Paul Young
John Helm
Affiliation:
Radford College, Radford, Virginia
Paul Young
Affiliation:
Purdue University, Lafayette, Indiana
Get access Rights & Permissions [Opens in a new window]

Abstract

Since the publication in 1967 of the two papers [1] and [2] by Manuel Blum, the techniques and results of “pure” recursion theory, particularly the recursion theorem and priority methods, have come to play an increasingly important role in studies of computational complexity. This paper gives a typical application of the recursion theorem with a fairly intricate diagonalization to answer a question raised by Blum in [3]. Roughly, we prove the existence of functions which have the property that if we are given any program for computing the function and want to pass to a program which computes the function much more efficiently, then we can only do so at the expense of obtaining a much larger program: the function which describes the necessary increase in the size of the more efficient program must grow more rapidly than any recursive function.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 36 , Issue 1 , March 1971 , pp. 21 - 27
Copyright
Copyright © Association for Symbolic Logic 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Blum, Manuel, A machine independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[2]Blum, Manuel, On the size of machines, Information and control, vol. 11 (1967), pp. 257–265.CrossRefGoogle Scholar
[3]Blum, Manuel, On effective procedures for speeding up algorithms, Journal of the Association for Computing Machinery (to appear).Google Scholar
[4]Meyer, A. R. and Fischer, P. C., On computational speed-up. Conference Record Ninth Annual IEEE Symposium on Switching and Automata Theory, 1968, pp. 351–355.Google Scholar
[5]Young, P. R., Speed-ups by changing the order in which sets are enumerated. Mathematical systems theory (to appear).Google Scholar