ПРЕДСТАВИМОСТИ МАТРИЦ ПРОБЛЕМА

проблема, заключающаяся в том, чтобы выяснить, можно ли указать такой единый общий метод ( алгоритм), к-рый по произвольной системе U, U₁ ,. . ., U_q целочисленных матриц позволял бы за конечное число шагов ответить на вопрос, представима ли матрица Uчерез остальные матрицы U₁ ,. . ., U_q с помощью операции умножения. Наибольший интерес представляет случай, когда матрицы U, U₁ , . . ., U_q являются квадратными и имеют один и тот же порядок. Так сформулированная П. м. п. наз. общей. Фиксируя матрицы U₁ , . .., U_q и оставляя матрицу Uпеременной, получают т. <н. частные П. м. п. Алгоритм, решающий общую П. м. п., решал бы и все частные проблемы, так что для установления неразрешимости общей П. м. п. достаточно указать хотя бы одну неразрешимую частную П. м. п.

П. м. п.- одна из первых алгоритмических проблем алгебраич. характера, неразрешимость к-рых была установлена. Первоначально А. А. Марковым было показано (см. [1], [2]), что для любого может быть построена система, состоящая из 91 матрицы порядка п, такая, что соответствующая ей частная П. м. п. будет неразрешимой, т. е. будет невозможен алгоритм (понимаемый в точном смысле этого слова), распознающий по произвольной матрице порядка п, представима ли она через матрицы данной системы. В дальнейшем (см. [3]) число матриц в системе было уменьшено до 23 и было показано, что за счет надлежащего усложнения конструкции системы (включая увеличение числа членов) условие может быть ослаблено до . Для любого строится конкретная система, состоящая из 12 матриц порядка п, с неразрешимой частной П. <м. <и. (см. [4]). Путем подходящей фиксации Uи варьирования U₁ , . . ., U_q доказана неразрешимость общей П. <м. <п. для n=3 (см. [5]).

Лит.:[1] Марков А. А., "Докл. АН СССР", 1951, т. 78, № в, с. 1089-92; [2] его же, Теория алгорифмов, М.- Д., 1954 (Тр. Матем. ин-та АН СССР, т. 42); [3] его же, "Z. math. Logik und Grundl. Math.", 1958, Bd 4, S. 157-68; [4] Haгорный Н. M., "VI Всесоюзн. конференция по матем. логике", Тб., 1982, с. 124; [5] Paterson M.S., "Studies in appl. math.", 1970, v. 49, № 1, p. 105-07. Н. М. Нагорный.