English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу

Сотрудники :: Бабин Дмитрий Николаевич :: Публикации Бабина Д.Н.

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

Бабин Д.Н.
Кафедра Математической теории интеллектуальных систем

Скачать статью полностью в формате 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 г.

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru