zbMATH — the first resource for mathematics

Sequences of binary strings with relation of conditional simplicity. (English. Russian original) Zbl 0990.94021
Mosc. Univ. Math. Bull. 55, No. 5, 20-22 (2000); translation from Vestn. Mosk. Univ., Ser. I 2000, No. 5, 19-22 (2000).
The author considers a finite analogue of the Turing degrees of unsolvability [J. Shenfield, “Degrees of unsolvability”, Nauka, Moscow (1977)] and determines a partial order formalizing the intuitive relation “\(x\) is simple with respect to \(y\)”. It is shown that the partially ordered set defined in this way is an upper semi-lattice, rather than a lattice.
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
06A12 Semilattices
94A15 Information theory (general)