Sequences of binary strings with relation of conditional simplicity (Q5960250)
From MaRDI portal
scientific article; zbMATH DE number 1727653
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Sequences of binary strings with relation of conditional simplicity |
scientific article; zbMATH DE number 1727653 |
Statements
Sequences of binary strings with relation of conditional simplicity (English)
0 references
14 April 2002
0 references
The author considers a finite analogue of the Turing degrees of unsolvability [\textit{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.
0 references
analogue of Turing degrees of unsolvability
0 references
sequence of binary strings
0 references
