Paul Fahn

   Measuring Information Efficiency by Bounded Oracle Computation


What does it mean for two nonrecursive sets of natural numbers to
contain the same information? If two sets contain the same
information, how can we compare the efficiency with which they
represent the information?  We introduce quantitative measures of
relative information effiency between two sets A and B by asking a
series of questions along the lines of ``How many bits of A can be
computed from n bits of B?''

We show how to make these questions mathematically precise using a
model of computation with a bounded number of oracle queries. The
oracle queries can be either ``parallel,'' where all n questions are
asked at once, or ``sequential,'' where each oracle query can depend
on the answers to earlier queries. We examine, and present results
for, both models of bounded oracle computation, using the complete
sets of Ershov's difference hierarchy as natural examples.