Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Комбинаторика слов. Алгоритмические проблемы

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

Пытаясь описать конструктивную, алгоритмическую деятельность человека, мы также приходим к понятию слова и как указания к действию и как обрабатываемого объекта.

Заметим, наконец, что Слово оказывается началом всего сущего в мировых религиях.

В 1900 году Гильберт сформулировал свой знаменитый список проблем, в котором десятая состояла в поиске алгоритма решения полиномиальных уравнений в целых числах. Эта проблема получила отрицательное решение в 1970-м году в работе студента Ленинградского университета, ныне академика РАН Юрия Владимировича Матиясевича, представителя научно школы Андрей Андреевича Маркова в Санкт-Петербурге. В работах Геделя, Поста, Тьюринга в 1930-е годы появилось формальное определение того, что значит, что некоторая функция вычислима, что значит, что задача построения алгоритма — неразрешима. В конце 1940-ых годов общее определение вычислимости функций над словами было предложено А. А. Марковым. Замечательно, что еще до начала распространения компьютеров и программирования А. А. Марков построил систему структурного программирования и индуктивного доказательства правильности программ и детально доказал правильность работы компилятора (для своих — абстрактных, алгоритмов). Общий вид алгоритмов, работающих с графами был описан А. Н. Колмогоровым и В. А. Успенским в начале 1950-ых гг.

П. С. Новиков построил конечно определенную группу с неразрешимой проблемой равенства (в группе) элементов, задаваемых с помощью определяющих соотношений — словами над алфавитом порождающих. В терминах слов естественно формулируются и свойства самих групп и полугрупп. А. А. Марков доказал нераспознаваемость нетривиальных свойств конечно определенных полугрупп. Некоторые свойства групп оказывается возможным (алгоритмически) распознать по заданию группы. Однако для всех «естественно интересных» свойств нужного алгоритма не существует. Это доказал С. И. Адян в 1955 г. и двумя годами позже М. Рабин. Результат Адяна был вскоре использован А. А. Марковым для доказательства неразрешимости классической проблемы распознавания гомеоморфности топологических многообразий в размерностях больше четырех.

С. И. Адяну принадлежит и весьма тонкое доказательство существования алгоритма для задачи, которую легко понять школьнику: фиксировано слово, его разрешается вставлять в другие слова или вычеркивать в них; можно ли из одного слова получить другое?