ВЫЧИСЛИМЫЙ ИНВАРИАНТ это:

ВЫЧИСЛИМЫЙ ИНВАРИАНТ

бинарного отношения между словами данного вида - алгоритм (в к.-л. точном смысле; напр. - как это сделано в [1] - нормальный алгорифм), применимый ко всякому слову рассматриваемого вида и перерабатывающий в одно и то же слово всякие два слова, связанные этим отношением.

А. А. Марков называет два слова неотделимыми по инвариантам данного отношения, если всякий В. и. этого отношения перерабатывает упомянутые слова в один и тот же результат. Заметим, что если к.-л. бинарное отношение разрешимо (см. Разрешимое множество), то легко построить такой его В. и., к-рый будет принимать различные значения на любых двух словах, не связанных этим отношением. Если же для данного отношения удастся построить слова, им не связанные, но по его инвариантам неотделимые, то тем самым будет доказана также и неразрешимость рассматриваемого отношения.

Многие известные алгоритмические проблемы алгебры и топологии могут быть формулированы как задачи исследования разрешимости определенных классов отношений эквивалентности, и отрицательные решения таких проблем обычно получаются в виде утверждений о наличии неразрешимых отношений среди определенного типа отношений эквивалентности. А. А. Марковым была осуществлена программа усиления в духе сделанного в предыдущем абзаце замечания известных отрицательных решений многих алгоритмич. проблем математики (проблемы тождества в теории групп, проблемы гомеоморфии, проблемы распознавания инвариантных свойств ассоциативных исчислений и групповых исчислений). Был построен пример перечислимого (см. Перечислимое множество), но не разрешимого отношения эквивалентности слов, у которого тем не менее любые два слова, не связанные этим отношением, отделимы по его инвариантам (см. [2]). Вопрос о возможности получения аналогичного результата для классов отношений, рассмотренных А. А. Марковым, остается открытым (1977).

Лит.:[1] Марков А. А., "Изв. АН СССР. Сер. матем.", 1963, т. 27, М 4, с. 907-36; [2] Нагорный Н. М., в сб.: Исследования по теории алгорифмов и математической логике, т. 1, М., 1973, с. 205-10. Н. М. Нагорный.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ВЫЧИСЛИМЫЙ ИНВАРИАНТ" в других словарях:

  • Инвариант графа — в теории графов  некоторое обычно числовое значение или упорядоченный набор значений (хэш функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при… …   Википедия

  • Изоморфизм графов — В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»