Randomness extraction and asymptotic Hamming distance

Randomness extraction and asymptotic Hamming distance

We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-L\"of random in asymptotic Hamming distance. Our result is that the class of stochastically bi-immune sets is not Medvedev reducible to the class of sets having complex packing dimension 1.

Bibliographic Details
Main Authors: Cameron E. Freer, Bjoern Kjos-Hanssen
Format: Article
Language:English
Published: Logical Methods in Computer Science e.V. 2013-09-01
Series:Logical Methods in Computer Science
Subjects:
mathematics - logic
computer science - computational complexity
computer science - information theory
computer science - logic in computer science
Online Access:https://lmcs.episciences.org/889/pdf
Description
Summary:We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-L\"of random in asymptotic Hamming distance. Our result is that the class of stochastically bi-immune sets is not Medvedev reducible to the class of sets having complex packing dimension 1.
ISSN:1860-5974

Similar Items