|
Сотрудники :: Бабин Дмитрий Николаевич :: Публикации Бабина Д.Н.
О полноте двуместных о.-д. функций относительно суперпозиции
Бабин Д.Н.
Кафедра Математической теории интеллектуальных систем
Скачать статью полностью в формате PDF (170 кб): gilbert.pdf
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x
Резюме:
13 проблема Гильберта состоит в следующем: доказать что при любом n всякая непрерывная в n-мерном кубе
функция может быть представлена в виде суперпозиции непрерывных функций двух переменных.
А.Н.Колмогоров [1] доказал более сильный результат: всякая непрерывная в
n-мерном кубе
функция может быть представлена в виде суперпозиции непрерывных функций одного переменного и функции
сложения. Проблема естественно обобщается на другие классы функций. Оказалось, что в классе дифференцируемых
функций такая представимость уже не имеет места [2]. Для детерминированных функций
(автоматов с бесконечной памятью), которые можно рассматривать как подкласс непрерывных функций,
имеет место отрицательное решение 13 проблемы Гильберта [3].
Конечных полных относительно суперпозиции систем о.д.-функций не существует, а все известные полные системы
содержат функции с неограниченным в совокупности числом переменных [4]. Поэтому важен вопрос
о минимальном числе переменных полной системы конечных автоматов.
В статье доказывается, что всякая о.д.-функция (конечный автомат) представим суперпозицией о.д.-функций
одного переменного и универсальной булевой функции.
-
- 1
-
Колмогоров А.Н. О представлении непрерывных функций нескольких
переменных в виде суперпозиций непрерывных функций одного переменного
и сложения. – Докл. АН СССР, 1957, т.114, 5, стр.953-956.
- 2
-
Витушкин А.Г., Хенкин Г.М. Линейные суперпозиции функций. – Успехи
матем. наук, 1967, т.22, вып. 1, стр.77-124.
- 3
-
Марченков С.С. Об одном методе анализа суперпозиций непрерывных функций. –
Проблемы кибернетики., вып.37, М:Наука, 1980, стр.5-17.
- 4
-
Кудрявцев В.Б., Алешин С.В., Подколзин А.С.
Введение в теорию автоматов.– М.:Наука, 1985.– с.151-174.
Дискретная математика, N4, 1989 г.
Наверх
|
