DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.72

Algorithmic Dimensions via Learning Functions

Authors: Jack H. Lutz and Andrei N. Migunov

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

We characterize the algorithmic dimensions (i.e., the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i.e., Martin-Löf random) sequences. Our proof uses Lutz’s and Mayordomo’s respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity.

Cite as

Jack H. Lutz and Andrei N. Migunov. Algorithmic Dimensions via Learning Functions. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.MFCS.2024.72,
  author =	{Lutz, Jack H. and Migunov, Andrei N.},
  title =	{{Algorithmic Dimensions via Learning Functions}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{72:1--72:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.72},
  URN =		{urn:nbn:de:0030-drops-206282},
  doi =		{10.4230/LIPIcs.MFCS.2024.72},
  annote =	{Keywords: algorithmic dimensions, learning functions, randomness}
}

Search Results

Documents authored by Migunov, Andrei N.

Algorithmic Dimensions via Learning Functions

Abstract

Cite as

Thanks for your feedback!

Could not send message