# 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.
##### MSC:
 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory 06A12 Semilattices 94A15 Information theory (general)