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

  • Никос [Nikos] Филиппович [Ph.] Алексиадис [Aleksiadis]
Ключевые слова: полином, функциональная система, проблема полноты, десятая проблема Гильберта, алгоритмически неразрешимая проблема

Аннотация

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

Сведения об авторе

Никос [Nikos] Филиппович [Ph.] Алексиадис [Aleksiadis]

Учёная степень:

кандидат физико-математических наук

Место работы

кафедра Математического моделирования НИУ МЭИ

Должность

доцент

Литература

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.
---
Для цитирования: Алексиадис Н.Ф. Об аналоге теоремы Слупецкого для полиномиальных функций // Вестник МЭИ. 2017. № 5. С. 143—149. DOI: 10.24160/1993-6982-2017-5-143-149.
#
1. Aleksiadis N.F. Funktsional'naya Sistema Polinomov s Natural'nymi Koeffitsientami. Vestnik MPEI. 2013;6:125—140. (in Russian).

2. Aleksiadis N.F. Ob Otnositel'noy Polnote v Funktsional'noy Sisteme Polinomov s Natural'nymi Koeffitsientami. Informatsionnye Sredstva i Tekhnologii: Trudy XXII Mezhdunar. Nauch.-tekhn. Konf. M.: Izd. Dom MPEI, 2014;3:95—100. (in Russian).

3. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami.
Vestnik MPEI. 2015;3:110—117. (in Russian).

4. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nahozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20;3:19—23. (in Russian).

5. Aleksiadis N.F., Tun Lin Naing. Predpolnota Nekotoryh Klassov Polinomov s Tselymi Koeffitsientami, Sohranyayushchih Konstanty. Informatsionnye Sredstva i Tekhnologii: Trudy XXI Mezhdunar. Nauch.-tekhn. Konf. M.: Izd. Dom MPEI, 2013;3:89—95. (in Russian).

6. Kudryavtsev V.B. Funktsional'nye Sistemy. Izd-vo MGU, 1982. (in Russian).

7. Yablonskiy S.V. Vvedenie v Diskretnuyu Matematiku. M.: Nauka, 1988. (in Russian).
---
For citation: Aleksiadis N.Ph. An Analog of Slupecki’s Theorem for Polynomials. MPEI Vestnik. 2017;5: 143—149. (in Russian).
DOI: 10.24160/1993-6982-2017-5-143-149.
Опубликован
2019-01-18
Раздел
Математика (01.01.00)