Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (793777), страница 4
Текст из файла (страница 4)
На двух из них мы остановимся подробнее. Несмотря на различия,каждый из этих двух способов основан на идее исключения из формального описанияалгоритма какой-либо содержательной информации, касающейся целей и смысла каксамого алгоритма, так и операций, выполняемых на его отдельных шагах.Реализация этой идеи, на первый взгляд, входит в противоречие с интуитивнымпредставлением об алгоритмах.
Разные алгоритмы предназначены для отыскания решенийразнообразных задач, в то же время каждый конкретный алгоритм может бытьпредназначен лишь для обработки исходных данных лишь определенного типа. Так,алгоритм Евклида, обрабатывает пару натуральных чисел и исходное слово для этогоалгоритма должно изображать эту пару. Для исходных данных, не задающих парунатуральных чисел, алгоритм Евклида теряет смысл. Ориентация конкретного алгоритмана определенный тип исходных данных может выражаться явными требованиями к ним ив ограничениях, вытекающих из описания операций, предусмотренных в шагах алгоритма.Обнаружение нарушения этих требований и ограничений естественно расценивать, какнеприменимость алгоритма. Однако такой подход можно признать приемлемым только втом случае, когда обнаружение нарушений требований и ограничений, о которыхговорится выше, достигалось бы, так сказать, алгоритмически.
То есть, в результатепредварительного алгоритма распознавания допустимости исходных данных и далее впроцессе выполнения шагов алгоритма при помощи каких-то простых операций,включенных в эти шаги. Все эти дополнения разумно считать неотъемлемой частьюалгоритма.В такой ситуации формально исчезает отличие успешного окончания процессавыполнения алгоритма от его неудачного завершения.
Отличие между такимизавершениями обнаруживается только при содержательном рассмотрении результата. На12первый взгляд, заманчиво ввести в понятие алгоритма два типа окончаний - "нормальное"(результативное) и "аварийное" (нерезультативное). Однако на этом пути возникают двасущественных замечания. Во-первых, нет оснований формально ограничиваться лишьдвумя типами окончаний.
Во-вторых, расширяя таким образом понятие алгоритма, мыостаемся с тем же классом частичных отображений на множестве слов (A*) конечногоалфавита (А), что и при исходном понятии алгоритма. Это так, потому что каждомуалгоритму F, реализующему частичное отображение:A*А*можно сопоставить эквивалентный алгоритм f, который не завершается ни на одном слове( v), не принадлежащем области его определения (v ∈ А*, но v∉ В ⊂ A*, где В - областьопределения F). В самом деле, каждый алгоритм с "аварийными" завершениями можетбыть превращен в эквивалентный ему алгоритм без "аварийных" завершений. Для этогодостаточно каждое предписание об "аварийном" окончании заменить предписанием опереходе к выполнению бесконечного цикла, предварительно включив такой цикл вописание алгоритма как один из его шагов.Таким образом, мы можем избавиться от "аварийных" (нерезультативных),"нормальных" (результативных) и других вариантов окончаний алгоритма.
И без потериобщности можем ограничиться лишь рассмотрением и исследованием алгоритмов, длякаждого из которых область определения (применимости) совпадает с множеством слов,исходя из которых он завершается после выполнения конечного числа шагов. А областьюнеприменимости оказывается множество всех слов, исходя из которых алгоритм незавершается (зацикливается). Рассматривая только такие алгоритмы, мы избавляемся оттрудностей, связанных с содержательным рассмотрением исходных данных и результатовалгоритма, а также открываем путь для максимального упрощения промежуточных шагови отказа от содержательных рассмотрений.Другими словами, абстрагируясь от конкретного содержания решаемых с помощьюалгоритмов задач, мы сводим все такие задачи к нахождению слова - "ответа" позаданному слову - "исходным данным".
И, в соответствии с этим, рассматриваемалгоритмы, как процессы преобразования конечных слов в конечном алфавите. Такиедостаточно формализованные процессы мы вправе считать эквивалентными общемупонятию алгоритма.Перейдем к рассмотрению двух способов формализации понятия алгоритма. Первымрассмотрим подход Тьюринга - Поста.5.1. МАШИНА ТЬЮРИНГААнглийский математик Алан Тьюринг в 1936 году предложил формальноеопределение понятия алгоритма, получившее впоследствии название "машина Тьюринга".Основная идея предложенного Тьюрингом подхода к уточнению понятия алгоритма,заключается в том, что алгоритмами должны называться те и только те отображения намножестве слов, которые могли бы осуществлять достаточно простые машины автоматы. Выполнение отображения понимается при этом следующим образом.
Машине автомату предъявляется любое исходное слово, а она "выдает" слово, являющееся образомисходного слова при данном отображении.Если предъявление исходного слова должно предшествовать полностью автономнойработе машины, то последняя должна обладать устройством, на котором можно было бызафиксировать любое сколь угодно длинное слово.
Неограниченная лента, пожалуй, самоепростое из таких воображаемых устройств.13Машина Тьюринга работает с лентой, разбитой на равновеликие ячейки, и имеет всвоем "устройстве" управляющую головку (УГ), мимо которой может протягиватьсялента.УГЛЕНТАΛΛСЛОВОΛΛΛПри остановке ленты перед управляющей головкой оказывается одна из ячеек. Лентапротягивается шагами на одну ячейку в любую сторону. Конечно, можно считать, что отячейки к соседней ячейке продвигается управляющая головка, а лента остаетсянеподвижной.
Мы будем предполагать, что лента неограниченна в обе стороны, хотяэквивалентные результаты получаются, если считать, что лента ограничена с одной изсторон.Можно считать, что лента конечна, но дополняема, т.е. что каждый раз, когдавозникает потребность в протяжке ленты на шаг, выводящий за один из концов ленты, кпоследней "приклеивается" дополнительный кусок. Вместо "приклеивания" можнопредставлять себе, что в этом случае в лентопротяжный механизм ставится другая лента,которая становится продолжением снятой ленты.
Лента машины в процессе работыпревращается в последовательность лент, число которых может расти. Такая работадолжна поддерживаться дополнительными возможностями машины. В частности, машинадолжна реагировать на ситуацию "выход за конец ленты" и выдавать соответствующийсигнал, приостанавливая протяжку и дожидаясь сигнала для ее продолжения.В каждой ячейке ленты может быть записан любой символ из связанного с данноймашиной Тьюринга конечного алфавита А ={ a 1 , a 2 , ...
, a p }, называемого внешнималфавитом машины. К алфавиту А присоединяется специальный символ "пустоты",который для определенности мы будем обозначать Λ. Расширенный таким образомалфавит будем обозначать Ã. Считается, что в каждой ячейке ленты, в которую не былзаписан никакой символ из Ã, записан символ Λ. При записи любого символа из à вкакую-либо ячейку ленты, ранее записанный в нее символ, исчезает. Запись символов из вà ячейки ленты может быть произведена как перед началом работы машины, так и впроцессе ее работы. В каждый момент только в конечном числе ячеек ленты могут бытьзаписаны символы, отличные от Λ. Говоря о записи на ленту машины слова w из Ã*, мыбудем понимать запись последовательности составляющих слово w символов впоследовательно расположенные слева - направо ячейки ленты машины.Управляющая головка является устройством, способным находиться в любом изконечного множества внутренних состояний.
Эти состояния будем помечать некоторымисимволами ( q 0, q 1, ..., q s), составляющими внутренний алфавит Q ={ q 0, q 1, ..., q s }машины Тьюринга. Среди состояний управляющей головки имеются два особыхсостояния - состояние останова и состояние, называемое начальным. Для определенностибудем считать, что останов помечен символом q s, а начальное состояние - символом q 0.Управляющая головка, находясь в отличном от останова состоянии, способнавоспринимать символ, записанный в расположенную перед ней ячейку, записывать в этуячейку любой символ из Ã, изменять свое состояние и выдавать сигналы для протяжкиленты на одну ячейку. Оказавшись в состоянии останова, управляющая головка выдаетсигнал конца работы. Перед началом работы машины Тьюринга на ее пустую лентузаписывается слово, которое мы будем называть исходным.14Работа машины Тьюринга начинается по сигналу "пуск", инициируемому извне,например, нажатием кнопки, и распадается на последовательность тактов.
Начало каждоготакта определяется специальным сигналом, возникающим через определенныепромежутки времени. Сигнал "пуск" переводит головку в начальное состояние q 0 изапускает генератор сигналов начала такта. По сигналу начала такта управляющая головка(если она не находится в состоянии останова) распознает символ, записанный воказавшейся перед ней ячейке ленты, и конкретизирует свои действия в текущем тактеработы.
То есть, "решает" - какой символ из Ã следует записать в стоящую перед головкойячейку, в какое новое состояние перейти и, наконец, какой сигнал выдатьлентопротяжному механизму. Эти решения должны однозначно определяться парой(q i, a j) - текущим состоянием управляющей головки q i и распознанным символом a j вобозреваемой ячейке ленты.
После выполнения выбранных действий и прошествиинекоторого промежутка времени, достаточного для протяжки ленты, согласно выданномусигналу, снова возникает сигнал начала такта, и т.д. Такая работа продолжается до техпор, пока управляющая головка не окажется в состоянии останова (q s). Слово,оказавшееся при этом на ленте, называется выходным словом и считается результатомработы машины. Если такого не случится, то машина будет работать без конца, исчитается, что машина не применима к соответствующему исходному слову. Заметим, чтовнутри исходного слова и внутри слова - результата не должен содержаться символ Λ.В каждом такте "поведение" машины Тьюринга или ее работа определяетсязначениями трех функций: φ(q i, a j), ψ(q i, a j) и δ(q i, a j ), заданных на конечноммножестве Q' x à и принимающих, соответственно, значения из Q, из à и из S = {R, L},где R - сигнал протяжки для подвода к головке следующей (правой) ячейки ленты, а L сигнал для подвода предыдущей (левой) ячейки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
