- Φ(M,x) is finite if and only if M(x) halts, and
- There is a computable procedure that given (M,x,r) can decide if Φ(M,x)=r.

The Borodin-Trakhtenbrot Gap Theorem states that given any computable function g(n) (e.g. g(n)=2^n), there exists a function t(n) such that every language computable in time g(t(n)) is also computable in time t(n), i.e., there exists a gap between these time classes. Once again the theorem holds for any Blum complexity measure.

We don't see much of the Blum complexity measures these days for a few reasons.

- The only truly interesting Blum measures are time and space.
- The functions and languages that one gets out of the speed-up, gap and related theorems are usually quite large and artificial.
- Many measures that we are interested in today, like the number of random coins used by a probabilistic Turing machine, do not fulfill the Blum axioms.

## No comments:

## Post a Comment