License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.172
URN: urn:nbn:de:0030-drops-34351
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3435/
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 prefix-free Turing machine. Omega numbers are obviously left-r.e., i.e., are effectively approximable from below. Furthermore, among all left-r.e. real numbers in the appropriate range between 0 and 1, the Omega numbers admit well-known characterizations as the ones that are Martin-Lö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 prefix-free 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 prefix-free 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 one-sided 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 two-sided Theta number. We demonstrate that in the case of a universal prefix-free Turing machine, for given a and all sufficiently large b the corresponding two-sided Theta number is again an Omega number. Conversely, any Omega number can be realized as two-sided 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 = {172--181},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3435},
URN = {urn:nbn:de:0030-drops-34351},
doi = {10.4230/LIPIcs.STACS.2012.172},
annote = {Keywords: computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number}
}
|
Keywords: |
|
computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number |
|
Collection: |
|
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
24.02.2012 |
