НормальныеАлгоритмы Маркова.Построение алгоритмов из алгоритмов.
В 1956 году отечественным математикомА.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднеебыло названо его именем.
В этом уточнении выделенные нами 7параметров были определены следующим образом:
Совокупность исходных данных — слова валфавите S;
Совокупность возможных результатов — слова в алфавите W;
Совокупность возможных промежуточныхрезультатов — слова в алфавите
Р=S/>W/>V,где V — алфавит служебных вспомогательных символов.
Действия:
Действия имеют вид либо a®g,либо a a g,где a, g ÎP*, где
P* — множество слов над алфавитом Р, и называется правилом подстановки. Смысл этогоправила состоит в том, что обрабатываемое слово w просматривается слеванаправо и ищется вхождение в него слова a.
Определение.3.1. Слово aназывается вхождением в слово w, если существуют такие слова b и n надтем же алфавитом, что и a и w, для которых верно: w=ban.
Если вхождение a в wнайдено, то слово a заменяется на слово g.
Все правила постановки упорядочиваются.Сначала ищется вхождение для первого правила подстановки. Если оно найдено, топроисходит подстановка и преобразуемое слово опять просматривается слеванаправо в поисках вхождения. Если вхождение для первого правила не найдено, тоищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотрправил начинается с первого, а слово просматривается сначала и слева направо.
Вся совокупность правил подстановкиназывается схемой алгоритма.
Правило начала — просмотр правил всегданачинается с первого.
Правило окончания — выполнение алгоритмазаканчивается, если:
было применено правило подстановки вида a a g,
не применимо ни одно правило подстановкииз схемы алгоритма.
7. Правило размещения результата — слово, полученное после окончания выполнения алгоритма.
Рассмотрим пример 1 из лекции 2:
построить алгоритм для вычисления
U(n)=n+1;
S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.
Cхемаэтого НАМ показана на рисунке 3.1.
/>
Перегоняем служебный символ * в конец слова n, чтобы отметить последнюю цифру младших разрядов.
Увеличиваем на единицу, начиная с цифр младших разрядов.
/> Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.
Рис.3.1. Схема НАМ для вычисления U1(n)=n+1
Нетрудно сообразить, что сложностьэтого алгоритма, выраженная в количестве выполненных правил подстановки, будетравна:
(k+1)+(l+1),
где k — количество цифр в n, l — количество 9, которые были увеличены на 1.
Но в любом случае сложность НАМ для U1(n) больше сложности Машины Тьюринга для этой же функции, котораяравнялась k+1.
Обратите внимание, что у НАМ порядокследования правил подстановки в схеме алгоритма существенно влияет нарезультат, в то время как для МТ он не существеннен.
Построим НАМ для примера 2 из лекции 2:
построить алгоритм для вычисления
U2((n)1)=(n-1)1
Итак,S={|}; W=S; V=Æ, т.е. пусто.
| a
Cложностьэтого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюрингаравнялась n.
Теперь построим НАМ для примера 3 излекции 2:
построить алгоритм для вычисления
U3((n)1)=(n)10
S={|}; W={0,1,2,3,4,5,6,7,8,9}; V=Æ
Схема этого алгоритма приведена нарисунке 3.2.
1|®2
2|®3
3|®4
4|®5
5|®6
6|®7
7|®8
8|®9
9|®|0
|0®10
0|®1
|®0|
Рис. 3.2. Схема НАМ для вычисления U3((n)1)=(n)10.
Сложность этого НАМ будет n+[log10n], что существенно меньше сложности для Машины Тьюринга,вычисляющей эту функцию, которая равнялась n2+[log10n(log10n+1)].
Реализацию функции U4 сравнения двух целых чисел оставляем читателю в качествеупражнения.
Замечание: исходное слово надо задать вформе /> * />
Для нормальных алгоритмов Марковасправедлив тезис, аналогичный тезису Тьюринга.
Тезис Маркова: Для любой интуитивновычислимой функции существует алгоритм, ее вычисляющий.
Построение алгоритмов из алгоритмов.
До сих пор, строя ту или иную МТ, илиНАМ мы каждый раз все делали заново. Естественно задать вопрос, а нельзя ли припостроении, например, новой МТ пользоваться уже построенной ранее МТ.
Например, МТ3 из примера 3
U3((n)1)=(n)10
по существу есть надлежащим образомобъединенные МТ для U1(n)=n+1 и U2((n)1)=(n-1)1.
Аналогичный вопрос можно сформулироватьдля НАМ. Другими словами можно ли аккумулировать знания в форме алгоритмов так,чтобы из них можно было строить другие алгоритмы.
Мы рассмотрим эту проблемуприменительно к МТ. Однако все сформулированные нами утверждения будутсправедливы и для НАМ и для других эквивалентных уточнений понятия алгоритма.Эквивалентость уточнений понятия алгоритма мы рассмотрим позже.
Определение.3.2.Будем говорить, что МТ1 можно эффективно построить изМТ2 и МТ3 если существует алгоритм, который позволяет,имея программу для МТ2 и МТ3, построитьпрограмму для МТ3.
Определение.3.3.Последовательнойкомпозицией МТ А и В называется такая МТ С, что
область применимости МТ А и С совпадают;
C(a)=B(A(a)).
Другими словами, применение С к слову aдает такой же результат, как последовательное применение к этому же словусначала А, а потом к результату применения А — В.
Последовательную композицию МТАи МТВ будем обозначать АoВ.
Теорема 3.1. Пусть даны МТ А и В, такие,что В применима к результатам работы А и QA/>QB=Æ.
Тогда можно эффективно построить МТ Стакую, что С= АoВ.
Доказательство.
В качестве алфавита данных и множествасостояний для МТС возьмем объединение алфавитов данных и множествсостояний для А и В, т.е.
DC=DA/>DВ, QC= QA/>QB
В программе для А все правила ap®b!w, где a,bÎDA*, wÎ{Л,П, Н} заменим на ap®bqoBw, где qoBÎ QB — начальное состояние для В. Этообеспечит включение В в тот момент, когда А свою работу закончила и не раньше,т.к. QA/>QB=Æ.
Что и т.д.
Табличная запись программы для Споказана на рисунке 3.3.
/>
Рис 3.3 Структура табличной записипрограмм для Машины С.
Определение3.4. Параллельнойкомпозицией Машин Тьюринга А и В назовем такую МашинуС, для которой:
DC=DA/>DB
QC=QA/>QB
C(a||b)=A(a||b)°B=B(a||b)°A=A(a)||B(b).
Из этого определения видно, что порядокприменения МТА и МТВ не влияет на результат. Он будет такой же как если бы мынезависимо применили А к слову a, а В к слову b.
Теорема 3.2 Для любых МТ А и МТ Вможно эффективно построить МТ С такую, что С=А||В
Обоснование. Мы не будем давать здесьстрого доказательства в виду его технической сложности. Покажем лишьобоснование правильности утверждения теоремы. Обозначим DC=DA/>DB; QC=QA/>QB.
Основная проблема: какгарантировать чтобы А не затронула слово b, а В — слово a. Для этого введем в алфавит DС символ||. Добавим для всех состояний qiÎQCтаких,что qiÎQA правила вида ||qi®||qiЛ, т.е. каретка машины Абудет, натыкаясь на символ ||, уходить влево.Соответственно для всех qjÎQC таких,что qjÎQB добавим правила вида ||qj®||qjП, т.е. каретка машины В будет уходитьвправо. Тем самым мы как бы ограничиваем ленту для Асправа, а для В слева.
Существенным здесь является вопрос: неокажутся ли вычислительные возможности Машины Тьюринга с полулентой слабее, чемвычислительные возможности Машины Тьюринга с полной лентой?
Оказывается справедливо следующееутверждение: множество алгоритмов, реализуемых МТ с полулентой, эквивалентномножеству алгоритмов, реализуемых МТ с полной лентой.Обозначим Ф(Р) Машину Тьюринга, реализующую распознающий алгоритм:
/>
Теорема 3.3. Для любых МашинТьюринга А, В и Ф, имеющих один и тот же алфавит S,может быть эффективно построена машина С над тем же алфавитом S, такая что
/>
Доказательство.
Обозначим: E(Р)тождественную машину, т.е. Е(Р)=Р
СOPY(Р)копирующую машину, т.е. СOPY(Р)=Р||Р,
где ||ÏS.
BRANCH(P) — эта машина переходит либо в состояние р1, либо всостоянии ро. Ее программа состоит из 4-х команд:
1qo®1р1П
||р1®||р1П
0qo®0роП
||ро®||роП
Построим машину
/>
Эта машина строится по следующейформуле:
/>
Согласно теоремам 3.1 и 3.2., мы можемпостроить машину />, зная Е, Ф и COPY. Теперь, имея />, BRNCH, A и В, можно построить машину С следующим образом:
Машина />o BRANCH заканчивает свою работу либо в состоянии р1, если слово P обладает нужным свойством, либо в состоянии ро,находясь в начале слова P.Поэтому, если принять у машины А состояние р1, как начальное, а умашины В состояние ро, как начальное, то машина А будет включена приусловии, что Ф(Р)=1, а машина В будет включена, если Ф(Р)=0.
Правило композиции, определяемое этойтеоремой будем записывать, если Ф то А иначе В.
Теорема 3.4. Для любых машин А и Фможно эффективно построить машину Lтакую, что
L(P)={ Пока Ф(Р)=1, применяй А }
Доказательство: Заменим в доказательстветеоремы 3.3. машину В машиной Е, а заключительное состояние в машине В заменимна начальное состояние в машине />. В итоге получим нужный результат.
Теорема 3.5. (Бомм, Джакопини, 1962)
Любая Машина Тьюринга может бытьпостроена с помощью операции композиций o, ||, если Ф, то А иначе В,пока Ф применяй А.
Эту теорему мы даем здесь бездоказательства.
Следствие 3.1. В силу Тезиса Тьюринга,любая интуитивно вычислимая функция может быть запрограммирована в терминахэтих операций.
Следствие 3.2 Мы получили что-то вродеязыка, на котором можно описывать новую Машину Тьюринга, используя описания ужесуществующих, а затем, используя теоремы 3.1 — 3.4, построить её функциональнуюсхему.
Следствие 3.3 Алгоритм — этоконструктивный объект. В случае Машины Тьюринга атомарными объектами являютсякоманды, а теорема 3.5 определяет правила композиции.
Выводы:
Алгоритм — конструктивный объект;
Алгоритм можно строить из другихалгоритмов;
o, ||, if_then_else, while_do — универсальный набор действий поуправлению вычислительным процессом.
Вопросы :
Что такое правило подстановки?
Зависит ли результат от порядкаследования правил в НАМ?
Что происходит когда не применимо ни одно правило подстановки?
Что утверждает тезис Маркова?
Можно ли доказать тезис Маркова?
Семантика операции o?
Семантика операции ||?
Семантика операции if_then_else?
Семантика операции while_do?
Что такое конструктивный объект?
Алгоритм — это конструктивный объект?
Списоклитературы
Для подготовки данной работы былииспользованы материалы с сайта www.ergeal.ru/