Представимости матриц проблема

проблема, заключающаяся в том, чтобы выяснить, можно ли указать такой единый общий метод (алгоритм), к-рый по произвольной системе U, U1,..., Uq целочисленных матриц позволял бы за конечное число шагов ответить на вопрос, представима ли матрица Uчерез остальные матрицы U1,..., Uq с помощью операции умножения. Наибольший интерес представляет случай, когда матрицы U, U1,..., Uq являются квадратными и имеют один и тот же порядок. Так сформулированная П. м. п. наз. общей. Фиксируя матрицы U1,..., Uq и оставляя матрицу Uпеременной, получают т. П. м. п.- одна из первых алгоритмических проблем алгебраич. характера, неразрешимость к-рых была установлена. Первоначально А. А. Марковым было показано (см. [1], [2]), что для любого [img: http://localhost:8080/file/041742-50.jpg] может быть построена система, состоящая из 91 матрицы порядка п, такая, что соответствующая ей частная П. м. п. будет неразрешимой, т. е. будет невозможен алгоритм (понимаемый в точном смысле этого слова), распознающий по произвольной матрице порядка п, представима ли она через матрицы данной системы. В дальнейшем (см. [3]) число матриц в системе было уменьшено до 23 и было показано, что за счет надлежащего усложнения конструкции системы (включая увеличение числа членов) условие [img: http://localhost:8080/file/041742-51.jpg] может быть ослаблено до [img: http://localhost:8080/file/041742-52.jpg]. Для любого [img: http://localhost:8080/file/041742-53.jpg] строится конкретная система, состоящая из 12 матриц порядка п, с неразрешимой частной П.