Simplified structure of proof. Consider a listing of all turing machines. T_1, T_2 …
The problem over which the speed up theorem applies involves simulating the first N Turing machines, but applying MUCH more compute to those that come first in the listing.
So your simulating Turing machine i for 2^^(N-i) (note double up arrow) steps.
By caching the outputs of the first few Turing machines, you can get a faster algorithm.
But, at some point, you get a Turing machine that never halts, but can’t be proved never to halt in ZFC.
At this point, your slower algorithm has to actually run the Turing machine, and your faster algorithm just magically knows that it never halts.
Blums speedup comes from replacing a long running computation, with a look up table full of uncomputable data. Computability theories “there exists an algorithm” allows you to magically know any finite amount of data.
Given the Blum infinite sequence of ever faster algorithms, there is a fastest algorithm that can be proved to work in ZFC.
Looked up Blum’s speedup theorem.
Simplified structure of proof. Consider a listing of all turing machines. T_1, T_2 …
The problem over which the speed up theorem applies involves simulating the first N Turing machines, but applying MUCH more compute to those that come first in the listing.
So your simulating Turing machine i for 2^^(N-i) (note double up arrow) steps.
By caching the outputs of the first few Turing machines, you can get a faster algorithm.
But, at some point, you get a Turing machine that never halts, but can’t be proved never to halt in ZFC.
At this point, your slower algorithm has to actually run the Turing machine, and your faster algorithm just magically knows that it never halts.
Blums speedup comes from replacing a long running computation, with a look up table full of uncomputable data. Computability theories “there exists an algorithm” allows you to magically know any finite amount of data.
Given the Blum infinite sequence of ever faster algorithms, there is a fastest algorithm that can be proved to work in ZFC.