Disjunctive sequence (original) (raw)
A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings). The complexity function of a disjunctive sequence S over an alphabet of size k is pS(n) = kn. A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic.
| Property | Value |
|---|---|
| dbo:abstract | A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings). The complexity function of a disjunctive sequence S over an alphabet of size k is pS(n) = kn. Any normal sequence (a sequence in which each string of equal length appears with equal frequency) is disjunctive, but the converse is not true. For example, letting 0n denote the string of length n consisting of all 0s, consider the sequence obtained by splicing exponentially long strings of 0s into the shortlex ordering of all binary strings. Most of this sequence consists of long runs of 0s, and so it is not normal, but it is still disjunctive. A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic. (en) Un nombre univers est un nombre réel dans les décimales duquel on peut trouver n'importe quelle succession de chiffres de longueur finie, pour une base donnée. Ainsi, si l'on se donne une manière de coder les caractères d'un livre selon une suite de chiffres (ce qui est le cas, par exemple, dans tout format informatique), on trouvera dans un nombre univers tous les livres déjà écrits et à venir, y compris celui de l'histoire de votre vie passée et future. Mais on ne peut bien sûr pas en tirer une quelconque information : ce serait aussi efficace que de générer une succession aléatoire de lettres et de réessayer jusqu'à obtenir le livre que l'on cherche, et cela suppose de le connaître déjà lettre par lettre. (fr) |
| dbo:wikiPageID | 4251950 (xsd:integer) |
| dbo:wikiPageLength | 7912 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032027967 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Prime_number_theorem dbc:Sequences_and_series dbr:Character_(computing) dbr:Limit_of_a_sequence dbr:Comeager dbr:Alphabet_(computer_science) dbr:Complexity_function dbr:Dense_set dbr:String_(computer_science) dbr:Shortlex_order dbr:Cube_(algebra) dbr:Floor_and_ceiling_functions dbr:Normal_number dbr:Conversion_(logic) dbr:Radix dbr:Prime_number dbr:Pi dbr:Polynomial dbr:Square_numbers dbr:Natural_numbers dbr:Real_number dbr:Champernowne_constant dbr:Sequence dbr:Unit_interval dbr:Recurrent_word dbr:Substring dbr:Euler's_number |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Cite_book dbt:Cite_journal dbt:Mono dbt:Refbegin dbt:Refend dbt:Reflist |
| dct:subject | dbc:Sequences_and_series |
| rdf:type | yago:WikicatSequencesAndSeries yago:Abstraction100002137 yago:Arrangement107938773 yago:Group100031264 yago:Ordering108456993 yago:Sequence108459252 yago:Series108457976 |
| rdfs:comment | A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings). The complexity function of a disjunctive sequence S over an alphabet of size k is pS(n) = kn. A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic. (en) Un nombre univers est un nombre réel dans les décimales duquel on peut trouver n'importe quelle succession de chiffres de longueur finie, pour une base donnée. Ainsi, si l'on se donne une manière de coder les caractères d'un livre selon une suite de chiffres (ce qui est le cas, par exemple, dans tout format informatique), on trouvera dans un nombre univers tous les livres déjà écrits et à venir, y compris celui de l'histoire de votre vie passée et future. (fr) |
| rdfs:label | Disjunctive sequence (en) Nombre univers (fr) |
| owl:sameAs | freebase:Disjunctive sequence yago-res:Disjunctive sequence wikidata:Disjunctive sequence dbpedia-fr:Disjunctive sequence https://global.dbpedia.org/id/4iup8 |
| prov:wasDerivedFrom | wikipedia-en:Disjunctive_sequence?oldid=1032027967&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Disjunctive_sequence |
| is dbo:wikiPageDisambiguates of | dbr:Disjunctive |
| is dbo:wikiPageRedirects of | dbr:Lexicon_(mathematics) dbr:Disjunctive_number dbr:Disjunctive_word dbr:Rich_number |
| is dbo:wikiPageWikiLink of | dbr:Lexicon_(mathematics) dbr:Normal_number dbr:Ehrenfeucht–Mycielski_sequence dbr:Champernowne_constant dbr:Disjunctive dbr:Disjunctive_number dbr:Disjunctive_word dbr:Rich_number |
| is foaf:primaryTopic of | wikipedia-en:Disjunctive_sequence |