The Journal of Symbolic Logic

Research Article

On size vs. efficiency for programs admitting speed-ups

John Helma1 and Paul Younga2 1

a1 Radford College, Radford, Virginia

a2 Purdue University, Lafayette, Indiana

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.

(Received October 08 1969)

Footnotes

1   Supported by NSF Grant GP 6120 at Purdue University. Presented at the American Mathematical Society Meetings in Miami, January, 1970 (Notices AMS, abstract 672–169).