Note on the topological structure of random strings

DOI10.1016/0304-3975(93)90027-QzbMath0781.68073OpenAlexW1999238062WikidataQ57001788 ScholiaQ57001788MaRDI QIDQ1210302

Cezar Campeanu, Cristian S. Calude

Publication date: 24 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90027-q

zbMATH Keywords

Kolmogorov complexityrandom stringseffective topology

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theories of computational complexity
• On the Topological Size of Sets of Random Strings
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Each regular code is included in a maximal regular code
• Relations on free monoids, their independent sets, and codes¹
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences