DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.62

Randomness Versus Superspeedability

Authors: Rupert Hölzl, Philip Janicki, Wolfgang Merkle, and Frank Stephan

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

Abstract

Speedable numbers are real numbers which are algorithmically approximable from below and whose approximations can be accelerated nonuniformly. We begin this article by answering a question of Barmpalias by separating a strict subclass that we will refer to as superspeedable from the speedable numbers; for elements of this subclass, acceleration is possible uniformly and to an even higher degree. This new type of benign left-approximation of numbers then integrates itself into a hierarchy of other such notions studied in a growing body of recent work. We add a new perspective to this study by juxtaposing this hierachy with the well-studied hierachy of algorithmic randomness notions.

Cite as

Rupert Hölzl, Philip Janicki, Wolfgang Merkle, and Frank Stephan. Randomness Versus Superspeedability. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{holzl_et_al:LIPIcs.MFCS.2024.62,
  author =	{H\"{o}lzl, Rupert and Janicki, Philip and Merkle, Wolfgang and Stephan, Frank},
  title =	{{Randomness Versus Superspeedability}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{62:1--62:14},
  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.62},
  URN =		{urn:nbn:de:0030-drops-206187},
  doi =		{10.4230/LIPIcs.MFCS.2024.62},
  annote =	{Keywords: superspeedable numbers, speedable numbers, regainingly approximable numbers, regular numbers, left-computable numbers}
}

Search Results

Documents authored by Janicki, Philip

Randomness Versus Superspeedability

Abstract

Cite as

Thanks for your feedback!

Could not send message