Об аналоге теоремы Слупецкого для полиномиальных функций


Аннотация

Функциональные системы являются одним из основных объектов дискретной математики и математической кибернетики. Содержательная связь функциональных систем с реальными кибернетическими моделями управляющих систем, с одной стороны, определяет серию существенных требований, которые накладываются на функциональные системы, а с другой стороны, порождает класс важных задач, имеющих как теоретическое, так и прикладное значение. Проблематика теории функциональных систем обширна. К числу основных относятся проблемы о полноте и относительной полноте, о выразимости, синтезе и анализе и другие. В настоящей статье рассмотрены функциональные системы полиномиальных функций: • с натуральными коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству натуральных чисел; • с целыми коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству целых чисел; • с рациональными коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству рациональных чисел. В качестве множества операций во всех функциональных системах взяты операции суперпозиции (перестановка переменных, переименование переменных без отождествления, отождествление переменных, введение фиктивной переменной, удаление фиктивной переменной и подстановка одной функции в другую), и для этих систем исследована проблема относительной полноты. Представлен алгоритмический подход данной проблемы (аналог теоремы Слупецкого) для указанных функциональных систем. В частности, доказано, что поставленная задача имеет положительный ответ только для функциональной системы с натуральными коэффициентами, а для двух других ответ отрицательный.


Ключевые слова

полином, функциональная система, проблема полноты, десятая проблема Гильберта, алгоритмически неразрешимая проблема


Библиографический список

 1. Алексиадис Н.Ф. Функциональная система полиномов с натуральными коэффициентами // Вестник МЭИ. 2013. № 6. С. 125—140.

2. Алексиадис Н.Ф. Об относительной полноте в функциональной системе полиномов с натуральными коэффициентами // Информационные средства и технологии: Труды XXII Междунар. науч.-техн. конф. М.: Изд. дом МЭИ, 2014. Т. 3. С. 95—100.

3. Алексиадис Н.Ф.  Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.

4. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.

5. Алексиадис Н.Ф., Тун Лин Наинг. Предполнота некоторых классов полиномов с целыми коэффициентами, сохраняющих константы // Информационные средства и технологии: Труды XXI Междунар. науч.-техн. конф. М.: Изд. дом МЭИ, 2013. Т. 3. С. 89—95.

6. Кудрявцев В.Б. Функциональные системы. Изд-во МГУ, 1982.

7. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1988.

DOI: 10.24160/1993-6982-2017-5-143-149

Для цитирования: Алексиадис Н.Ф. Об аналоге теоремы Слупецкого для полиномиальных функций // Вестник МЭИ. 2017. № 5. С. 143—149. DOI: 10.24160/1993-6982-2017-5-143-149.