Аннотация:
В статье изучаются вычислимые нумерации и полурешетки Роджерса классов семейств всюду определенных (тотальных) вычислимых функций. Доказано, что тип изоморфизма полурешетки Роджерса любого конечного класса вычислимых семейств тотальных функций $\mathfrak{F}$ зависит только от упорядочений по включению самого класса $\mathfrak{F}$ и класса $C(\mathfrak{F})$ замыканий его элементов, рассматриваемых как подмножества бэровского пространства. Получен критерий существования универсальных нумераций конечных классов вычислимых семейств тотальных функций, а также исследовано свойство замкнутости произвольных классов семейств тотальных функций, обладающих универсальными нумерациями, относительно объединений вычислимых возрастающих последовательностей их элементов. Установлено, что нетривиальные полурешетки Роджерса вычислимых классов $\mathfrak{F}$, у которых $C(\mathfrak{F})$ конечно, бесконечны и не являются решетками.
Ключевые слова и фразы:нумерация, вычислимая нумерация, $\Sigma^0_n$-вычислимая нумерация, вычислимое семейство, $\Sigma^0_n$-вычислимое семейство, вычислимый класс семейств, полурешетка Роджерса, универсальная нумерация.
УДК:510.57
Статья поступила: 11.05.2021 Переработанный вариант: 15.07.2021 Принята к публикации: 30.08.2021