Today I had a presentation on the Speed-Up theorem for my Theory of Computation class, and I found the subject so interesting that I thought I would share it there as well. It has been developped by Manuel Blum in 1967, an MIT PhD that obtained later the Turing medal (equivalent of the Nobel prize for Computer Science) for his contribution in cryptography and theory of complexity. As an interesting side-note, he is the inventor of the CAPTCHA and its improvement, the reCAPTCHA.

Simply put, the theorem states that there exists functions that we cannot find optimal programs that compute them. An other way to say it is that there exists a function such that, if given a program i that computes it, there exists a program j that will compute this function but works much faster, or with much less memory, almost everywhere. This is far from being trivial but the intuition lies in the fact that given inputs that become larger and larger, we can tailor our program to be more efficient for those.

If those two short paragraphs interested you, you will find below a short abstract for my presentation, the slides and a video explaining the proof.

• abstract (fr)
• slides (fr)
• presentation (fr)