Points to ponder:

Speedup theorem:

There exists a (total computable) predicate P such that for any algorithm computing P(x) with running time T(x), there exists another algorithm computing P(x) with computation time O( T(x)).

Gap theorem:

For any computable unbounded r(n) there exist a computable time bound t(n) such that any language

computable in time t(n) is also computable in time r(t(n)).

How do these results gel with our sense that problems should have intrinsic running times ? what’s the catch ?

### Like this:

Like Loading...

*Related*

## 2 comments

Comments feed for this article

May 13, 2009 at 6:55 am

carlosscheideggerSince no one has tried it, let me be the first to make a fool of myself in front of everyone else 🙂

Is it that the speedup theorem hasn’t pegged the actual computational model to use? That is, are the algorithms that run on time $O(T(x))$ and $O(\log T(x))$ running on different models? If so, is that “just” a strengthening of the trick to add extra tapes to a Turing machine to reduce the running tie that manages to not say anything about the actual model?

(no comment previews?)

May 13, 2009 at 8:03 am

geomblogI’ll merely state that the model of computation is the same.