Нормальные алгоритмы Маркова

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

“Московский государственный технический университет радиотехники, электроники и автоматики”

МГТУМИРЭА

Кафедра вычислительной техники

Курсовая работа

по дисциплине «Дискретная математика»

На тему: «Нормальные алгоритмы Маркова»

Студент группы Шамхалов Э.К.

Махачкала 2013 г.

Содержание

Введение

1. Неформальное понятие алгоритма

2. Основные требования к алгоритмам

3. Необходимость в математическом уточнении понятии алгоритма

4. Нормальные алгоритмы Маркова

4.1 Марковские подстановки

4.2 Нормальные алгоритмы и их применение к словам

4.3 Нормально вычислимые функции и принцип нормализации Маркова

4.4 Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу

5. Присоединяющие алгоритмы

6. Сокращающие алгоритмы

7. Разветвляющий алгоритм

8. Удваивающий алгоритм

9. Применение теории нормальных алгоритмов к решению практических задач

Заключение

Литература

Введение

Понятие алгоритма формировалось с древнейших времен, но до конца первой трети XX в. математики довольствовались интуитивным представлением об этом объекте. Термин «алгоритм» употреблялся в математике лишь в связи с теми или иными конкретными алгоритмами. Утверждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием.

Парадоксы, обнаруженные в основаниях математики в начале XX в., вызвали к жизни различные концепции и течения, при- званные эти парадоксы устранить. В 1920-е гг. вплотную встали вопросы о том, что же такое строгая выводимость и эффективное вычисление. Понятие алгоритма само должно было стать объектом математического исследования и поэтому нуждалось в строгом определении. Кроме того, к этому вынуждало развитие физики и техники, быстро приближавшее начало века электронно-вычислительных машин.

Далее, у математиков начали возникать подозрения в том, что некоторые массовые задачи, по-видимому, не имеют алгоритмического решения. Для точного доказательства несуществования какого-то объекта необходимо иметь его точное математическое определение. Совершенно аналогичная ситуация сложилась в свое время в математике, когда назрела необходимость уточнения таких понятий, как непрерывность, кривая, поверхность, длина, площадь, объем и т.п.

Первые работы по уточнению понятия алгоритма и его изучению, т.е. по теории алгоритмов, были выполнены в 1936--1937 гг. математиками А. Тьюрингом, Э. Постом, Ж. Эрбраном, К. Гёделем, А.А. Марковым, А. Чёрчем. Было выработано несколько определений понятия алгоритма, но впоследствии выяснилось, что все они равносильны между собой, т.е. определяют одно и то же понятие.

В данной работе более подробно рассмотрены одна из алгоритмических моделей понятия алгоритма - нормальные алгоритмы Маркова. Целью работы является изучение теории названных алгоритмов. Для реализации поставленной цели необходимо решить следующие задачи:

1) рассмотреть понятие алгоритма и его основные свойства;

2) показать необходимость в математическом уточнении понятии алгоритма;

3) рассмотреть примеры применения нормальных алгоритмов;

4) охарактеризовать некоторые виды нормальных алгоритмов, такие как присоединяющие алгоритмы, сокращающие алгоритмы, разветвляющие алгоритм, удваивающие алгоритмы;

5) сконструировать нормальные алгоритмы для решения некоторых видов арифметических задач.

1. Неформальное понятие алгоритма

С алгоритмами, т. е. эффективными процедурами, однозначно приводящими к результату, математика имела дело всегда. Школьные методы умножения «столбиком» и деления «углом», метод исключения неизвестных при решении системы линейных уравнений, правило дифференцирования сложных функций, способ построения треугольника по трем заданным сторонам -- все это алгоритмы. Однако пока математика имела дело в основном с числами и вычислениями и понятие алгоритма отождествлялось с понятием метода вычисления, потребности в изучении самого этого понятия не возникало. Традиции организации вычислений складывались веками и стали составной частью общей научной культуры в той же степени, что и элементарные навыки логического мышления. Все многообразие вычислений комбинировалось из 10-15 четко определенных операций арифметики, тригонометрии и анализа. Поэтому понятие метода вычисления считалось изначально ясным и не нуждалось в специальных исследованиях.

До середины XIX в. единственной областью математики, работавшей с нечисловыми объектами, были геометрия, и как раз она, не имея возможности опираться на вычислительную интуицию человека, резко отличалась от остальной математики повышенными требованиями к строгости своих рассуждений.

К новым, более жестким требованиям строгости началось в математике во второй половине XIX века. Оно стимулировалось в основном математикой нечисловых объектов -- открытием неэвклидовой геометрии, появлением абстрактных алгебраических теорий типа теорий групп и т. д. Одним из решающих обстоятельств, приведших к пересмотру оснований математики, т. е. принципов, лежащих в основе математических рассуждений, явилось создание Г. Кантором теории множеств. Довольно быстро стало ясно, что понятия теории множеств в силу своей общности лежат в основе всего здания математики. Однако почти столь же быстро было показано, что некоторые кажущиеся вполне естественные рассуждения в рамках этой теории приводят к неразрешимым противоречиям -- парадоксам теории множеств. Все это потребовало точного изучения принципов математических рассуждений (до сих пор казавшихся интуитивно ясными) математическими же свойствами. Возникла особая отрасль математики - основание математики или метаматематика.

Опыт парадоксов теории множеств научил математику крайне осторожно обращаться с бесконечностью и по возможности даже о бесконечности рассуждать с помощью финитных методов. Сущность финитного подхода заключается в том, что он допускает только конечный набор действий над конечным числом объектов. Выявление того какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью -- все это стало предметом теории алгоритмов и формальных систем, которая первоначально возникла в рамках математики и стала важнейшей её частью. Главным внутриматематическим приложением теории алгоритмов явилось доказательство невозможности алгоритмического (т. е. точного и однозначного) решения некоторых математических проблем. Такие доказательства (да и точные формулировки доказываемых утверждений) неосуществимы без точного понятия алгоритма.

Пока техника использовала вычислительные методы, эти высокие проблемы чистой математики ее мало интересовали. В технику термин «алгоритм» пришел вместе с кибернетикой. Если понятие метода вычисления не нуждалось в пояснениях, то понятие процесса управления пришлось вырабатывать практически заново. Понадобилось осознавать, каким требованиям должна удовлетворять последовательность действий (или ее описание), чтобы считаться конструктивно заданной, т. е. иметь право называться алгоритмом. В этом осознании огромную помощь инженерной интуиции оказала практика использования вычислительных машин, сделавшая понятие алгоритма ощутимой реальностью. С точки зрения современной практики алгоритм -- это программа, а критерием алгоритмичности процесса является возможность его запрограммировать. Именно благодаря этой реальности алгоритма, а также потому, что подход инженера к математическим методам всегда был конструктивным, понятие алгоритма в технике за короткий срок стало необычайно популярным (быть может, даже больше, чем в самой математике).

Плохо то, что в повседневной практике слово «алгоритм» употребляется слишком широко, теряя зачастую свой точный смысл. Приблизительные описания понятия «алгоритм». В результате за алгоритм зачастую выдаётся любая инструкция, разбитая на шаги. Появляются такие дикие словосочетания как «алгоритм изобретения».

Ясное представление о том, что такое алгоритм, важно конечно, не только для правильного словоупотребления. Оно и важно при разработке конкретных алгоритмов, особенно когда имеется ввиду их последующие программирование. Чтобы ориентироваться во всех алгоритмах, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству решений, но и по характеристикам самих алгоритмов. Такое сравнение невозможно без введения точного языка для обсуждения всех этих вопросов, иначе говоря, сами алгоритмы должны стать такими же предметами точного исследования, как и те объекты, для работы с которыми они предназначены.

2. Основные требования к алгоритмам

Несмотря на обилие разнообразных алгоритмов существуют общие типичные черты характерные для каждого из них.

1. Алгоритм -- это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задаётся исходная конечная система величин, а в каждый следующий момент система величин, получается, по определённому закону (программе) из системы величин, имевшихся в предыдущий момент времени (дискретность алгоритма);

2. Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени (детерминированность алгоритма);

3. Закон получения последующей системы величин из предшествующей должен быть простым и локальным (элементарность шагов алгоритма), типичный пример множества элементарных действий -- система команд ЭВМ;

4. Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма (результативность алгоритма);

5. Начальная система величин может выбираться из некоторого потенциально бесконечного множества (массовость алгоритма).

Понятие алгоритма, в какой-то мере определяемое этими требованиями, конечно, нестрогое: в формулировках требований встречаются слова «способ», «величина», «простой», «локальный», точный смысл которых не установлен. В дальнейшем это нестрогое понятие алгоритма будет называться непосредственным или интуитивным понятием алгоритма.

Комментарии к описанным требованиям. Любой алгоритм применяется к исходным данным и выдает результат. В привычных технических терминах это означает, что алгоритм имеет входы и выходы. Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данными -- входными, промежуточными и выходными. Поскольку мы собираемся уточнять понятие алгоритма, нужно уточнить и понятие данных, т. е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать.

Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». Во многих случаях хорошо понятно, что это значит: к таким алгоритмическим объектам относятся числа, векторы, матрицы смежностей графов, формулы. Изображения (например, рисунок графа) представляются менее естественными в качестве алгоритмических объектов. Если говорить о графе, то дело даже не в том, что в рисунке больше несущественных деталей и два человека одни и тот же граф изобразят по-иному (в конце концов, разные матрицы смежности тоже могут задавать одни и тот же граф с точностью до изоморфизма, а в том, что матрица смежности легко разбивается на элементы, причем из элементов всего двух видов (нулей и единиц) строят матрицы любых графов, тогда как разбить на элементы рисунок гораздо труднее. Наконец с такими объектами, как хорошая книга или осмысленные утверждения, с которыми легко управляется любой человек (но каждый по своему), алгоритм работать не сможет, пока они не будут описаны как данные с помощью других, более подходящих объектов.

Вместо того чтобы пытаться дать общее словесное определение четкой определенности объекта, в теории алгоритмов фиксируют конкретные конечные наборы исходных объектов (называемых элементарными) конечный набор средств построения других объектов из элементарных. Набор элементарных объектов образует конечный алфавит исходных символов (цифр, букв, и т.д.), из которых строятся другие объекты.

Типичным средством построения являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Простейшее индуктивное определение -- это определение некоторого множества слов, классическим примером которого служит определение идентификатора в Паскале: идентификатор -- это либо буква, либо идентификатор, к которому приписана справа буква или цифра. Слова конечной длины в конечных алфавитах (в частности, числа) -- самый простой тип алгоритмических данных, а число символов в слове (длина слова) - естественная единица измерения объема обрабатываемой информации. Более сложный случай алгоритмических объектов -- формулы. Они также определяются индуктивно и также являются словами в конечном алфавите, однако не каждое слово в этом алфавите является формулой. В этом случае обычно основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям. Такая проверка называется синтетическим анализом.

Данные для своего размещения требуют памяти. Память обычно считается однородной и дискретной, то есть состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ алфавита данных. Т.о. единицы измерения объема данных и памяти согласованы. При этом память может быть бесконечной. Вопрос о том нужна ли отдельная память для каждого из трех видов данных (входных, выходных и промежуточных) решается по-разному.

Требование результативности, в частности предполагает, что всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисление функции f(x), обязан показать, что алгоритм остановиться после конечного числа шагов (как говорят, сходится) для любого x из области задания f. Однако проверить результативность (сходимость) гораздо труднее, чем требование, изложенные в других пунктах. В отличие от них сходимость обычно не удаётся установить простым просмотром описания алгоритма А и любых входных данных х как будет показано далее вообще не существует.

Если алгоритм используется для вычисления значений числовой функции, то эта функция называется эффективно вычислимой, или алгоритмически вычислимой, или просто вычислимой.

Следует различать:

1) описание алгоритма (инструкцию или программу);

2) механизм реализации алгоритма (например, компьютер), включающий средства пуска, остановки, реализации элементарных шагов, выдачи результатов и обеспечении детерминированности, т.е. управление ходом вычисления;

3) процесс реализации алгоритма, т. е. последовательность шагов, которая будет порождена при примени алгоритма к конкретным данным.

Будем предполагать, что описание алгоритма и механизм его реализации конечны (память, как уже говорилось, может быть бесконечной, но она не включается в механизм). Требование конечности процесса реализации совпадает с требованием результативности.

алгоритм нормализация функция марков

3. Необходимость в математическом уточнении понятии алгоритма

Понятие «алгоритма» формировалось с древнейших времен, но до конца первой трети 20 века математики довольствовались интуитивным представлением о нем. Утверждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием. Необходимости в уточнении понятия алгоритма не было до тех пор, пока в математике не накопилось достаточно проблем, для решения которых не удалось найти алгоритмы. Одно дело привести решение проблемы, а другое доказать невозможность построения алгоритма для решения данной проблемы. В первом случае достаточно описать процесс решения, чтобы удостовериться, что он действительно является алгоритмом. В этом случае достаточно и интуитивного понятия «алгоритма». Доказать не существование алгоритма таким путем невозможно. Для этого нужно точно знать, что такое «алгоритм». В 20-х г.г. 20 века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Первые работы по уточнению понятия алгоритма и его изучению, т.е. теории алгоритмов, были выполнены в 1936-1937 годах математиками А.Тьюрингом, Постом, Эрбраном, Черчем, А.А. Марковым. Попытки этих исследователей дать четкое математическое определение алгоритма в конечном итоге были сведены к трем основным типам универсальных алгоритмических моделей.

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа - рекурсивные функции - является исторически первой формализацией понятия алгоритма.

Второй тип основан на представление об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Основной теоретической моделью этого типа является машина Тьюринга.

Третий тип алгоритмических моделей - это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (подслова) другим словом. Пример моделей этого типа - нормальные алгоритмы Маркова.

Впоследствии выяснилось, что машины Тьюринга, нормальные алгоритмы Маркова и рекурсивные функции равносильны между собой, т. е. если какой-нибудь процесс можно задать с помощью одного определения, то его можно задать и с помощью двух других и наоборот.

4. Нормальные алгоритмы Маркова

Теория нормальных алгоритмов (или алгоритмов, как называл их создатель теории) была разработана советским математиком А. А. Марковым (1903--1979) в конце 1940-х -- начале 1950-х гг. XX в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.

4.1 Марковские подстановки

Алфавитом называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв -- словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово будем обозначать . Если А и В -- два алфавита, причем А В, то алфавит В называется расширением алфавита А.

Слова будем обозначать латинскими буквами: Р, Q, R (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Пусть А -- алфавит русских букв, рассмотрим слова: . Слово Р₂ является подсловом слова -- подсловом Р₁ и Р₂, причем в Р₁ оно входит дважды. Обратим внимание на первое вхождение.

Определение 1. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова Р (если таковое имеется и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R. Если же первого вхождения Р в слово R нет (и, следовательно, вообще нет ни одного вхождения Р в R), то считается, что марковская подстановка (Р, Q) неприменима к слову R.

Частными случаями марковских подстановок являются подстановки с пустыми словами:

Пример 1. Примеры марковских подстановок рассмотрены в таблице, в каждой строке которой сначала дается преобразуемое слово, затем применяемая к нему марковская подстановка и, наконец, получающееся в результате слово:

Таблица 1

Преобразуемое слово	Марковская подстановка	Результат
138 578 926	(8 578 9, 00)	130 026
тарарам	(ара,)	трам
шрам	(ра, ар)	шарм
функция	(, )	функция
логика	(ика, )	лог
книга	()	книга
поляна	(пор, т)	[неприменима]

Для обозначения марковской подстановки (Р, Q) используется запись РQ . Она называется формулой подстановки (Р, Q). Некоторые подстановки (Р, Q) будем называть заключительными (смысл названия станет ясен чуть позже). Для обозначения таких подстановок будем использовать запись, называя ее формулой заключительной подстановки. Слово Р называется левой частью, a Q -- правой частью в формуле подстановки.

4.2 Нормальные алгоритмы и их применение к словам

Упорядоченный конечный список формул подстановок в алфавите А называется схемой (или записью) нормального алгоритма в А. (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.)

Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова. Дадим его точное определение.

Определение 2. Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности Vi слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V₀ последовательности берется слово V. Пусть для некоторого слово Vi построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в V_i то V_i+1 полагают Равным Vi, и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в V_i то в качестве V_i+l берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово V_i ; процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки, и продолжающимся -- в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Последний член W последовательности называется результатом применения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V в W.

Последовательность V_i, будем записывать следующим образом:

Мы определили понятие нормального алгоритма в алфавите А. Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А.

Рассмотрим примеры нормальных алгоритмов.

Пример 2. Пусть А = {a, b} -- алфавит. Рассмотрим следующую схему нормального алгоритма в А:

Рассмотрим, как работает определяемый этой схемой нормальный алгоритм. Всякое слово V в алфавите А, содержащее хотя бы одно вхождение буквы а, он перерабатывает в слово, получающееся из V вычеркиванием в нем самого левого (первого) вхождения буквы а. Пустое слово он перерабатывает в пустое. (Алгоритм не применим к таким словам, которые содержат только букву b.) Например, aabab => abab, ab => b, aa => a, bbab => bbb, baba => bba.

Пример 3. Пусть A = {a₀, a₁ ..., a_n} -- алфавит. Рассмотрим схему

Она определяет нормальный алгоритм, перерабатывающий всякое слово (в алфавите А) в пустое слово. Например



4.3 Нормально вычислимые функции и принцип нормализации Маркова

Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам. В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления. Рассмотрим два примера.

Пример 4. В алфавите А = {1} схема определяет нормальный алгоритм, который к каждому слову в алфавите А = {1} (все такие слова суть следующие: , 1, 11, 111, 1111, 11111 и т.д.) приписывает слева 1. Следовательно, алгоритм реализует (вычисляет) функцию .

Пример 5. Дана функция

где n -- число единиц в слове 11...1. Рассмотрим нормальный алгоритм в алфавите А = {1} со следующей схемой:

Этот алгоритм работает по такому принципу: пока число букв 1в слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше 0, то оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, оно заключительно переводится в слово 1. Например:

1111111 => 1111 => 1 => ;

111111111 => 111111 => 111 => => 1.

Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию.

Сформулируем теперь точное определение такой вычислимости функций.

Определение 3. Функция f заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение В данного алфавита () и такой нормальный алгоритм в В, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f(V).

Таким образом, нормальные алгоритмы примеров 4 и 5 показывают, что функции f(х) = х+ 1 и нормально вычислимы. Причем соответствующие нормальные алгоритмы удалось построить в том же самом алфавите А, на словах которого были заданы рассматривавшиеся функции, т.е. расширять алфавит не потребовалось (В = А). Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий данную функцию.

Пример 6. Построим нормальный алгоритм для вычисления Функции f(х) = х + 1 не в одноичной системе (как сделано в примере 4), а в десятичной. В качестве алфавита возьмем перечень арабских цифр А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, а нормальный алгоритм будем строить в его расширении В = А U {а, b}. Вот схема этого нормального алгоритма (читается по столбцам):



Попытаемся применить алгоритм к пустому слову . Нетрудно понять, что на каждом шаге должна будет применяться самая последняя формула данной схемы. Получается бесконечный процесс:

=>а => аа => ааа => аааа =>...

Это означает, что к пустому слову данный алгоритм не применим.

Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: 499 => а499 (применена последняя формула) => 4а99 (формула из середины второго столбца) => 49а9 => 499b (дважды применена формула из конца второго столбца) => 499b (предпоследняя формула) => 49b0=> 4b00 (дважды применена предпоследняя формула первого столбца) => 500 (применена формула из середины первого столбца).

Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что 328 => 329, 789 => 790.

В рассмотренном примере нормальный алгоритм построен в алфавите В, являющемся существенным расширением алфавита А (т.е.), но данный алгоритм слова в алфавите А перерабатывает снова в слова в алфавите А. В таком случае говорят, что алгоритм задан над алфавитом А.

Создатель теории нормальных алгоритмов советский математик А. А. Марков выдвинул гипотезу, получившую название «Принцип нормализации Маркова». Согласно этому принципу, для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.

Сформулированный принцип, носит внематематический характер и не может быть строго доказан. Он выдвинут на основании математического и практического опыта.

Все, что мы знаем о тезисах Тьюринга и Чёрча, можно с полным правом отнести к принципу нормализации Маркова. Косвенным подтверждением этого принципа служат теоремы следующего пункта, устанавливающие эквивалентность и этой теории алгоритмов теориям машин Тьюринга и рекурсивных функций.

4.4 Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу

Это совпадение будет означать, что понятие нормально вычислимой функции равносильно понятию функции, вычислимой по Тьюрингу, а вместе с ним и понятию частично рекурсивной функции.

Теорема 1. Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.

Доказательство. Пусть машина Тьюринга с внешним алфавитом А = {} и алфавитом внутренних состояний Q= вычисляет некоторую функцию f, заданную и принимающую значения в множестве слов алфавита А (словарную функцию на А). Попытаемся представить программу этой машины Тьюринга в виде схемы некоторого нормального алгоритма. Для этого нужно каждую команду машины Тьюринга представить в виде совокупности марковских подстановок. Конфигурации, возникающие в машине Тьюринга в процессе ее работы, представляют собой слова в алфавите A U Q. Эти слова имеют вид: Нам понадобится различать начало слова и его конец (или его левый и правый концы). Для этого к алфавиту A U Q добавим еще два символа (не входящие ни в А, ни в Q): Эти символы будем ставить соответственно в начало и конец каждого машинного слова w: uwv.

Пусть на данном шаге работы машины Тьюринга к машинному слову w предстоит применить команду . Это означает, что машинное слово w (а вместе с ним и слово uwv) содержит подслово q_aai. Посмотрим, какой совокупностью марковских подстановок можно заменить данную команду в каждом из следующих трех случаев:

а) Х= С, т.е. команда имеет вид: . Ясно, что в этом случае следующее слово получается из слова uwv с помощью подстановки которую мы и будем считать соответствующей команде

б)Х= Л, т.е. команда имеет вид: . Нетрудно понять, что в этом случае для получения из слова uwv следующего слова надо к слову uwv применить ту подстановку из совокупности

которая применима к слову uwv. В частности, последняя подстановка применима только тогда, когда q_a -- самая левая буква в слове w, т.е. когда надо пристраивать ячейку слева;

в) Х= П, т.е. команда имеет вид: . В этом случае

аналогично, чтобы получить из слова uwv следующее слово, нужно к слову uwv применить ту из подстановок совокупности

которая применима к слову uwv.

Поскольку слово входит в слово w только один раз, то к слову uwv применима только одна из подстановок, перечисленных в пунктах б, в. Поэтому порядки следования подстановок в этих пунктах безразличны, важны лишь их совокупности.

Заменим каждую команду из программы машины Тьюринга указанным способом совокупностью марковских подстановок. Мы получим схему некоторого нормального алгоритма. Теперь ясно, что применить к слову w данную машину Тьюринга -- это все равно, что применить к слову uwv построенный нормальный алгоритм. Другими словами, действие машины Тьюринга равнозначно действию подходящего нормального алгоритма. Это и означает, что всякая функция, вычислимая по Тьюрингу, нормально вычислима.

Верно и обратное утверждение.

Теорема 2. Всякая нормально вычислимая функция вычислима по Тьюрингу.

Теорема 3. Следующие классы функций (заданных на натуральных числах и принимающих натуральные значения) совпадают :

а) класс всех функций, вычислимых по Тьюрингу,

б) класс всех частично рекурсивных функций;

в) класс всех нормально вычислимых функций.

Смысл и значение этого результата. В разное время в разных странах ученые независимо друг от друга, изучая интуитивное понятие алгоритма и алгоритмической вычислимости, создали теории, описывающие данное понятие, которые оказались равносильными. Этот факт служат мощным косвенным подтверждением адекватности этих теорий опыту вычислений, справедливости каждого из тезисов Тьюринга, Чёрча и Маркова. В самом деле, ведь если бы один из этих классов оказался шире какого-либо другого класса, то соответствующий тезис Тьюринга, Чёрча или Маркова был бы опровергнут. Например, если бы класс нормально вычислимых функций оказался шире класса рекурсивных функций, то существовала бы нормально вычислимая, но не рекурсивная функция. В силу ее нормальной вычислимости она была бы алгоритмически вычислима в интуитивном понимании алгоритма, и предположение о ее нерекурсивности опровергало бы тезис Чёрча. Но классы Тьюринга, Чёрча и Маркова совпадают, и таких функций не существует. Это и служит еще одним косвенным подтверждением тезисов Тьюринга, Маркова и Чёрча.

Можно отметить, что существуют еще и другие теории алгоритмов, и для всех них также доказана их равносильность с рассмотренными теориями.

5. Присоединяющие алгоритмы

Возьмем алфавит А такой, что буквы и не входят в А. Пусть Q - какое-либо фиксированное слово в А. Обозначим символом U нормальный алгоритм в А со схемой:

(тождественный нормальный алгоритм в алфавите со схемой)

Пусть А - алфавит, состоящий из букв a, b, и с; пусть е - буква, не входящая в А; пусть Q - какое-либо фиксированное слово в А. Обозначим символом B нормальный алгоритм в алфавите Ае со схемой

(1)

До конца параграфа P, R, и S будут означать любые слова в алфавите А, а о - любую букву этого алфавита.

Докажем

B: Р+ еР. (B переводит Р в еР)

Действительно, левая часть последней формулы подстановки (пустое слово) входит в Р, тогда как левые части всех предшествующих формул в Р не входят из-за присутствия в них буквы е. Следовательно, алгоритм B действует на Р, причем формулой подстановки, активной на слове Р, является последняя формула схемы. Результатом действия алгоритма B на слово Р является результат действия на Р активной формулы, т. е. результат подстановки в Р правой части этой формулы (слова е) вместо первого вхождения **Р ее левой части, т. е. слово еР, и, так как активная на Р формула подстановки - простая,

B: Р+ еР (B переводит Р в еР)

Что и требовалось доказать.

B: РеоR + PоеR

В самом деле, алгоритм B действует на слово РеоR, так как на это слово действуют две формулы подстановки его схемы: одна из первых двух, имеющая вид еоое, и последняя. Ясно, что активной на слове РеоR будет формула еоое, так как она предшествует последней формуле схемы. Имеется единственное вхождение Р*ео*R левой части формулы еоое в слово РеоR. Следовательно, оно и будет первым. Результат подстановки правой части активной формулы, т. е. слова ое, вместо этого вхождения есть слово PоеR и, так как активная формула подстановки простая,

B: РеоR + PоеR

Что и требовалось доказать.

Схему (1) нормального алгоритма B, первые три формулы подстановки которой имеют «общий вид» еоое, где о - произвольная буква алфавита А, удобно записывать в следующем сокращенном виде:

Дополнительно указывая, что о пробегает алфавит А. При расшифровке этой записи мы придаем о последовательно значения a, b, c, соблюдая - для конкретности - порядок букв в А.

Алгоритмы U и B естественно называть присоединяющими алгоритмами; алгоритм U - левым присоединяющим (слово Q) алгоритмом над алфавитом А, алгоритм B - правым присоединяющим (слово Q) алгоритмом над алфавитом А. Частным случаем левого присоединяющего алгоритма над алфавитом А является тождественный нормальный алгоритм J в алфавите А.

Для него мы имеем

J(Р) ° Р (графическое равенство слов)

6. Сокращающие алгоритмы

Будем говорить о простой формуле подстановки, что она сокращающая, если длина ее правой части меньше длины ее левой части.

Будем говорить о нормальном алгоритме, что он сокращающий, если все его простые формулы подстановок сокращающие.

Следующая лемма очевидна:

Если U - сокращающий алгоритм и U: P+ Q, то

<

(результат применения операции к слову Q и P)

Любой сокращающий алгоритм U в алфавите А применим ко всякому слову Р в алфавите А, причем имеет место неравенство:

(U : P) ¦(1)

Будем доказывать эту теорему методом индукции по длине слова Р, фиксируя сокращающий алгоритм U.

Алгоритм U применим ко всякому слову длины

и для всякого такого слова Р имеет место неравенство (1). В самом деле, если ° то Р ° ^. Никакая простая формула подстановки в этом случае не действует на Р, так как ее левая часть не пуста. Если алгоритм U действует на Р, то формулой, активной на Р в U, является заключительная формула подстановки. Тогда имеется слово Q такое, что U : P+ Q, и мы имеем (U : P) ° ¦(¦- натуральные числа), откуда следует, что алгоритм U применим к слову Р. Если же U не действует на Р, то (U : P) ° . В обоих случаях алгоритм U применим к слову Р и имеет место (1).

Предположим теперь, что для натурального числа N доказано, что алгоритм U применим ко всякому слову в А длины не большей N, и что для всякого такого слова имеет место неравенство (1). Пусть Р - слово в А длины N¦. Имеет место одно из трех 1) U : P¬(схема U не действует на слово Р); 2) имеется слово Q такое, что U : P+ Q; 3) имеется слово Q такое, что U : P+ Q. В первых двух случаях алгоритм U применим к Р и (U : P) ¦. В третьем случае < и потому N. По индуктивному предположению отсюда следует, что алгоритм U применим к Q и что (U : P) ¦. Следовательно, алгоритм U применим к Р и (U : P) ° (U : Q)¦. Но ¦ . Поэтому

(U : P) ° (U : Q)¦ ¦

Что и требовалось доказать.

Пусть А - алфавит и С - нормальный алгоритм в алфавите А с сокращенно записанной схемой

Где о пробегает алфавит А.

Нормальный алгоритм С сокращающий

Алгоритм С применим ко всякому слову в алфавите А.

Алгоритм С действует на всякое не пустое слово в алфавите А.

Докажем теперь, что:

алгоритм С перерабатывает всякое слово в алфавите А в пустое слово.

Пусть Р - слово в алфавите А. Имеется слово Q в А такое, что

С(Р) ° Q (1)

Имеем поэтому С: Р ¦ Q (Сконечно преобразует Р в Q) или С: Р ¦ Q¬. Первая возможность отпадает, так как заключительных формул подстановок в схеме С нет. Следовательно, С: Р ¦ Q¬.

Отсюда следует, что

Q ° (2)

Таким образом, С (Р) ° [(1), (2)], что и требовалось доказать.

Ввиду выше сказанного мы будем называть алгоритм С аннулирующим алгоритмом в А.

Фиксируем слово С в алфавите А и обозначим С нормальный алгоритм в алфавите А со следующей сокращенно записанной схемой:

Где пробегает А. Алгоритм С сокращающий. Имеем поэтому:

- алгоритм С применим ко всякому слову в алфавите А ;

- алгоритм С действует на всякое слово в алфавите А; если при этом слово Р в алфавите А не пусто, то формула подстановки, активная на Р в С, простая.

Из этого следует:

- невозможно естественное окончание процесса применения алгоритма С;

- если С: R+ Q, то R ° и Q ° C.

В самом деле, если R не пусто, то в алгоритм С просто переводит R в некоторое слово S, что невозможно, так как по условию С: R+ Q. Поэтому R ° . Единственной формулой подстановки, действующей на , является формула , ввиду чего С: + C. Таким образом, Q ° C, что и требовалось доказать.

Алгоритм С перерабатывает всякое слово в алфавите А в слово С.

Пусть Р - слово в алфавите А. Имеется слово Q в А такое, что С(Р) ° Q (Алгоритм С применим ко всякому слову в алфавите А)

Имеем С: Р ¦ Q или С: Р ¦ Q¬. Следовательно, С: Р ¦ Q, и поэтому имеется слово R такое, что С: R+ Q. Отсюда следует, что Q ° C

Таким образом, С (Р) ° C [(1), (2)], что и требовалось доказать.

7. Разветвляющий алгоритм

Пусть не является буквой алфавита А. Пусть C,

D, E - какие-либо фиксированные слова в А. Построим нормальный алгоритм U в алфавите А с сокращенно записанной схемой

(1)

Где пробегает алфавит А.

Покажем, что он применим ко всякому слову в алфавите А, причем

U(С) ° D(2)

U(Р) ° Е(3)

Для всякого слова Р в А, графически отличного от С.

Чтобы установить (2), мы заметим, что левые части формул подстановок алгоритма U, соответствующие первым пяти строкам схемы (1), в С не входят, так как эти левые части либо содержат букву , либо имеют длину на единицу большую длины слова С. Левая часть следующей формулы подстановки С D входит в С. Таким образом, эта формула активна на слове С в схеме (1) и результат ее действия - а тем самым и результат действия схемы (1) - на слово С, как легко видеть, есть слово D, и так как в данном случае активная формула подстановки является заключительной, то

U: С+ D

Откуда непосредственно следует (2)

Для установления истинности утверждения (3) мы докажем следующие восемь лемм 1 - 8. В них P, Q, R будут обозначать произвольные слова в алфавите А, а - любую букву этого алфавита.

1. U: QR+ QR.

В самом деле, на слово QR действует в точности одна из формул подстановок, представленных первой строкой схемы (1): формула . Именно она и является в данном случае активной. Вхождение Q**R является единственным - а следовательно, и первым - вхождением ее левой части в слово QR. Значит, результат действия схемы (1) на слово QR есть QR. А тка как активная формула простая, то

U: QR+ QR.

Что и требовалось доказать.

Таким образом, лемма 1 говорит о том, что в результате одного простого шага буква в слове вида QR «продвигается» на одно место влево.

2. U: QR¦ QR.

Это утверждение мы докажем правой индукцией по Q. Для этого мы рассмотрим свойство F слова Q, выражаемое условием «каково бы ни было R, U: QR¦ QR »,

И покажем, что любое слово Q обладает этим свойством.

В самом деле, пустое слово обладает свойством F. Пусть теперь Q обладает F, а - какая-либо буква. Тогда

U: QR+ QR [1] (4)

Но R - слово в А, и потому по индукционному предположению

U: QR¦ QR. (5)

Следовательно,

U: QR¦ QR [(4), (5)]

И, значит, Q обладает свойством F. Таким образом, действительно, любое Q обладает свойством F, а это и доказывает наше утверждение.

3. U: Р+ Р.

В самом деле, ни одна из формул подстановок, представленных первой строкой схемы (1), не действует на Р. Вхождение **Q есть единственное вхождение слова вида в Р. Таким образом, из рассмотрения схемы (1) вытекает, что формула является активной на Р в схеме (1), и потому

U: Р+ Р

Что и требовалось доказать.

4. U: ¦ .

Докажем это утверждение левой индукцией по Р. Для этого рассмотрим свойство G слова Р, выражаемое условием

«. U: ¦ »,

И покажем, что этим свойством обладает любое слово Р.

Действительно, пустое слово им обладает. Пусть теперь Р обладает G, а - какая-либо буква. Тогда

U: Р+ Р [3] (6)

Но по индукционному предположению

U: ¦ (7)

И потому

U: Р¦

Т. е. Р обладает свойством G. Значит, любое Р обладает этим свойством, а это и требовалось доказать.

5. U: + Е.

В самом деле, формулы подстановок, представленные первыми двумя строками схемы (1), не действуют на , а формула действует на это слово и, значит, она является в данном случае активной. Вхождение ** является первым вхождением левой части этой формулы в слово . Результат подстановки ее правой части вместо этого вхождения есть Е, и так как эта формула является заключительной, то

U: + Е

Что и требовалось доказать.

6. Если С входит в Р и Р графически не принадлежит С, то существуют такие слова Q и R в А, что U: Р+ QR.

В самом деле пусть Р - слово в А, отличное от С, и пусть С входит в Р. Тогда в Р входит либо одно из слов вида С, либо одно из слов вида . Иначе говоря, в Р входит левая часть хотя бы одной из формул, представленных четвертой и пятой строками схемы (1). Эта формула имеет вид S, и требуется применить ее к первому вхождению слова S (равного С или ) в Р. Пусть Q*S*R будет этим вхождением. Тогда Q и R суть, как и Р, слова в А , а результат подстановки правой части формулы есть слово QR. Так как активная формула простая, U: Р+ QR, что и требовалось доказать.

7. Если С не входит в слово Р в алфавите А, то

U: Р+ .

В самом деле, в этом случае из левых частей формул подстановок алгоритма U левая часть последней формулы - пустое слово - входит в Р, все же остальные не входят в Р, так как в них либо входит , либо С. Следовательно, требуется подставить правую часть последней формулы, т. е. вместо первого вхождения пустого слова в Р, что дает Р. Так как активная формула простая, то

U: Р+ , что и что и требовалось доказать.

8. Если Р - слово в алфавите А, отличное от С, то могут быть указаны такие слова Q и R в А, что U: Р+ QR.

В самом деле, если С входит в Р, то такие Q и R могут быть указаны 6. Если же С не входит в Р, то, согласно 7, в качестве Q можно взять ^, а качестве R слово Р.

Мы можем теперь доказать равенство (3). Пусть Р - слово в А отличное от С. Возьмем слова Q и R в А согласно 8 таким образом, что U: Р+ QR.

Имеем тогда

U: Р+ QR

¦ QR [2]

¦ [4]

+ Е [5]

Откуда U: Р¦ Е, и поэтому U: (Р) ° Е, что и требовалось доказать.

Таким образом, работа алгоритма U над словом Р в А протекает следующим образом. Если Р ° С, то U за один шаг переводит Р в D и на этом его работа заканчивается. Если же Р графически не равен С, то U «вводит» в перерабатываемое слово сигнализирующую об этом букву [8], которая «выходит» затем в начало слова [2], «стирает» его [4] и превращается в Е [5], после чего работа U прекращается.

8. Удваивающий алгоритм

Пусть и означают различные буквы, не принадлежащие алфавиту А. Построим нормальный алгоритм J в алфавите А с сокращенно записанной схемой

(1)

Где и пробегают алфавит А (про n-буквенном алфавите А эта схема состоит из n+n+4 формул подстановок).

Покажем, что

J(Р) ° РР(2)

Для всякого слова Р в А.

Для установления истинности утверждения (2) мы введем две операции Ф и Ш над словами в А, а затем докажем леммы, из которых это утверждение будет вытекать. В дальнейшем P, Q, R, S будут обозначать произвольные слова в А, а , - любые буквы этого алфавита.

Положим

Ф(^) ^ ( - равенство по определению ) (3)

Ф(Р) Ф(Р) (4)

Ш(^)^(5)

Ш(P) Ш (P) (6)

Легко видеть, что

Ф() ° [(4), (3)] (7)

Ш () ° [(6), (5)] (8)

Кроме того правой индукцией по Q нетрудно показать, что

Ф(РQ) ° Ф(Р) Ф(Q)[(3), (4)] (9)

Ш(РQ) ° Ш(Р) Ш(Q)[(5), (6)] (10)

Имеем

1. J: Р+ Р.

В самом деле, левые части всех формул, подстановок схемы (1), кроме последней, не входят в Р, так как буквы и не являются буквами алфавита А. Левая часть последней формулы (пустое слово) входит в Р и, таким образом, эта формула является активной на Р. **Р есть первое вхождение левой части этой формулы в слово Р. Вместо этого вхождения требуется подставить правую часть активной формулы, т. е. , что и дает нам слово Р. Так как активная формула является простой,

J: Р+ Р

Что и требовалось доказать.

2. J: Q + Q.

Доказывается аналогично 1 рассмотрением схемы (1). Формулой подстановки, активной в (1) на Q, является формула .

3. J: Ф(Р) РQ+ Ф(Р) РQ.

Доказывается рассмотрением схемы (1). Легко видеть, что ни одна из формул, представленных первой строкой схемы (1), не действует на слово Ф(Р) РQ. Между тем среди формул, представленных второй строкой, имеется формула с левой частью, входящей в Ф(Р) РQ. Эта формула и является активной на данном слове. Единственное вхождение ее левой части в рассматриваемое слово имеет вид Ф(Р) Р**Q. Вместо него подставляется правая часть формулы, т. е. слово , и, так как активная формула является простой,

J: Ф(Р) РQ+ Ф(Р) РQ

Что и требовалось доказать.

4. J: Ф(S) RQ+ Ф(S) RQ.

Доказывается рассмотрением схемы (1). Активной на слове Ф(S) RQ является формула , представленная первой строкой схемы (1).

5. J: Ф(S) RРQ ¦ Ф(S) RQ.

Мы докажем это утверждение левой индукцией по Р. С этой целью мы выведем свойство F слов Р, выражаемое условием «каковы бы ни был Q, R, S и ,

J: Ф(S) RРQ ¦ Ф(S) RQ»

И обычным индуктивным рассуждением покажем, что любое Р обладает этим свойством.

Действительно, пустое слово обладает свойством F. Допустим теперь, что им обладает слово Р, и покажем, что тогда им обладает и слово , какова бы ни была буква . В самом деле, R есть слово в А, и потому по индукционному предположению

J: Ф(S) RQ ¦ Ф(S) RQ. (11)

Но согласно 1.4,

J: Ф(S) RQ+ Ф(S) RQ. (12)

И, следовательно,

J: Ф(S) RQ ¦ Ф(S) RQ[(11), (12)]

Что и оставалось доказать.

6. J: Ф(Р) РQ ¦ Ф(Р) Q.

Это утверждение представляет собой частный случай 5 при R° и S ° P.

7. J: PQ ¦ Ф(Р) PQ.

Докажем это утверждение правой индукцией по Р. С этой целью рассмотрим свойство G слов Р, выражаемое условием «каково бы ни было Q, J: PQ ¦ Ф(Р) PQ»

И индуктивным рассуждением покажем, что этим свойством обладает любое слово в А.

Действительно, пустое слово им обладает. Предположим теперь, что им обладает слово Р, и пусть - произвольная буква. Тогда по индукционному предположению

J: PQ ¦ Ф(Р) PQ. (13)

J: Ф(Р) PQ + Ф(Р) РQ [3], (14)

И потому

J: Ф(Р) PQ ¦ Ф(Р) РQ[(13), (14)]¦ Ф(Р) Q[1.6]

° Ф (Р) РQ[(4)]

Следовательно, Р обладает свойством G. Тем самым лемма 7 доказана.

8. J: P ¦ Ф(Р) P.

Это утверждение представляет собой частный случай 7 при Q °

9. J: Ш(P) Ф(Q) R+Ш (P) Ф(Q) R.

Доказывается рассмотрением схемы (1). Активна формула, представленная третьей строкой схемы.

10. J: Ф(PQ) PQ¦ Ш (P) Ф(Q) R.

Доказательство проведем правой индукцией по Р. Для этого рассмотрим свойство H слов Р, выражаемое условием «каково бы ни было Q,

J: Ф(PQ) PQ¦ Ш (P) Ф(Q) R»

И, рассуждая, как обычно в таких условиях, покажем, что им обладает любое слово в А.

Действительно, пустое слово этим свойством обладает. Пусть теперь им обладает слово Р, и пусть - произвольная буква. Тогда

J: Ф(PQ) PQ¦ Ш (P) Ф(Q) РQ

° Ш (P) Ф(Q) РQ[(9), (7)]

+ Ш (P) Ф(Q) РQ[9]

° Ш (P) Ф(Q) РQ[(6)]

И, значит, P также обладает свойством Н. Таким образом, действительно, любое слово в А обладает свойством Н, что и требовалось доказать.

11. J: Ф(Р) P¦ Ш (P) P

(Частный случай 10 при Q ° .)

12. J: РШ(Q)PQ + P Ш(Q)PQ.

Доказывается рассмотрением схемы (1). Активная формула, представленная четвертой строкой схемы.

13. J: Ш (PQ)PQ¦ PШ (Q) PQ.

Доказательство проведем правой индукцией по Р. Для этого рассмотрим свойство К слов Р, выражаемое условием «каково бы ни было Q,

J: Ш (PQ)PQ¦ PШ (Q) PQ»

И обычным для таких случаев рассуждением покажем, что им обладает любое слово в А.

Действительно, пустое слово им обладает. Пусть теперь им обладает слово Р, и пусть - любая буква. Тогда

J: Ф(PQ) PQ¦ РШ(Q) РQ

° РШ(Q) PQ [(10), (8)]

+ PШ(Q) PQ [1.12]

Т. е. Р также обладает свойством К. Значит, действительно, любое слово в А обладает этим свойством, что и требовалось доказать.

14. J: Ш(Р) P¦ PP.

(Частный случай 13 при Q ° .)

Теперь докажем утверждение (2). Действительно,

J: Р + Р[1.1]

¦ Ф(Р) P [1.8]

? Ш(Р) P [1.11]

¦ PP[1.14]

+ PP[1.2]

Откуда J: Р¦ PP и, следовательно, J: (Р) ° РР

Что и требовалось доказать.

Таким образом, нормальный алгоритм J может быть охарактеризован как удваивающий алгоритм над алфавитом А.

9. Применение теории нормальных алгоритмов к решению практических задач

Таблица №1. Что получиться в результате следующих марковских подстановок:

Преобразуемое слово	Марковская подстановка	Результат
апельсин		капельсин
апельсин	(пельс, спир)	аспирин
апельсин	(ль,	апесин

№2. Дан алфавит . Построить нормальный алгоритм Маркова, заменяющий все а на с в некотором слове.

Решение:

;

.

№3. Построить нормальный алгоритм Маркова, который в слове из алфавита все вхождения последовательности abc заменяет на символ f.

Решение:

;

.

№4. Дан алфавит . Построить нормальный алгоритм Маркова, который удаляет все b в некотором слове.

Решение:

;

.

№5. Построить нормальный алгоритм Маркова, который в слове из алфавита удаляет все вхождения последовательности bc.

Решение:

;

.

№6. Построить нормальный алгоритм Маркова, который к любом слове в алфавите переносит все буквы а в начало слова.

Решение:

№7. Построить нормальный алгоритм Маркова для вычисления функции в десятичной системе счисления

Решение:

№8. Построить нормальный алгоритм Маркова для вычисления функции в троичной системе счисления.