Comment by dctwin

Cf. Blums speedup theorem for an extreme example of this