Универсальный алгоритм

Лекция 11 Универсальный алгоритм Для получения некоторых результатов теории алгоритмов полезно понятие универсального алгоритма. Пусть зафиксирован некоторый способ кодирования алгоритмов, который устанавливает взаимно однозначное соответствие между алгоритмом Al и его кодом K(Al). Алгоритм U назовем универсальным, если он по входу K(Al)X строит выход алгоритма Al на входе X. Если алгоритм Al не применим к входу X, то и алгоритм U не применим к входу K(Al)X. Возможность построения универсального алгоритма, вообще-то, достаточно очевидна. Однако, само построение универсального алгоритма связано с достаточно утомительными построениями. Здесь, попытаемся преодолеть эти трудности и построить универсальный алгоритм. В качестве исходной модели алгоритма возьмем машину Тьюринга с бинарным алфавитом {0,1}. Опишем способ кодирования моделируемой программы. Запишем ее в виде последовательности команд, разделенных символами a или b. Символ b будет расположен перед активной (т.е. моделируемой в данный момент) командой и перед всеми командами, расположенными левее ее. Символ a будет стоять перед всеми командами, расположенными правее активной и после последней команды. В начальный момент символ b будет расположен только перед первой командой. Отдельная команда имеет вид . Символы определяют действие, которое должно выполнится универсальным считывающим устройством: 0 - печать пустого символа, 00 – печать 0, 01 – печать 1, 1 - сдвиг указателя влево, 10 – сдвиг указателя вправо, 11 – указатель оставить на месте. Символы равны либо 0, либо 1 и определяют следующую команду в зависимости от считанного символа. В зависимости от символа в обозреваемой ячейке , 0, 1, следующая команда определяется словом , , . При этом слово означает, что следующая команда расположена на k-1 команд левее, а слово означает, что следующая команда расположена на k команд правее. Если ни одного из этих слов нет, то это означает, что следующей команды нет, а текущая команда является выходной. Сразу за кодом программы запишем символ c, указывающий обозреваемую ячейку и входное слово X. Признаком конца входного слова является символ a. Входным словом алгоритма U, согласно приведенному описанию будет слово вида . Кроме символов a, b, c алгоритм будет использовать символ d. Прежде чем приступить к построению универсального алгоритма расширим математическое обеспечение. 1. Поиск символа h справа от обозревателя FR(h): . Граф программы приведен Error: Reference source not found. 2. Поиск символа h слева от курсора FL(h): . Граф программы приведен Error: Reference source not found 3. Сдвиг слова на одну позицию вправо R1. По сути, действие программы описывается подстановкой . Положение обозревателя помечено крышкой. Программа имеет вид . Граф программы приведен Error: Reference source not found. Перейдем к составлению программы универсального алгоритма. 1. Найти символ c, определяющий положения обозревателя в моделируемой программе. Запомнить символ, стоящий справа от символа c (этот символ обозревается моделируемой программой). Затем, вернуться к символу b и найти относительное положение следующей команды, пометить его символом d (подготовить переход в следующее состояние). Программа имеет следующий вид. [FR(c),r,(если )[FL(b),r,r,r,d] (если a)[FL(b),r,r,r,d] (если 0)[FL(b),r,r,r,FR(),d] (если 1)[FL(b),r,r,r,FR(),r,FR(),d]]. 2. Найти исполняемую команду (т.е. символ b), прочитать команду для универсального считывающего устройства, записанную в двух символах справа, найти c и выполнить считанную команду. [FL(b),r,(если 0)[r,(если )[FR(c),r,(если a)[r,a,l],] (если 0)[FR(c),r,(если a)[r,a,l],0] (если 1)[ FR(c),r,(если a)[r,a,l],1]] (если 1)[r,(если )[FR(c),r,(если a)[l,,c,a] (если )[l,,c] (если 0)[l,0,c] (если 1)[l,1,c]] (если 0)[FR(c),l,(если a)R1 (если )[c,r,] (если 0)[c,r,0] (если 1)[c,r,1]] (если 1)FR(c)]]. 3. Вернуться к исполняемой команде и осуществить переход к новой исполняемой команде. [FL(d),,r,(если 0)[(пока 0)[d,FR(a),b,FL(d),0,r],FR(a),FL(b)](если 1)[r,(пока 1)[d,FL(b),a,FR(d),1,r],FL(b)] (если )[конец]]. Граф программы универсального алгоритма приведен на Error: Reference source not found. Построим такую схему S по универсальному алгоритму (Error: Reference source not found), что вопрос о распознавании слова алгоритмом сводится к вопросу эквивалентности слов в построенной схеме S. Поскольку универсальный алгоритм моделирует работу любого алгоритма (см. Error: Reference source not found), то задача распознавания слов алгоритмами сводится к проверке эквивалентности слов в схеме S. Так как задача распознавания слов алгоритмом является алгоритмически не разрешимой, то и задача проверки эквивалентности слов в схеме S является алгоритмически неразрешимой. Оформим полученное утверждение в виде следствия. Следствие 1 Существует конкретная схема, что проверка эквивалентности слов в этой схеме является алгоритмически не разрешимой задаче1.