RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2001, том 40, номер 2, страницы 202–217 (Mi al217)

О замкнутых классах финально периодических функций

А. П. Семигродских


Аннотация: Вводится понятие рекурсивно замкнутого класса и дается описание рекурсивно замкнутых классов, порожденных константами. Данные классы входят в некоторое частично упорядоченное множество, “пронизывающее” решетку всех замкнутых по суперпозиции классов, состоящих из примитивно рекурсивных функций. При описании рекурсивно замкнутых классов, порожденных константами, вводится понятие финально периодической функции, обобщающее понятие периодической функции. Основным результатом является теорема о том, что рекурсивно замкнутый класс, порожденный множеством из $n$ констант, совпадает с классом всех принимающих значения из этого множества финально периодических функций, периоды которых делят натуральные степени числа $n!$. В качестве следствия получается описание рекурсивно замкнутых классов, порожденных бесконечными множествами констант. В частности, оказывается, что рекурсивно замкнутый класс, порожденный всеми константами, совпадает с классом всех финально периодических функций.

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

УДК: 512.56/.57:510.57

Поступило: 20.08.1999


 Англоязычная версия: Algebra and Logic, 2001, 40:2, 112–121

Реферативные базы данных:


© МИАН, 2024