Automatic Kolmogorov complexity, normality, and finite-state dimension revisited - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Computer and System Sciences Year : 2021

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

Abstract

In this paper we characterize normal sequences and finite-state dimension in terms of the automatic Kolmogorov complexity and finite-state a priori probability. We show that many known results about normal sequences and finite-state dimension, including the equivalence between aligned and non-aligned normality, Wall's theorem, Piatetski–Shapiro's theorem, Champernowne's example of normal number and its modifications, equivalences between different definitions of finite-state dimension, Agafonov's and Schnorr's results about finite-state selection rules, become easy corollaries of this characterization. For that we use notions of automatic (finite-state) complexity and finite-state a priori probability that are the natural counterparts of the notions of Kolmogorov complexity and Solomonoff–Levin a priori probability in the algorithmic information theory. We also give a machine-independent characterization of normality and finite-state dimension in terms of superadditive calibrated functions. We compare our approach with previous results and notions relating finite automata and complexity.
Fichier principal
Vignette du fichier
S0022000020301215.pdf (394.61 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03371116 , version 1 (03-02-2023)

Licence

Attribution - NonCommercial

Identifiers

Cite

Alexander Kozachinskiy, Alexander Shen. Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. Journal of Computer and System Sciences, 2021, 118, pp.75-107. ⟨10.1016/j.jcss.2020.12.003⟩. ⟨lirmm-03371116⟩
31 View
22 Download

Altmetric

Share

Gmail Facebook X LinkedIn More