Comment by tgv

> You can always always tradeoff time vs space

Not always, isn't it? The theorem says that there exists a function that can be sped up, but not that every function can be. A trivial counter example would be the identity function on a TM. It's simply a HALT/ACCEPT. There's no way to reduce that.

The space/time trade-off is also not infinitely flexible, since it takes time to fill space. And lookup tables have to be constructed at run-time, or they'll be of finite size, and hence only a constant speed-up. Perhaps you were thinking of that theorem, the linear as wikipedia calls it? https://en.wikipedia.org/wiki/Linear_speedup_theorem