### ?

## The normalized algorithmic information distance can not be approximated

P. 130-141.

Bauwens B. F., Blinnikov I.

It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all *𝜀*<1/2, there exist no semicomputable functions that differ from N by at most *𝜀*. Moreover, for any computable function *f* such that |lim*𝑡**𝑓*(*𝑥*,*𝑦*,*𝑡*)−N(*𝑥*,*𝑦*)|≤*𝜀* and for all *n*, there exist strings *x*, *y* of length *n* such that

∑*_𝑡 *|*𝑓*(*𝑥*,*𝑦*,*𝑡*+1)−*𝑓*(*𝑥*,*𝑦*,*𝑡*)| ≥* 𝛺*(log *𝑛*)

This is optimal up to constant factors.

We also show that the maximal number of oscillations of a limit approximation of N is *𝛺*(*𝑛*/log*𝑛*). This strengthens the *𝜔*(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, *Normalized information distance and the oscillation hierarchy*].

Keywords: Kolmogorov complexitycomputability theoryAlgorithmic information distanceoscillation hierarchy

Publication based on the results of:

Bauwens B. F., , in : 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1-46:14.

Added: March 20, 2020

Bauwens B. F., Shen A., Theory of Computing Systems 2013 Vol. 52 No. 2 P. 297-302

Added: October 2, 2015

Vereshchagin N., Milovanov A., , in : 32nd Computational Complexity Conference. : Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.

A fundamental notion in Algorithmic Statisticsis that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical ...

Added: October 12, 2017

Bauwens B. F., Archive for Mathematical Logic 2015 Vol. 54 No. 5 P. 615-629

Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K ...

Added: October 2, 2015

Bauwens B., Makhlin A., Vereshchagin N. et al., Short lists with short programs in short time / . 2013. No. TR13-007.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: December 14, 2013

Milovanov A., , in : Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015. P. 339-349.

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will ...

Added: June 27, 2016

Bauwens B. F., Shen A., Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632

Added: October 2, 2015

Milovanov A., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521-535

Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...

Added: June 27, 2016

Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531-537

The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as ...

Added: January 17, 2020

Vereshchagin N., Bauwens B. F., Makhlin A. et al., Computational Complexity 2018 Vol. 27 No. 1 P. 31-61

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: April 22, 2017

Rubtsov A. A., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...

Added: September 12, 2018

Bienvenu L., Desfontaines D., Shen A., Logical Methods in Computer Science 2016 Vol. 12 No. 2

The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the ...

Added: February 7, 2017

Bauwens B. F., Theory of Computing Systems 2015 Vol. 58 No. 3 P. 482-501

Added: October 2, 2015

Day A., Fellows M., Greenberg N. et al., Berlin : Springer, 2017

Added: October 26, 2018

Milovanov A., , in : 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13.

Algorithmic statistics considers the following problem: given a binary string
x
(e.g., some
experimental data), find a “good” explanation of this data. It uses algorithmic information
theory to define formally what is a good explanation. In this paper we extend this framework in
two directions.
First, the explanations are not only interesting in themselves but also used for prediction: we
want to ...

Added: June 27, 2016

Vereshchagin N., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669-737

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...

Added: February 13, 2017

Milovanov A., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable.
In this paper we develop algorithmic ...

Added: October 15, 2017

Milovanov A., , in : Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. : Springer, 2021. Ch. 17. P. 283-295.

We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) ...

Added: August 11, 2021

Shen A., Uspensky V. A., Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017

Antunes L., Bauwens B. F., Souto A. et al., Theory of Computing Systems 2017 Vol. 60 No. 2 P. 280-298

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program ...

Added: May 4, 2016

Shen A., Vereshchagin N., , in : Computability and Complexity. : Berlin : Springer, 2017. P. 669-737.

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...

Added: October 26, 2018

Bienvenu L., Muchnik A., Shen A. et al., Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that lim supnC(x|n) equals C0′(x). Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary ...

Added: December 14, 2013

Ianovski E., Miller R., Ng K. M. et al., Journal of Symbolic Logic 2014 Vol. 3 No. 79 P. 859-881

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by
R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].
Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is ...

Added: February 25, 2019

Vereshchagin N., , in : CSR 2014 : 9th International Computer Science Symposium in Russia. Proceedings. Vol. 8476.: Berlin : Springer, 2014. P. 365-374.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha y
gin. Randomized Individual Communication Complexity. IEEE Con ference on Computational Complexity 2008: 321-331] considered com munication complexity of the following problem. Alice has a bi nary string x and Bob a binary string y, both of length n, and they
want to compute or approximate Kolmogorov complexity C(x|y) of
x conditional to ...

Added: October 6, 2014