Edit abstract data

### Abstract

With the notion of optimal programs defined in terms of Blum's complexity
measure, the well known speed-up theorem states that there exist computable
functions that do not have optimal programs. For type-2 computation, we argue
that the same speed-up theorem can be obtained as long as the complexity measure
satisfies Blum's complexity measure under the Oracle Turing Machine model.
In the present paper, we consider the oracle query as a dynamic complexity
measure. Since the query complexity is not a Blum's complexity measure, we
have to characterize the notions of optimal programs in a very different way. We
give three notions of query-optimal programs in different strength and argue
that the stronger the notion of query-optimal programs we define, the more
difficult to have query-optimal programs. In other words, with a stronger
definition of query-optimal programs, one can prove an easier version of the
speed-up theorem.