Математическая логика и теория алгоритмов

Теорема 6.7. Не существует нормального алгоритма В, позволяющего решить все задачи массовой проблемы {а^}. Иначе: не существует нормального алгоритма В, который позволил бы выяснить, применим или нет произвольный нормальный алгоритм А |К произвольному слову Р. Теорему примем без доказательства. 2. П р о б л е м а эквивалентности слов. Пусть А - некоторый алфа­ вит; Р и Q слова в этом алфавите; P ^ Q - ориентированная подста­ новка, т.е. когда вместо слова Р подставляется слово Q; P - Q - неориентированная подстановка, т.е. можно подставить либо вместо Р слово Q, либо наоборот, вместо Q слово Р . Из бесчисленного множества возможных подстановок в алфавите А задают некоторое конечное множество подстановок указанных видов и называют их допустимыми подстановками. Два слова Е й S в алфавите А называются эквивалентными, если существует конечная последовательность слов (R\=R, R „=S) такая, что i?,+ i получается из i?, в результате одной допустимой подстановки. Возникает следующая массовая проблема: для любых двух слов в данном алфавите -фебуется указать, эквивалентны они или нет - проблема эквивалентности слов. Марков и Пост доказали, что данная проблема тоже алгоритмически неразрешима. Ъ.Проблема представимостиматриц. Пусть Ui,U2,-.,Ug - матрицы порядка п х п . Будем говорить о матрице U того же порядка, что она представима через U\,Ui,.-,Uq, если для некоторого целого положительного t и целых чисел г\,гъ...Г1 из ряда имеет место равенство U=U,,*Ur2*...*U,, Общая проблема представимости матриц. Дано целое положительное число п, требуется выяснить, существует ли алго­ ритм, посредством которого мояшо было бы узнавать для любой 249