Математический словарь
" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

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

Значение ПРЕДСТАВИМОСТИ МАТРИЦ ПРОБЛЕМА в математической энциклопедии:

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

П. м. п.- одна из первых алгоритмических проблем алгебраич. характера, неразрешимость к-рых была установлена. Первоначально А. А. Марковым было показано (см. [1], [2]), что для любого может быть построена система, состоящая из 91 матрицы порядка п, такая, что соответствующая ей частная П. м. п. будет неразрешимой, т. е. будет невозможен алгоритм (понимаемый в точном смысле этого слова), распознающий по произвольной матрице порядка п, представима ли она через матрицы данной системы. В дальнейшем (см. [3]) число матриц в системе было уменьшено до 23 и было показано, что за счет надлежащего усложнения конструкции системы (включая увеличение числа членов) условие может быть ослаблено до . Для любого строится конкретная система, состоящая из 12 матриц порядка п, с неразрешимой частной П. <м. <и. (см. [4]). Путем подходящей фиксации Uи варьирования U1 , . . ., Uq доказана неразрешимость общей П. <м. <п. для 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. Н. М. Нагорный.