ТОЖДЕСТВА ПРОБЛЕМЫ

ТО́ЖДЕСТВА ПРОБЛЕ́МЫ

проблемы эквивалентности, проблемы иден-тичности, проблемы равенства с л о в (англ. word problems) – задачи нахождения общего метода (алгоритма), позволяющего для произвольной пары элементов к.-л. множества, в к-ром определено отношение типа равенства (тождества, эквивалентности), установить, равны ли эти элементы в смысле данного отношения. Каждая Т. п. является, т.о., разрешения проблемой для множества всех пар равных (эквивалентных) друг другу "слов" в нек-ром "алфавите". Напр., не содержащие кванторов и переменных формулы т.н. ограниченной арифметики (т.е. формальной арифметич. системы, в число аксиом к-рой не входит принцип математической индукции или к.-л. равносильный ему постулат) можно понимать как слова, "буквами" к-рых являются цифровые знаки и символы арифметич. операций; алгоритм, дающий положительное решение Т. п. для выражений вида Α=Β, образованных из таких формул с помощью стоящего между ними знака равенства, состоит в последовательном выполнении алгоритмов арифметич. действий в каждом из выражений А и В к последующей проверке, являются ли получившиеся в результате слова А и В, уже не содержащие букв "+", "–", "·" и ":", графически равными (т.е., попросту, совпадают ли они по написанию). Решение Т. п. даже для большинства сравнительно "простых" (по способу их задания) классов слов представляет, как правило, значит. трудности. Для нек-рых частных классов алгебраич. систем (групп, полугрупп) удалось найти алгоритмы, решающие (для них) Т. п. (М. Ден, В. Магнус, 1941, В. А. Тартаковский, 1949, и др.). Как и для любой массовой проблемы, для Т. п. положительное решение является в нек-ром смысле идеалом, к-рый, однако, достижим лишь в сравнительно редких случаях. Так, в 1947 А. А. Марков и амер. математик Э. Пост независимо друг от друга доказали алгоритмич. неразрешимость общей Т. п. для полугрупп (ассоциативных исчислений), поставленной еще в 1914. В 1950 Тьюринг установил неразрешимость Т. п. для т.н. полугрупп с сокращениями. Наконец, в 1952 П. С. Новиков доказал алгоритмич. неразрешимость Т. п. для групп, не поддававшуюся усилиям математиков с 1912 [этот результат был затем передоказан амер. математиками У. Буном (1959), Г. Хигманом (1961) и Дж. Бриттоном (1963)]. Дальнейшие результаты в этой области относятся к установлению иерархий, взаимной сводимости и степеней неразрешимости Т. п. для различных классов алгебраич. систем, а также к близким к Т. п. массовым проблемам логики, алгебры, теории алгоритмов и др. областей математики. Продолжаются и поиски частных классов систем с разрешимой Т. п. Неразрешимость важнейших случаев Т. п. свидетельствует о существенной нетривиальности не только различных Т. п., но и вообще самого понятия "равенства" ("тождества", "эквивалентности", "конгруентности" и т.п.), в т.ч. и в случаях "равенства по определению" (см. Определение), и об относит. характере этого важнейшего понятия логики и математики, зависящего, вообще говоря, от принимаемых в каждом конкретном случае исходных допущений (см. также Абстракция отождествления, Принцип абстракции, Тождество).

Лит.: Новиков П. С., Об алгоритмической неразрешимости проблемы тождества слов и теории групп, "Тр. Матем. ин-та АН СССР", 1955, т. 44; Адян С. И., Неразрешимость некоторых алгоритмических проблем теории групп, "Тр. Моск. матем. общества", 1957, т 6; Фридман Α. Α., Степени неразрешимости проблемы тождества для конечно-определенных групп, М., 1967; Rabin M. О., Recursive unsolvability of group theoretic problems, "Annals Mathematics", 1958, v. 67, No 1; Boone W., The word problem, там же, 1959, v. 70, No 2.

Ю. Гастев. Москва.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.