Note on the topological structure of random strings
type: Item
instance of: scholarly article
title: Note on the topological structure of random strings
zbMATH Open document ID: 0781.68073
DOI: 10.1016/0304-3975(93)90027-Q
published in: Theoretical Computer Science
publication date: 1993-05-24T00:00:00Z
review text: The natural way to define an effective topology on the set of finite strings is to start with a recursive order \(\leq\) and to define for each string \(v\) its basic open set as \(U_ v=\{w | v \leq w\}\). The topological size of random Kolmogorov strings is investigated with respect to a lot of topologies based, as above, on natural orderings of finite strings. The results are of the following types (1) the set of nonrandom strings is dense and (2) the set of random strings is recursively rare with the notably exception of the topology derived from the infix ordering. In this case, for strings over an alphabet with at least three symbols, the random strings form a dense set, while for binary strings the question remains open.
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 178044
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: effective topology
zbMATH Keywords: random strings
Wikidata QID: Q57001788
author: Cristian S. Calude
author: C. Câmpeanu
reviewed by: Marius Zimand
MaRDI profile type: Publication
cites work: On the Topological Size of Sets of Random Strings
cites work: Theories of computational complexity
cites work: Q3671142
cites work: Q3827996
cites work: Q3714070
cites work: Each regular code is included in a maximal regular code
cites work: Register machine proof of the theorem on exponential diophantine representation of enumerable sets
cites work: Relations on free monoids, their independent sets, and codes1
cites work: Q5540222
cites work: Q3214803
cites work: Q4385509
cites work: The definition of random sequences
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
full work available at URL: 0304-3975(93)90027-q
OpenAlex ID: W1999238062
DBLP publication ID: journals/tcs/CaludeC93
description: scientific article; zbMATH DE number 178044