О нумерациях классов семейств тотальных функций
М. Х. Файзрахманов Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, ул. Кремлевская, 18, Казань, 420008 РОССИЯ
Аннотация:
В статье изучаются вычислимые нумерации и полурешетки Роджерса классов семейств всюду определенных (тотальных) вычислимых функций. Доказано, что тип изоморфизма полурешетки Роджерса любого конечного класса вычислимых семейств тотальных функций
$\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
DOI:
10.33048/mattrudy.2022.25.108