5.2. Блок-схемы алгоритмов

Связь между шагами можно изобразить в виде графа. В рас­смотренном примере это граф, изображенный на рис.5.

Такой граф, в котором вершинам соответствуют шаги, а реб­рам – переходы между шагами, называют блок-схемой алгоритма. Его вершины могут быть двух видов: вершины, из которых выходит одно ребро (их называют операторами), и вершины, из которых вы­ходят 2 ребра (их называют логическими условиями или предика­тами). Кроме того, есть единственный оператор начала и единствен­ный оператор конца, из которого не выходят ребра. Важной особен­ностью блок-схемы является то, что связи, которые она описывает, не зависят от того, являются ли шаги элементарными или представляют собой самостоятельные алгоритмы или блоки.

При всей наглядности языка блок-схемы, не следует пере­оценивать его возможности. Он достаточно груб и отражает связи лишь по управлению, а не по информации (где этому блоку брать исходные данные). Блок-схемы не содержат сведений ни о данных, ни о памяти, ни об используемом наборе элементарных шагов. В частности, если в блок-схеме нет циклов, это не значит, что нет циклов в алгоритме (они могут быть в каком-либо элементарном блоке). По существу блок-схема – удобное средство для описания детерминизма алгоритма. Условия, т.е. точки ветвления могут быть не только двоичными (да- нет; x < 5 - x  5 ), но и многозначными (x < 5; 5  x < 20; x = 20; x > 20).

В теории алгоритмов используется следующий подход: выби­рается конечный набор исходных объектов, которые объявляются элементарными, и конечный набор способов построения из них но­вых объектов. Этот подход уже использован при обсуждении во­проса о ‘‘данных”. Уточнением понятия ‘‘данные” будем считать множества слов в конечных алфавитах. Для уточнения детерми­низма используются либо блок-схемы, либо соответствующие словесные описания. Кроме того, нужно зафиксировать набор элемен­тарных шагов и договориться об использовании памяти. После того, как это будет сделано, получится конкретная алгоритмическая мо­дель.

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

I тип связывает понятие алгоритма с наиболее традицион­ными понятиями математики – вычислениями и числовыми функ­циями. Наиболее развитая модель этого типа – рекурсивная функция;

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

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

5.3. Машины Тьюринга

Основные определения:

Машина Тьюринга состоит из:

1) управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество

Q={q­­₁, q­­₂, …, q­­_n};

2) ленты, разбитой на ячейки в каждой из которых может быть записан один из символов конечного алфавита А={а₁,…., a_m};

3) устройства обращения к ленте, (считывающей и пишущей головки), которое в любой момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состоя­ния управляющего устройства, записывает в ячейку символ (быть может совпадающий с прежним или пустой, т.е. стирает), сдви­гается на ячейку вправо или влево или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом). Среди состояний управляющего устройства выделены начальное состояние q­­₁ и заключительное состояние q­­_{Z ­} (z здесь не числовая переменная, а мнемонический знак конца). В начальном состоянии машина находится перед нача­лом работы; попав в заключительное состояние она останавли­вается.

Таким образом, память машины Тьюринга – это конечное множество состояний (внутренняя память) и лента (внешняя па­мять). Лента бесконечна в обе стороны, однако, в начальный момент времени только конечное число ячеек ленты заполнено непустыми символами, остальные ячейки – пусты, т.е. содержат пустой символ  (пробел). Из характера работы следует, что в любой момент вре­мени лишь конечное число ячеек будет заполнено непустыми сим­волами, важна не бесконечность ленты, а ее неограниченность, т.е. возможность писать на ней сколь угодно длинные, но конечные слова. Данные машины Тьюринга – это слова в алфавите ленты; на ленте записываются и исходные данные и окончательные резуль­таты. Элементарные шаги машины – это считывание и запись сим­волов, сдвиг головки на ячейку вправо или влево, а так же переход управляющего устройства в следующее состояние. Детерминиро­ванность машины, т.е. последовательность ее шагов, определяется следующим образом: для любого внутреннего состояния q_i и сим­вола a_j однозначно заданы:

а) следующее состояние q_i

б) символ а_j который нужно записать вместо а_j в ту же ячейку (стирание символа – занесение пустого символа );

в) направление сдвига головки d_k, обозначаемое одним из трех символов: L (влево), R (вправо), E (на месте). Это задание может опи­сываться либо системой правил (команд), имеющих вид:

q_i а_j q_i а_j d_k, (5.1)

либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении строки q_i и столбца а_j записана тройка символов q_i а_j d_k и, наконец, блок –схемой, которую называют диаграммой перехода. В этой диаграмме, состояниям соответствуют вершины, а правилу (5.1) – ребро, ведущее из q_i в q'_i, на котором написано а_j а_j d_k. Условие однозначности требует, чтобы для любого j и любого iz в системе команд (5.1) имелась одна ко­манда, с левой частью q_i а_j; состояние q_z в левых частях не встреча­ется. На диаграмме переходов это выражается условием, что из лю­бой вершины, кроме q_z выходит ровно m ребер, причем на разных ребрах левые части различны; в вершине q_z нет выходящих ребер.

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

Например, конфигурация с внутренним состоянием q_i , в кото­рой на ленте записано abcde, а головка обозревает d, запишется abcq_ide. Стандартной начальной конфигурацией назовем конфигу­рацию вида q₁, т.е. конфигурацию, содержащую начальное состояние, в которой головка обозревает крайний левый символ слова, написанного на ленте. Аналогично стандартной заключи­тельной конфигурацией, называется конфигурация вида q_z.

Ко всякой не заключительной конфигурации К машины Тью­ринга применима ровно одна команда вида (5.1), которая переводит в конфигурацию К, это соотношение между конфигурациями обозна­чим К К. Если из контекста ясно, о какой машине Тьюринга идет речь, то знак Т опускают.

Если для К₁ и К_n существует последовательность К₁, К₂,…..,К_n, такая, что К₁ К₂ ,….., К_n. Обозначим это К₁К_n

Например, если в системе команд машины Тьюринга имеются команды:

q₂ a₅ q₃ a₄R и q₂ a₁L q₄ a₂, то

q₂a₅a₁a₂ a₄q₃a₁a₂ q₄a₄a₂a₂ и, следовательно,

q₂a₅a₁a₂q₄a₄a₂a_2.

Последовательность конфигураций К₁ К₂ ,….. …, К_n … однозначно определяется исходной конфигурацией К₁ и полностью описывает работу машины Тьюринга, начиная с К₁. Она конечна, если в ней встретится заключительная конфигу­рация, содержащая q_z, или бесконечна в противном случае.

Пример 1. Машина с алфавитом A={1,} состояниями {q₁,q_z} и системой команд q₁1 q₁1R, q₁ q₁1R из любой начальной кон­фигурации будет работать бесконечно, заполняя единицами ленту вправо от начальной точки.

Пример 2. Для любой машины Тьюринга, если К₁ К_i К_j и К_i = К_j, последовательность К₁ К_i К_j……. является бесконечной; ее отрезок К_i К_j будет повторяться (зацикливаться).

Если ₁q₁₂  ₁q_z₂ , то говорят, что машина Тьюринга пе­рерабатывает слово ₁₂ в слово ₁₂ и обозначают это T(₁₂)= ₁₂. Для того, чтобы говорить о том, что могут делать машины Тью­ринга, надо уточнить, как будет интерпретироваться их поведение и как будут представляться данные. Исходными данными машины Тьюринга считаем записанные на ленте слова в алфавите исходных данных А_исхА и векторы из таких слов (словарные векторы над А_исх). Запись на ленте начальной конфигурации со словарным векто­ром (₁,…,_к) назовем правильной, если она имеет вид: ₁₂…_к (при условии А_исх), либо ₁₂…._к, где  - специальный символ – разделитель, не входящий в А_исх. Для любого вектора V_исх над А_исх машина Тьюринга либо работает бесконечно, либо перера­батывает его в совокупность слов, разделенных пробелами в алфа­вите результатов А_резА. В ходе работы ленты могут появиться сим­волы, не входящие в А_исх и А _рез и образующие промежуточный ал­фавит А_пр (содержащий, в частности разделитель). Таким образом:

А=А_исхА_прА_рез.

В простейшем случае А_исх=А_рез и А=А_исх.

Пусть f- функция, отображающая множество векторов над А_рез. Ма­шина Тьюринга правильно вычисляет функцию f, если:

1. Для любых V и W, таких, что f(V)=W: q₁V^*­ q_zW^*­, где V^* и W^*­ - правильные записи V и W.

2. Для любого V, такого, что f(V) не определена, ма­шина Тьюринга запущенная в стандартной начальной конфигу­рации q₁V^*, работает бесконечно.

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

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

Пример 2: Если машина Тьюринга содержит команды q_i a_j q_i a_jE и q_i a_j q_i a_jd_k, то заменив эти две команды одной q_i a_j q_i a_jd_k, получим машину Тьюринга, эквивалентную Т. Путем таких преобразований можно в машине Тьюринга убрать все команды, со­держащие Е и более того, доказывается, что:

Для любой машины Тьюринга существует эквивалентная ей машина, не содержащая Е в командах, следовательно, можно рассматривать ма­шины, головки которых на любом шаге движутся.

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

Для начала рассмотрим числовые функции, отображающие N в N. Договоримся представлять натуральные числа в единичном (унарном) коде, т.е. для всех числовых функций А_исх={1} либо, А_исх={1,*} и число х представляется словом 1,…., 1=1^х, состоящим из х единиц. Таким образом, числовая функция f(x₁,…,x_n) правильно вычислима по Тьюрингу, если есть машина Тьюринга, такая, что q₁1 ^х11 ^х2…1 ^хn q_n1 ^y, когда f(x₁,…,x_n)=y, и Т работает бесконечно, начиная с q₁1 ^х11 ^х2…1 ^хn, если f(x₁,…,x_n) не определена.

Пример 3:

1. Сложение: Во введенном унарном представлении, сложить два числа а и b – значит, слово 1^a 1^b переработать в слово 1^a+b, т.е. уда­лить разделитель  и сдвинуть одно из слагаемых, скажем первое, ко второму. Это преобразование осуществляет машина T₊ с четырьмя состояниями и следующей системой команд (первая команда ведена для случая, когда а=0 и исходное слово имеет вид 1^b):

q₁q_zR

q₁1q₂R

q₂1q₂1R

q₂q₃1L

q₁1q₃1L

q₁q_zR

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

2. Копирование (перезапись слова), т.е. переработка  в . Для чисел эту задачу решает машина Т_коп, система команд которой приведена в таблице.

Таблица 19

	1			0
q1	q20R	qzR	q1L	q11L
q2	q21R	q3R	q2R
q3	q31R	q41L
q4	q41L		q4L	q10R

С оответствующая диаграмма переходов: