«ВЫЧИСЛИМЫЕ МОДЕЛИ
И НУМЕРАЦИИ»
С 6 по 11 августа на базе Института математики СО РАН проходила международная конференция «Вычислимые модели и нумерации», организованная в рамках гранта Национального научного Фонда США DMS-0554841. Среди участников гранта — сотрудники отдела математической логики Института математики С. Гончаров, А. Морозов, О. Кудинов, Е. Фокина.
В современной математике алгоритмические проблемы лежат в центре многообразных направлений исследований и играют существенную роль в приложениях современных методов в науке и производстве, а также в других сферах человеческой деятельности. В этой связи сам феномен вычислимости, ставший объектом математического исследования лишь в начале XX столетия, является предметом изучения математической логики, математической кибернетики и теоретического программирования. Сибирская школа алгебры и логики, основанная академиками А. И. Мальцевым и Ю. Л. Ершовым, — один из мировых лидеров в этой области. Исследования этого коллектива формируются вокруг проблем теории вычислимости и ее приложений в теории моделей, алгебре и теоретическом программировании.
Одно из основных направлений исследований коллектива связано с изучением алгоритмических свойств математических моделей. В изучении алгоритмической природы математических моделей сформировалось два подхода. Первый из них восходит к работам Б.Л. ван дер Вардена, М. О. Рабина, Р. Л. Воота, А. Фрелиха и Дж. Шефердсона, А. И. Мальцева, А. В. Кузнецова и Б. А. Трахтенброта. Он связан с изучением алгоритмических свойств на структурах, которые допускают задание имен для элементов этой структуры словами в некотором конечном алфавите. На основе классической теории вычислимости изучаются алгоритмические свойства этих структур. Исследование же таких объектов, как, например, алгоритмы решения систем линейных уравнений над полем вещественных или комплексных чисел, решение проблем нахождения дискретных автоматных управлений для сложных систем, работа которых описывается дифференциальными или интегральными уравнениями, требует построения общей теории вычислимости над произвольными абстрактными структурами. Данные исследования восходят к трудам Я. Московакиса, А. Нероуда, Д. Барвайса, теории семантического программирования Гончарова-Ершова-Свириденко и других авторов. Эти проблемы и лежат в фокусе интересов представленной научной школы.
Исследования, проводимые коллективом сибирской научной школы, получили широкое признание в России и в мировом научном сообществе. С. Гончаров, совместно с профессором Б. Купером из Англии, является соруководителем большого проекта по теории вычислимости, объединившего специалистов из России, Казахстана, Англии, Италии, Германии. Результаты этих работ в 2003 году были опубликованы в «Computability and models» под редакцией С. Гончарова и Б. Купера издательством «Kluwer Academic/Plenum Publishers» в известной серии «The University Series in Mathematics». С. Гончаров и профессор А. Нероуд из Корнельского университета (США) — инициаторы проекта издания книги по рекурсивной математике «Handbook of Recursive Mathematics». Книга вышла в 1998 году в двух томах под редакцией Ю. Ершова, С. Гончарова и американских математиков А. Нероуда, Д. Реммеля и В. Марека в издательстве «Elsevier», серии «Studies in Logic and the Foundations of Mathematics». К подготовке книги были привлечены ведущие в мире специалисты по теории вычислимости из разных стран мира.
Об уровне работ по теории вычислимости в Новосибирске говорит и тот факт, что 9-я Азиатская логическая конференция 2005 года впервые проходила в России. В 2006 году под редакцией С. Гончарова, Р. Доуни и японского логика Х. Оно вышли труды 9-й Азиатской конференции по логике в Сингапурском издательстве. Также в 2006 и 2007 гг. в издательстве «Springer» опубликовано двухтомное издание под редакцией С. Гончарова, М. Захарьящева и английского логика Д. Габбая «Mathematical Problems from Applied Logic» в Международной математической серии, тома 4 и 5.
Теория вычислимости привлекает в последние годы внимание многих исследователей как в области математической логики, так и в программировании. В Европе была создана европейская программа «Computability in Europe», объединившая специалистов в области теории вычислимости из европейских университетов и бывших республик Советского Союза. Ее координатор — профессор Барри Купер из университета города Лидс (Англия). В состав программного комитета вошли ведущие специалисты из стран Европейского сообщества и России. В рамках программы ведутся совместные работы, обучение и подготовка аспирантов и студентов, стажировки и научные обмены, проводится серия конференций «Computability in Europe». Последняя конференция «Computation and Logic in the Real World» из этой серии была организована на базе Сиенского университета (Италия) 18-23 июня 2007 г. Одно из направлений данной конференции было посвящено вычислимым моделям и вычислимым нумерациям. Активное участие в форуме приняли ученые из Института математики СО РАН. Чл.-корр. РАН С. Гончаров был членом Программного комитета, ак. Ю. Ершов — приглашенным пленарным лектором, с докладами выступили сотрудники Института математики и преподаватели Новосибирского государственного университета С. Подзоров, М. Коровина, Е. Фокина, А. Стукачев, А. Мельников. В рамках ежегодной логической конференции «Logic Colloquium-2007» во Вроцлаве (Польша) выступили аспиранты и студенты Новосибирского государственного университета А. Гаврюшкин, А. Ревенко и Е. Павловский. С. Гончаров был приглашенным пленарным лектором на конференции «Logic Colloquium-2005» в Афинах (Греция) по теории вычислимых моделей и теории нумераций. В феврале 2007 г. состоялась конференция в г. Гейнсвилль (штат Флорида, США), в которой с приглашенным докладом участвовал и чл.-корр. РАН С. Гончаров, а также аспирантка Института математики СО РАН Е. Фокина, проходившая в это время по гранту Президента России годовую стажировку в Университете города Нотр Дам (США).
Работы в области теории вычислимости и приложений ведутся в тесном сотрудничестве с ведущими специалистами из США, Германии, Англии, Новой Зеландии, Австралии, Китая, Италии и других стран при поддержке различных международных грантов. С 1 по 15 августа в Новосибирске находилась делегация американских логиков во главе с Почетным доктором СО РАН, Хоскинским профессором университета города Нотр Дам Джулией Найт. В рамках визита обсуждался широкий круг вопросов, проводились совместные исследования, в которых принимали участие сотрудники и аспиранты Института математики, аспиранты и студенты НГУ, зарубежные гости. Цель исследований — изучение вопросов теории вычислимых моделей, связанных со сложностью различных алгоритмических проблем на конструктивных и автоматных моделях, проблем изучения классификации различных типов множеств и классов моделей, связи проблем определимости и вычислимости.
На международной конференции, проводимой с 6 по 11 августа, с докладами выступили признанные лидеры в этой области, — ак. Ю. Ершов, чл.-корр. РАН С. Гончаров, проф. Дж. Ф. Найт, проф. С. Бадаев, а также более молодые перспективные исследователи. Были представлены 19 докладов. Один из дней был посвящен совместной работе и дискуссиям.
Главным итогом конференции можно считать возникновение новых научных контактов, обмен опытом и интересные идеи для дальнейших совместных исследований.
Наш корр.
стр. 7
|
