Лекции 3—5. Формализация понятия алгоритма (1107980), страница 3
Текст из файла (страница 3)
Композиция нормальных алгоритмов Маркова.Композиция НАМ. Пусть у нас есть два НАМ R и S, работающих над исходным словомδ в некотором алфавите А. Фактически алгоритм R – некоторая функция f(δ), примененная к δ, а S – соответственно g(δ). Тогда их композиция есть суперпозиция функцийg(f(δ)). Как преобразовать правила, чтобы осуществить такую композицию? Отметим,что все это мы делаем для случая, когда R и S работают в одном алфавите A.В случае, когда оба алгоритма заканчиваются по правилу с ., решение имеет следующий вид.В R заменим .
на α.В S заменим любой символ ξ ∈ V∪V' на его «близнеца» ξ (ξ ∉ V∪V') во всех правилах.Кроме того в S заменим . на β. (α и β ∉ V∪V'). Расширим правила подстановок, добавив правила (для каждой пары символов ξ ∈ V и η ∈ V):ξα → αξ; αξ → αξ; ξη → ξη; (группа правил (1)); ξβ → βξ; βξ → βξ; ξη → ξη; (группаправил (2)); αβ → .; далее следуют правила вычисления S в «близнецовском» алфавите(система правил (3)), далее следуют правила вычисления R в алфавите V∪V' (системаправил (4)).Тогда последовательность применения правил будет такая. Поскольку исходное словоне содержит ни «близнецов», ни α, ни β, будет работать система правил (4).
Как тольковстретится правило, содержащее α (конечное правило R, так как метасимвол . замененна α) начнет выполняться группа правил (1): вначале произойдет вытеснение α в самую левую позицию слова (после работы (4) где-то в слове находится ровно одна α),затем символы будут преобразовываться в «близнецы», пока исходных символов в слове уже не будет. В близнецовском алфавите может работать только система правил (3).Система правил (3) будет выполняться до остановки S (символ β, заменивший .).
Кактолько в слове появится β, сработает правило αβ → ., стоящее раньше (3). Слово послевыполнения (2) содержит ровно одну β. Снова β будет вытесняться влево (пока не встанет рядом с α в начале слова), а затем каждый близнец заменится на исходный символ.Наконец, когда не останется ни одного близнеца, сработает правило αβ → .8(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год(остановка).
Результат есть g(f(δ)), где результат снова слово в алфавите V, не содержащее никаких вспомогательных символов («близнецов», α и β).В случае, когда один из алгоритмов заканчивается по ., другой (для определенности –первый) – потому что ни одно из правил неприменимо, нужно ввести в самом концееще одно правило → α. В общем случае, между группами правил (3) и (4) нужно добавить группу правил, которая слово ξ…ηα переводит в βξ…ηα.
Такая группа правиланалогична группе (1), при этом используется маркер γ.8.7. Алгоритмическая неразрешимость проверки свойства самоприменимости.8.7.1. Свойство самоприменимости. Пусть в некотором алфавите А = {a1, a2, ... an} задан НАМ U с помощью системы подстановок. Мы можем рассматривать записьсистемы подстановок как слово в алфавите А′ = {a1, a2, ... an, an+1, an+2, an+3}, гдеаn+1 = → , an+2 = , an+3 = . . Теперь применим систему подстановок U к слову, изображающему этот НАМ в алфавите А′. Если теперь U начнет перерабатывать этослово и остановится, то U будем называть самоприменимым, иначе – не самоприменимым.8.7.2.
Попытаемся построить такой НАМ W, который для любого слова в алфавите А′вырабатывает слово М, если это слово изображает самоприменимый алгоритм, ислово L, если алгоритм не самоприменим. Т.е. НАМ W распознает свойствосамоприменимости для любого слова в А′.Cнова «от противного». Предположим, что такой алгоритм W построен. Это значит, что в его системе правил есть правила ... →.
М (1) и ... →. L (2). Правило (1)срабатывает, когда алгоритм U самоприменим и (2), когда U – не самоприменим.Заменим теперь W на W′, заменив правило (1) на два правила {. M → αМ; α → α}(1′) : мы заменили . на α и добавили новое правило, которое зацикливает W′. Таким образом, алгоритм W′ зацикливается, если U - самоприменим, и вырабатывает L, если U – не самоприменим. Применяем теперь W′ к самому себе. Снова возможны два варианта:1. W′ - самоприменим: произойдет результативная остановка. Но тогда W′ - несамоприменим, поскольку вырабатывает слово L, которое и обозначает факт несамоприменимости.2.
W′ - не самоприменим: остановки не произойдет. Но ведь это как раз обозначает факт самоприменимости. Противоречие.8.8. Заключительные замечания8.8.1. Конечно, можно построить и универсальный НАМ U, который мог бы интерпретировать любой нормальный алгоритм, включая самого себя. Он строится приблизительно в той же манере, что и универсальная машина Тьюринга.8.8.2. Можно доказать эквивалентность двух формальных систем Тьюринга и Марковаконструктивным путем: построить универсальную МТ, которая могла бы интерпретировать любой НАМ и, наоборот, построить универсальный НАМ, которыйинтерпретирует любую МТ.8.8.3. Уже отмечалось, что решить задачу можно различными путями: существуют различные НАМ решения одной и той же задачи.
Конечно, важно уметь распознавать эквивалентность двух НАМ. Но проблема построения алгоритма, который9(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годможет определить эквивалентность любых двух НАМ, алгоритмически неразрешима.9. Об универсальных алгоритмах9.1.
Идея универсальных машин и алгоритмов широко используется в компьютерах. По существу программы (алгоритмы) почти никогда не пишутся в системе команд компьютера. Программы пишут программы для некоторой абстрактной машины (например,Си-машины, которая изучается в данном курсе). Программа переносится на реальныйкомпьютер некоторым алгоритмом (компилятором), причем такой перенос, как правило, является многоступенчатым (т.е. с использованием некоторых промежуточных интерпретаторов). В процессе компиляции многократно производится преобразованиеинформации из одного представления в другое. Причем все эти представления ориентированы на бесконечные машины.9.2.
Но реальный компьютер и реальный интерпретатор (Си) – конечные машины: все видыих памяти конечны (более того, известны их верхние границы). На конечных машинахвозникает новый тип останова, когда для выполнения программы не хватает памяти.На самом деле так было бы и для МТ, если бы лента МТ, была ограничена.9.3. В этой связи алгоритмическая неразрешимость утрачивает смысл. Действительно, этипроблемы связаны с бесконечностью ленты Тьюринга (хотя любая машина используетконечное число клеток ленты, но всегда найдется машина, которая использует на клетку больше – нет верхней границы), аналогично, со словом в алгоритмах Маркова.Вспомним также суммирование неизвестного количества чисел, находящихся на неизвестном (но конечном) расстоянии друг от друга.
На конечной ленте нет такой проблемы. Действительно, поскольку в компьютере конечное число клеток (битов) памяти, то,следовательно, на нем в принципе может быть только конечное число программ (алгоритмов), хотя фактически большое ≈ n!, где n - число битов. И казалось бы нам удаетсяизбежать такой опасности как неразрешимость. Но там нас подстерегает другая беда –сложность.
Ведь опасность может быть в объеме памяти, когда нельзя выполнить программу на данном компьютере из-за нехватки памяти. Другая опасность – время. Неимеет смысла иметь программу расчета траектории ракеты, если за время вычисленияракета уже попадет в цель и, следовательно, ее нельзя будет поразить противоракетой.Факт временной сложности используется широко, например, в системе защиты информации.
Конечно, в криптографии любой шифр может быть потенциально раскрыт, ноесли дешифровка требует полмиллиона лет суммарной работы всех компьютеров вмире, то шифр можно считать абсолютно надежным. Через полмиллиона лет зашифрованное письмо просто утратит всякий смысл.9.4. Поэтому при составлении программы для компьютера, необходимо оценивать ее временную и пространственную сложность (сложность исследуется и в формальных системах, но для реальных программ – это жизненно необходимо).
Необходимо иметьхотя бы грубые оценки сложности составляемых и применяемых программ. Более тонкие оценки дают возможность сравнивать между собой эквивалентные программы инаходить среди них подходящие (а иногда и наиболее подходящую) для данных условий.10(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
