Вестник Московского Университета. Математика, Механика - Содержание


УДК 510.5

Последовательности двоичных слов с отношением условной простоты / Ромащенко А.Е. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2000. N 5. C. 19-22.

В работе рассматривается финитный аналог тьюринговых степеней неразрешимости. Определяется частичный порядок, формализующий интуитивное отношение ``слово $x$ просто относительно слова $y$''. Доказывается, что определяемое частично упорядоченное множество является верхней полурешеткой, но не является решеткой.

Библиогр. 5.

К оглавлению номера  Go!