|
Problemy Peredachi Informatsii, 1982, Volume 18, Issue 2, Pages 83–100
(Mi ppi1228)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Automata Theory and Pattern Recognition
Algebra of Invariant Properties of Binary Sequences
V. V. V'yugin
Abstract:
The author investigates properties of infinite binary sequences that are invariant relative to algorithmic equivalence of sequences. Any two properties that differ on a set for which some natural measure is equal to 0 are identified with one another. It is shown that the class of all computable subsequences and the class of all random subsequences cannot be separated into nontrivial subclasses by such properties. The principal technical results of the paper are associated with the study of the invariant properties that may be possessed by noncomputable sequences that are algorithmically not equivalent to any random sequences.
Received: 21.01.1981
Citation:
V. V. V'yugin, “Algebra of Invariant Properties of Binary Sequences”, Probl. Peredachi Inf., 18:2 (1982), 83–100; Problems Inform. Transmission, 18:2 (1982), 147–161
Linking options:
https://www.mathnet.ru/eng/ppi1228 https://www.mathnet.ru/eng/ppi/v18/i2/p83
|
Statistics & downloads: |
Abstract page: | 297 | Full-text PDF : | 123 | First page: | 1 |
|