Глава 9. Формализация алгоритма 

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

Известно несколько подходов к формализации понятия «алгоритм»:

-   теория конечных и бесконечных автоматов;

-   теория вычислимых (рекурсивных) функций.

Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач.

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

Машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга в 1936 г. американским математиком Эмилем Постом и английским математиком Алланом Тьюрингом.

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

Машина Поста

Рисунок 39 – Эмиль Леон Пост (11.02.1897- 21.04.1954)

Эмиль Леон Пост  - американский математик и логик; один из основателей многозначной логики; основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики.

Абстрактная машина Поста: бесконечная лента, разделенная на клетки (пустые либо с меткой «V») и головка, способная перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если её метки там не было,  стирать если была, или проверять наличие в клетке метки.

Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины.

В каждый момент времени головка («-») находится над одной из клеток ленты и, как говорят, обозревает ее.

Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста.

Рисунок 40 – Машина Поста

Структура команды:

nKm,

где

п – порядковый номер команды,

K – действие, выполняемое головкой,

т – номер следующей команды, подлежащей выполнению.

Существует всего шесть команд машины Поста.

Рисунок 41 – Команды машины Поста

Посмотреть ячейку: если ячейка пустая, то перейти на команду с номером 3, иначе на команду с номером 1.

Программой для машины Поста будем называть непустой список команд, такой что

1.     на n-м месте команда с номером n;

2.     номер т каждой команды совпадает с номером какой-либо команды списка.

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

1.     останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы);

2.     останов при выполнении недопустимой команды; в этом случае останов называется безрезультативным;

3.     машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).

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

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

Пример №2. Командой условного перехода можно воспользоваться для организации циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции.

Пример №3. Представление чисел на ленте машины Поста и выполнение операций над ними.

Число k представляется на ленте машины Поста идущими подряд k + 1 метками (одна метка означает число «О»). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Например, запись чисел 2 и 4 на ленте машины Поста будет выглядеть так:

Обратим внимание, что используемая в машине Поста система записи чисел является непозиционной.

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

Предположим, что головка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавить единицу. В этом случае программа усложняется. Появится «блок поиска числа» - две команды, приводящие головку в состояние, рассмотренное в предыдущем примере:

Программы добавляющие единицу слева и справа.

Машину Поста можно рассматривать как упрощенную модель ЭВМ - как ЭВМ, так и машина Поста имеют:

-   неделимые носители информации (клетки - биты), которые могут быть заполненными или незаполненными;

-   ограниченный набор элементарных действий - команд, каждая из которых выполняется за один такт (шаг).

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

Машина Тьюринга

Алан Матисон Тьюринг – английский математик, логик, криптограф, изобретатель машины Тьюринга.

Рисунок 42 – Алан Матисон Тьюринг (23.06.1912 — 7.06.1954)

Машина Тьюринга (МТ) состоит из счетной ленты, читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q₀, q₁, ..., q_s, принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний).

При этом q₀ называется начальным состоянием.

Читающая и пишущая головка может читать буквы рабочего алфавита А = {а₀, a₁, ..., а_t}, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква а₀ - «пробел».

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

Порядок работы МТ (с рабочим алфавитом а₀, a₁, ..., а_t и состояниями q₀, q₁, ..., q_s) описывается таблицей машины Тьюринга. Эта таблица является матрицей с четырьмя столбцами и (s + 1) (t  + 1) строками.

Каждая строка имеет вид

q_ia_jv_ijq_ij,  0≤i≤s,  0≤j≤t,  q_ij принадлежит {q₀,q₁, … q_s}

где:

-   q_i начальное состояние;

-   a_j обозначен элемент алфавита {а₀, a₁, ..., а_t};

-  v_ij – действие МТ, состоящее либо в занесении в ячейку ленты символа алфавита а₀, a₁, ..., а_t, либо множества предписаний для лентопротяжного механизма: l – переместить ленту влево, r –переместить ленту вправо, s – остановить машину;

-   q_ij является последующим состоянием.

МТ работает согласно следующим правилам:

-   если МТ находится в состоянии q_i, головка прочитывает символ в рабочей ячейке.

-   Если v_ij – буква рабочего алфавита, то головка стирает содержимое рабочей ячейки и заносит туда эту букву.

-   Если v_ij – команда r или l для лентопротяжного механизма, то лента сдвигается на одну ячейку вправо или влево (если не происходит выход за левый край ленты) соответственно.

-   Если v_ij =s, то происходит машинный останов.

Пример №1. Алгоритм прибавления единицы к числу п в десятичной системе счисления. Дана десятичная запись числа п; требуется получить десятичную запись числа п + 1.

Внешний алфавит МТ должен состоять из десяти цифр 0,1,2,3,4,5,6,7,8,9 и символа пробела _. Эти цифры записывают по одной в ячейке (подряд, без пропусков).

При этом достаточно иметь два внутренних состояния машины: q₁ и q₂.

Предположим, что в начальный момент головка находится над одной из цифр числа, а машина находится в состоянии q₁. Тогда задача может быть решена в два этапа: движения головки к цифре единиц числа (во внутреннем состоянии q₁) и замене этой цифры на единицу большую (с учетом переноса 1 в следующий разряд, если это 9), во внутреннем состоянии q₂.

Пример №2. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q₁ обозревает один из символов указанной последовательности.

Решение.

В состоянии q₁ машина ищет правый конец числа.

В состоянии q₂ пропускает знак “+”, при достижении конца последовательности – останавливается.

В состоянии q3 машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.

Пример №3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q₁ обозревает правую цифру числа.

Решение

Состояние q₁ – уменьшаем младшую (очередную) цифру на 1. Если она не равна нулю, то после уменьшения сразу – останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание.

В клетку [a₀, q₁] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять.

Пример №4.  На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру числа.

Решение

Состояние q1 — поиск правой (младшей) цифры числа.

Состояние q2 — умножение очередной цифры числа на 2 без прибавления 1 переноса.

Состояние q3 — умножение очередной цифры числа на 2 с прибавлением 1 переноса.

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

Андрей Андреевич Марков – советский математик, сын известного русского математика А. А. Маркова.

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

Известен работами в области теории алгоритмов. Уделял большое внимание практическим вопросам математической логики, в частности ее применению в теории ЭВМ.

Рисунок 43 – Андрей Андреевич Марков (22.09.1903 – 11.10.1979)

Нормальные алгоритмы Маркова. Имеется алфавит (конечный набор различных символов). Составляющие его символы - буквы. Любая конечная последовательность букв - слово в этом алфавите.

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите.

Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

Пример подстановки. Пусть в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab.

Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и наоборот, заменив М на N, получим aabcbab или аbсаbаb.

Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово.

К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д.

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

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

Последовательность слов Р, P1, Р2, ..., М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки – смежное.

Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.

Пример №1. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

Алфавит                        Подстановки

{а, b, с, d, е}         ас - сa,                 abac - abace

                              ad - da;                eca - ae

                             bc - cb;                 eda - be

                             bd - db;                edb – be

Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.

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

Пример №2.

Алфавит:                        Система подстановок В:

А = {а, b, с}                     cb - cc

                                         сса - аb

                                         ab – bса

Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bсaсаbс получаем:

babaac → bbcaaac → остановка

bcacabc → bcacbcac → bcacccac → bсасаbс → бесконечные процесс (остановки нет), так как мы получили исходное слово.

Пример №3. Пример нормального алгоритма, описывающего сложение натуральных чисел (представленных наборами единиц).

Алфавит:                        Система подстановок В:

А = (+, 1)                                 1 + → + 1

                                                 + 1 → 1

                                                 1 → 1

Слово Р: 11+11+111

Последовательная переработка слова Р с помощью нормального алгоритма Маркова проходит через следующие этапы:

Р = 11 + 11 + 111                    Р5 = + 1 + 111111

Р1 = 1 + 111 + 111                           Р6 = ++ 1111111

Р2 = + 1111 + 111                            Р7 = + 1111111

Р3 = + 111 + 1111                            Р8 = 1111111

Р4 = + 11 + 11111                            Р9 = 1111111

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма.

Существует строгое доказательство того, что по возможностям преобразования нормальные алгоритмы Маркова эквивалентны машинам Тьюринга.

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

В 60-х годах прошлого века русским информатиком В.Ф.Турчиным вместе с учениками в ИПМ АН СССР был разработан новый язык Рефал (REFAL - REcursive Functional Algorithmic Language), который является развитием модели нормальных алгоритмов Маркова в направлении структурирования элементов языка НАМ.

Это один из немногих языков, разработанных в России и получивших известность во всем мире.

Рекурсивные функции

Еще одним подходом к проблеме формализации понятия алгоритма являются, так называемые, рекурсивные функции.

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

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