Том 23, номер 3, 2016 г., Cтр. 81–92

УДК 519.716
Марченков С. С.
О максимальных подалгебрах в алгебрах одноместных рекурсивных функций

Аннотация:
Рассматриваются алгебры одноместных функций с носителями из счётных примитивно-рекурсивно замкнутых классов и операцией композиции. Доказывается, что любая алгебра этого типа имеет континуальное число максимальных подалгебр, включающих множество всех одноместных функций из класса $\mathscr{E}^{2}$ иерархии Гжегорчика.
Библиогр. 13.

Ключевые слова: максимальная подалгебра, одноместная рекурсивная функция.

DOI: 10.17377/daio.2016.23.518

Марченков Сергей Серафимович ¹
1. Московский гос. университет,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: ssmarchen@yandex.ru

Статья поступила 3 декабря 2015 г.
Исправленный вариант — 26 апреля 2016 г.

Литература

[1] Березин С. А. Об алгебре одноместных примитивно-рекурсивных функций с операцией итерации общего вида // Кибернетика. 1976. № 3. С. 12–19.

[2] Березин С. А. О максимальных подалгебрах алгебр рекурсивных функций // Кибернетика. 1978. № 6. С. 123–125.

[3] Гаврилов Г. П. О функциональной полноте в счётнозначной логике // Пробл. кибернетики. 1965. Вып. 15. С. 5–64.

[4] Гжегорчик А. Некоторые классы рекурсивных функций // Проблемы математической логики. М.: Мир, 1970. С. 9–49.

[5] Козьминых В. В. Об одноместных примитивно-рекурсивных функциях // Алгебра и логика. 1968. Т. 7, № 1. С. 75–90.

[6] Марченков С. С. Об одном методе построения максимальных подалгебр в алгебрах общерекурсивных функций // Алгебра и логика. 1978. T. 17, № 5. С. 581–595.

[7] Марченков С. С. О мощности множества предполных классов в некоторых классах функций счётнозначной логики // Пробл. кибернетики. 1981. Вып. 38. С. 109–116.

[8] Марченков С. С. Элементарные рекурсивные функции. М.: МЦНМО, 2003. 112 с.

[9] Марченков С. С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.

[10] Михеев В. Л. Об одном классе алгебр примитивно-рекурсивных функций // Мат. заметки. 1973. T. 14, № 1. С. 143–156.

[11] Ричи Р. В. Классы предсказуемо вычислимых функций // Проблемы математической логики. М.: Мир, 1970. С. 50–93.

[12] Розинас М. Г. Алгебра многоместных примитивно-рекурсивных функций // Уч. записки Иванов. гос. пед. ин-та. 1972. T. 117. С. 95–111.

[13] Соколов В. А. О максимальных подалгебрах алгебры всех частично рекурсивных функций // Кибернетика. 1972. № 1. С. 70–73.