Andreev, Mikhail ;
Posobin, Gleb ;
Shen, Alexander
Plain Stopping Time and Conditional Complexities Revisited
Abstract
In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a onedirectional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefixfree set containing x; (c) the conditional complexity C(xx*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)<n; (e) as maxC^X(x) where C^X(z) is plain Kolmogorov complexity of z relative to oracle X and the maximum is taken over all extensions X of x.
We also show that some of these equivalent definitions become nonequivalent in the more general setting where the condition y and the object x may differ, and answer an open question from Chernov, Hutter and Schmidhuber [Alexey V. Chernov et al., 2007].
BibTeX  Entry
@InProceedings{andreev_et_al:LIPIcs:2018:9584,
author = {Mikhail Andreev and Gleb Posobin and Alexander Shen},
title = {{Plain Stopping Time and Conditional Complexities Revisited}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {2:12:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9584},
URN = {urn:nbn:de:0030drops95842},
doi = {10.4230/LIPIcs.MFCS.2018.2},
annote = {Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory}
}
27.08.2018
Keywords: 

Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 