# Plain stopping time and conditional complexities revisited

2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by 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 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 $2^n$ prefixes $z$ such that \$K(z)
Document type :
Other publications
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01803546
Contributor : Alexander Shen Connect in order to contact the contributor
Submitted on : Wednesday, May 30, 2018 - 2:55:43 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM

### Identifiers

• HAL Id : lirmm-01803546, version 1
• ARXIV : 1708.08100

### Citation

Mikhail Andreev, Gleb Posobin, Alexander Shen. Plain stopping time and conditional complexities revisited. 2017. ⟨lirmm-01803546⟩

Record views