Эта публикация цитируется в
2 статьях
Математика
Две теоремы о минимальных обобщенно-вычислимых нумерациях
М. Х. Файзрахманов Научно-образовательный математический центр Приволжского федерального округа Казанского федерального университета
Аннотация:
В статье доказывается, что для любого множества
$A$, вычисляющего невычислимое вычислимо перечислимое множество, каждое бесконечное
$A$-вычислимое семейство обладает бесконечным числом попарно неэквивалентных минимальных
$A$-вычислимых нумераций. Устанавливается, что произвольное множество
$A\leqslant_T\emptyset '$ является низким тогда и только тогда, когда любое бесконечное
$A$-вычислимое семейство с наибольшим по включению множеством обладает бесконечным числом попарно неэквивалентных позитивных
$A$-вычислимых нумераций.
Ключевые слова:
минимальная нумерация, позитивная нумерация, вычислимо перечислимое множество, низкое множество.
УДК:
510.5 Поступила в редакцию: 14.11.2022
DOI:
10.55959/MSU0579-9368-1-64-3-5