Merkle, Wolfgang ;
Teutsch, Jason
Constant compression and random weights
Abstract
Omega numbers, as considered in algorithmic randomness, are by definition real numbers that are equal to the halting probability of a universal prefixfree Turing machine. Omega numbers are obviously leftr.e., i.e., are effectively approximable from below. Furthermore, among all leftr.e. real numbers in the appropriate range between 0 and 1, the Omega numbers admit wellknown characterizations as the ones that are MartinLöf random, as well as the ones such that any of their effective approximation from below is slower than any other effective approximation from below to any other real, up to a constant factor. In what follows, we obtain a further characterization of Omega numbers in terms of Theta numbers.
Tadaki considered for a given prefixfree Turing machine and some natural number a the set of all strings that are compressed by this machine by at least a bits relative to their length, and he introduced Theta numbers as the weight of sets of this form.
He showed that in the case of a universal prefixfree Turing machine any Theta number is an Omega number and he asked whether this implication can be reversed. We answer his question in the affirmative and thus obtain a new characterization of Omega numbers.
In addition to the onesided case of the set of all strings compressible by at least a certain number a of bits, we consider sets that comprise all strings that are compressible by at least a but no more than b bits, and we call the weight of such a set a twosided Theta number. We demonstrate that in the case of a universal prefixfree Turing machine, for given a and all sufficiently large b the corresponding twosided Theta number is again an Omega number. Conversely, any Omega number can be realized as twosided Theta number for any pair of natural numbers a and b>a.
BibTeX  Entry
@InProceedings{merkle_et_al:LIPIcs:2012:3435,
author = {Wolfgang Merkle and Jason Teutsch},
title = {{Constant compression and random weights}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {172181},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3435},
URN = {urn:nbn:de:0030drops34351},
doi = {10.4230/LIPIcs.STACS.2012.172},
annote = {Keywords: computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number}
}
2012
Keywords: 

computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 