An Example of Information and Computation Resource Trade-Off
Robert Daley · Journal of the ACM · 1973
This paper is concerned with establishing the existence of a recursive sequence x which exhibits a "continuous" trade-off between the length of programs (information) which compute the finite initial segments of x and the computation resources (e.g.computation time) required by these programs for such computation.