Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Query-Optimal Oracle Turing Machines for Type-2 Computations

Edit abstract data

Speaker: Chung-Chih Li
Slot: Wed, 11:30-11:50, Room 24 (col. 3)


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.

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!