Plain stopping time and conditional complexities revisited - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

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 [9]. 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 one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x∗) 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 2n prefixes z such that K(z) < n; (e) as max CX (x) where CX (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 non-equivalent 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 [3].
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2018-2.pdf (407.16 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-01982373 , version 1 (06-06-2019)

Licence

Identifiers

Cite

Mikhail Andreev, Gleb Posobin, Alexander Shen. Plain stopping time and conditional complexities revisited. MFCS 2018 - 43rd International Symposium on Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. ⟨10.4230/LIPIcs.MFCS.2018.2⟩. ⟨lirmm-01982373⟩
110 View
40 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More