Вычислимый Инвариант

Бинарного отношения между словами данного вида — алгоритм (в к.-л. точном смысле; напр. — как это сделано в [1] — нормальный алгорифм), применимый ко всякому слову рассматриваемого вида и перерабатывающий в одно и то же слово всякие два слова, связанные этим отношением. А. А. Марков называет два слова неотделимыми по инвариантам данного отношения, если всякий В. и. этого отношения перерабатывает упомянутые слова в один и тот же результат. Заметим, что если к.-л. бинарное отношение разрешимо (см. Разрешимое множество), то легко построить такой его В. и., к-рый будет принимать различные значения на любых двух словах, не связанных этим отношением. Если же для данного отношения удастся построить слова, им не связанные, но по его инвариантам неотделимые, то тем самым будет доказана также и неразрешимость рассматриваемого отношения. Многие известные алгоритмические проблемы алгебры и топологии могут быть формулированы как задачи исследования разрешимости определенных классов отношений эквивалентности, и отрицательные решения таких проблем обычно получаются в виде утверждений о наличии неразрешимых отношений среди определенного типа отношений эквивалентности. А. А. Марковым была осуществлена программа усиления в духе сделанного в предыдущем абзаце замечания известных отрицательных решений многих алгоритмич. проблем математики (проблемы тождества в теории групп, проблемы гомеоморфии, проблемы распознавания инвариантных свойств ассоциативных исчислений и групповых исчислений). Был построен пример перечислимого (см. Перечислимое множество), но не разрешимого отношения эквивалентности слов, у которого тем не менее любые два слова, не связанные этим отношением, отделимы по его инвариантам (см. [2]). Вопрос о возможности получения аналогичного результата для классов отношений, рассмотренных А. А. Марковым, остается открытым (1977). Лит.:[1] Марков А. А., "Изв. АН СССР. Сер. матем.", 1963, т. 27, М 4, с. 907-36; [2] Нагорный Н. М., в сб.: Исследования по теории алгорифмов и математической логике, т. 1, М., 1973, с. 205-10. Н. М. Нагорный.