Logical Approaches to Computational Barriers

Every sequence is decompressible from a random one

Speaker:
| David Doty |

Author(s): |
David Doty |

Slot: |
Array, 11:30-11:50, col. 1 |

Kučera and Gács independently showed that every infinite
sequence is Turing reducible to a Martin-Löf random sequence. We extend
this result to show that every infinite sequence *S* is
Turing reducible to a Martin-Löf random sequence *R*
such that the asymptotic number of bits of *R* needed to
compute *n* bits of *S*, divided by
*n*, is precisely the constructive dimension of
*S*. We show that this is the optimal ratio of query bits to
computed bits achievable with Turing reductions. As an application of this
result, we give a new characterization of constructive dimension in terms of
Turing reduction compression ratios.

websites: Arnold Beckmann | 2006-04-21 |