For those not familiar, this was published by Lenore Blum and Manuel Blum (husband and wife). Manuel's speedup theorem from 1967 is totally mind-blowing. Unfortunately I'm not as familiar with Lenore's work.

> Blum's speedup theorem shows that for any complexity measure, there exists a computable function such that there is no optimal program computing it, because every program has a program of lower complexity.

https://en.m.wikipedia.org/wiki/Blum%27s_speedup_theorem