  A resource-bounded version of the statement "no algorithm recognizes all
non-halting Turing machines" is equivalent to an infinitely often (i.o.)
superpolynomial speedup for the time required to accept any coNP-complete
language and also equivalent to a superpolynomial speedup in proof length in
propositional proof systems for tautologies, each of which implies P!=NP. This
suggests a correspondence between the properties 'has no algorithm at all' and
'has no best algorithm' which seems relevant to open problems in computational
and proof complexity.
