Для глубокого, строгого изучения свойств алгоритма и его организации необходима формализация, хотя бы для того, чтобы иметь возможность делать доказательные утверждения о свойствах алгоритма. Подчеркнем, что цель математического уточнения понятия Алгоритма - изучение его свойств, а не создание практического инструмента для построения алгоритмов.
Один из возможных путей формализации состоит в том, чтобы подобрать понятия, уже известные в математике, и для которых уже разработан формализм. Одним из таких понятий-претендентов является функция. Действительно, на первый взгляд между функцией и алгоритмом есть много общего. У функции есть область определения, у алгоритма есть область применимости; у функции есть область допустимых значений, у алгоритма есть определенное множество результатов.
Рассмотрим взаимосвязь между функцией и алгоритмом. Сразу отметим, что основные свойства этой взаимосвязи мы будем здесь приводить без доказательства. Тому есть как минимум две причины. Первая - у читателя не предполагается знания необходимого математического аппарата; вторая - это увело бы нас в сторону от основной цели - формализации понятия алгоритма.
Определение 2.1. Говорят, что алгоритм А вычисляет функцию f(x), если:
Существует взаимно однозначное соответствие j между областью определения f(х) и областью применимости А;
Для любого х из области определения f верно: f(x)= А(j(x))
В этом случае функция f(x) называется вычислимой функцией.
Определение 2.2. Говорят, что Алгоритм А разрешает множество М относительно множества Х, где МÌХ, если:
Для любого х из множества М верно, что А(х) = “истина”;
Для любого у из Х, но у не принадлежит М, А(у) =“ложь”.
В этом случае говорят, что множество М разрешимое.
Примеры разрешающих алгоритмов - признаки делимости на 2, на 3, на 5. Эти алгоритмы разрешают множество натуральных чисел, кратных 2 (соответственно 3 либо 5), относительно всего множества натуральных чисел.
Определение 2.3. Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел N, а совокупность результатов есть множество В.
В этом случае В называется перечислимым множеством. Другими словами, в перечислимом множестве все элементы занумерованы целыми числами. Любой элемент в перечислимом множестве может быть найден по его номеру.
Изучение свойств вычислимой функции, а стало быть и алгоритма, показало, что:
Область применимости любого алгоритма - перечислимое множество; Следствие: алгоритмы не могут работать на множестве вещественных чисел.
Функция f(x) вычислима тогда и только тогда, когда перечислим ее график, т.е. множество {(x, f(x))} перечислимо.
Множество MÌX разрешимо относительно множества X, когда M и XM перечислимы.
Отсюда видно, что понятие алгоритма не сводимо к понятию функции. Множество функций мощнее множества алгоритмов.
Самое важное различие между этими понятиями для нас состоит в том, что алгоритм определяет некоторый процесс, который мы называем вычислительным. Понятие функции не предполагает и не определяет никакого процесса. Функция представляется в виде “черного ящика”, на вход которого подали аргументы и на выходе получили результат. Как этот результат был получен - умалчивается. Понятие алгоритма наоборот прежде всего сфокусировано на процессе вычисления результата. Алгоритм определяет именно то, как по аргументам вычислить результат. Итак, понятие функции, как оно есть в математике, нам не подходит, нужно строить формализацию, специально для алгоритма.
Всякое уточнение понятия алгоритма характеризуется следующими семью параметрами:
Совокупность возможных исходных данных (алфавит исходных данных).
Совокупность возможных результатов (алфавит результатов)
Совокупность возможных промежуточных результатов (алфавит промежуточных результатов).
Множество действий.
Правило начала.
Правило окончания.
Правило определения расположения результата.
Здесь в качестве примеров уточнения понятия алгоритма мы рассмотрим Машину Тьюринга и Нормальные алгоритмы Маркова.
Машина Тьюринга.
Машиной Тьюринга называется формализм, предложенный для понятия алгоритма, английским математиком Аланом Тьюрингом. В 30-х годах нашего столетия Тьюринг занимался исследованием свойств вычислимых функций и объектом его внимания был вычислительный процесс.
В качестве исполнителя алгоритмов им был предложен автомат, состоящий из:
бесконечной ленты, разбитой на ячейки;
каретки, способной передвигаться над лентой, от ячейки к ячейке, считывать символы, записанные на ленте, записывать символы в ячейки.
В каждой ячейке ленты может быть записан только один из определенного множества символов, называемого алфавитом. За одно срабатывание каретка способна выполнить следующие действия:
считать символ из ячейки, над которой она находится;
записать символ в ячейку, над которой она находится;
переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте.
изменять свое внутреннее состояние.
Поясним последний пункт. Предполагается, что каретка может находиться в одном из состояний, из определенного множества состояний. Одним из ее действий, на ряду с перечисленными выше, является переход из одного состояния в другое.
В терминах, упомянутых выше семи параметров машину Тьюринга можно определить следующим образом.
Совокупность возможных исходных данных - алфавит D;
Совокупность возможных результатов - алфавит D;
Совокупность возможных промежуточных результатов - алфавит D;
Множество действий:
множество правил вида ap®bqw, где a,bÎ D; p,qÎ Q; wÎ {Л, П, Н}.
D - алфавит символов, которые могут появляться на ленте;
Q - множество символов, обозначающих состояния каретки.
Л, П, Н - символы, обозначающие передвижение каретки налево, направо или наместе соответственно.
Смысл правила ap®bqw состоит в следующем. Если каретка находится над ячейкой, в которой записан символ а, и каретка находится в состоянии p, то каретка должна:
записать в эту ячейку символ b (символ а при этом стирается),
из состояния p перейти в состояние q,
переместиться на следующую ячейку влево если w=Л, - вправо если w=П или остаться на месте если w=Н.
Правило начала: каретка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии qo
;
Правило окончания: есть специальное состояние, мы его будем обозначать символом ! из алфавита Q. Как только каретка переходит в состояние ! , она останавливается.
Например, если правило имеет вид ap®b!w , то после его выполнения вычисление считается законченным.
Правило расположения результата: справа от каретки до первого символа пустоты.
Дело в том, что пустота - это тоже символ, который мы будем обозначать символом L.
Пример 1. Построить Машину Тьюринга, вычисляющую функцию
U(n)=n+1 , где nÎ {0,1,2,3,4,5,6,7.8.9}.
Машина Тьюринга с алфавитом D={0,1,2,3,4,5,6,7.8.9} и Q={qo,
qs,
!},
где qo
- начальное состояние, а ! - конечное.
Нижеприведенная последовательность команд, реализует требуемую функцию.
| № команды | a | b |
| 1 | 0qo
®1qs H |
0qs
®0qs Л |
| 2 | 1qo
®2qs H |
1qs
®1qs Л |
| 3 | 2qo
®3qs H |
2qs
®2qs Л |
| 4 | 3qo
®4qs H |
3qs
®3qs Л |
| 5 | 4qo
®5qs H |
4qs
®4qs Л |
| 6 | 5qo
®6qs H |
5qs
®5qs Л |
| 7 | 6qo
®7qs H |
6qs
®6qs Л |
| 8 | 7qo
®8qs H |
7qs
®7qs Л |
| 9 | 8qo
®9qs H |
8qs
®8qs Л |
| 10 | 9qo
®0qo Л |
9qs
®9qs Л |
| 11 | Lqo
®1!Л |
Lqs
®L!H |
Рис.1.
Рассмотрим таблицу на рисунке 1. Часть а) реализует увеличение цифры в текущей клетке на 1. Команда 9qo
®0qo
Л учитывает возникновение единицы переноса в старший разряд. Обратите внимание, что состояние qo
сохраняется. Именно в этом состоянии мы увеличиваем цифру, в очередной клетке на единицу. Команда 11 в столбце а) - L qo
®1!Л учитывает тот случай, когда в результате переноса разрядность числа возрастает на единицу. Последовательность команд в столбце b) обеспечивает соблюдение правила расположения результата. А именно, надо позаботиться, чтобы после увеличения числа на единицу, вся запись числа на ленте оказалась справа от каретки, согласно правилу размещения результата.
Нетрудно заметить, что пара: символ на ленте под кареткой и текущее состояние каретки однозначно определяет ту команду, которую надо применять. Действительно, среди записанных команд нет двух с одинаковыми левыми частями. Именно благодаря этому свойству Машина Тьюинга обеспечивает свойство детерминированности алгоритма. Таким образом, каретка всякий раз однозначно определяет ту команду, которую надо выполнить. Заметим, что проверку последовательности команд Машины Тьюринга на детерминированность осуществить очень просто. Достаточно сравнить левые части всех команд и убедиться, что они все разные.
Теперь, когда мы немного освоились с работой Машины Тьюринга и ее устройством, сделаем одно замечание по поводу записи последовательности команд, которую мы будем называть программой Машины Тьюринга. Один способ записи показан на рисунке 1. Другой способ основан на том, что пара - (текущий символ, текущее состояние каретки) однозначно определяет правую часть любой команды.
Действительно, возьмем таблицу размером p×(m-1), где p=|D| - число символов алфавита, m=|Q| - число состояний каретки. В размерности указано (m-1) потому, что состояние ! не может встретиться в левых частях команд. Столбцы этой таблицы поименуем символами из D, а строки - символами из Q. Тогда в соответствующих полях таблицы надо будет записать лишь тройку из правых частей команд.
На рис. 2 показана табличная запись программы с рисунка 1.
№ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | L |
qo
|
1qS
Л |
2qS
Л |
3qS
Л |
4qS
Л |
5qS
Л |
6qS
Л |
7qS
Л |
8qS
Л |
9qS
Л |
0qo
Л |
1!Л |
qs
|
0qs
Л |
1qs
Л |
2qs
Л |
3qs
Л |
4qs
Л |
5qs
Л |
6qs
Л |
7qs
Л |
8qs
Л |
9qs
Л |
L!Н |
Рис.2.
Рассмотрим в качестве примера работу только что построенной Машины Тьюринга U1
для случая n=231. Первой выполненной командой будет команда 1a): 1qo
®2qs
H; после этой последуют команды 4b): 3qs
®3qs
Л и 2b): 2qs
®2qs
Л и наконец, 11b): Lqs
®L!H. Таким образом, сложность этого вычислительного процесса будет равна 4.
В общем случае сложность этого алгоритма будет равна k+1, где k - число десятичных цифр в записи числа. Докажем это утверждение. Для k=1 истинность этого утверждения очевидна. Пусть это утверждение верно для k=l. Докажем, что оно сохранит истинность и для k=l+1. Появление очередной цифры в старшем разряде числа потребует от нас вместо исполнения команды Lqs
®L!H или команды Lqo
®1!Л либо увеличить эту цифру на 1, т.е. выполнить одну из команд в столбце а), либо “перескочит
Обратите внимание, что вместе с оценкой сложности мы фактически доказали свойство конечности нашего алгоритма, т.е., что он обязательно остановится.
Пример 2. Построить Машину Тьюринга, вычисляющую
U((n)1
)=(n-1)1
,
где n>0 и (n)1
означает запись числа n в унарной форме, т.е. в виде . Другими словами, эта Машина Тьюринга с алфавитом D={ L, | }должна стирать одну палочку в записи числа. На рисунке 3 показана программа для этой машины.
| | | L | |
| qo
|
Lqs
Л |
|qo
Л |
| qs
|
|qs
Л |
L!H |
Рис.3
Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание qo
L. По условию n>0. Поэтому в этом “неправильном” случае машина будет зацикливаться. Нетрудно подсчитать, что сложность этого алгоритма равна n+1.
Пример 3. Построить Машину Тьюринга
U((n)1
)=(n)10
,
где n>0 и (n)10
- запись числа n в десятичной системе. Другими словами эта Машина Тьюринга приводит запись числа n из унарной формы в десятичную. Работу этой машины организуем следующим образом.
Изначально на ленте находится слово из одних | символов и каретка находится над крайне правым | символом. Сотрем один символ |, а перед словом из символов | поставим цифру 1. Затем опять сотрем крайне правый символ | , а затем увеличим цифровую запись слева от слова из | на 1 и т.д. Обратим внимание, что стирать палочки мы умеем, это делает Машина U2
((n)1
)=(n-1)1
и увеличивать десятичную запись числа на 1 тоже умеем, это делает машина U1
((n)10
)=(n+1)10
. Программа для этой машины показана на рисунке 4.
| L | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | ||
Нач. состояние Сти раем палочку (крайнеправый сим вол |) |
qo
|
Lqer
|
Lqe
|
1qer
|
2qer
|
3qer
|
4qer
|
5qer
|
6qer
|
7qer
|
8qer
|
9qer
|
0qer
|
ql
|
1qr
П |
|ql
Л |
1qer
H |
2qer
H |
3qer
H |
4qer
H |
5qer
H |
6qer
H |
7qer
H |
8qer
H |
9qer
H |
0qer
H |
|
Про дви-жение вправо до пер вой | , либо если нет | , то пе реход в q2l
|
qr
|
Lq2l
|
|q2r
|
1qr
|
2qr
|
3qr
|
4qr
|
5qr
|
6qr
|
7qr
|
8qr
|
9qr
|
0qr
|
Движе-ние влево до на чала слова из цифр и стоп |
q2l
|
L!H |
|qer
|
1q2l
|
2q2l
|
3q2l
|
4q2l
|
5q2l
|
6q2l
|
7q2l
|
8q2l
|
9q2l
|
0q2l
|
Движение вправо на | до пер вой пусто-ты |
q2r
|
Lq3l
|
|q2r
|
1qer
|
2qer
|
3qer
|
4qer
|
5qer
|
6qer
|
7qer
|
8qer
|
9qer
|
0qer
|
Сти раем палочку. Дви жемся до пер вой циф ры и увели чива ем ее на единицу |
q3l
|
Lqer
|
Lqd
|
1qer
|
2qer
|
3qer
|
4qer
|
5qer
|
6qer
|
7qer
|
8qr
|
9q3l
|
0q2l
|
qd
|
1qr
H |
|qd
Л |
2qr
H |
3qr
H |
4qr
H |
5qr
H |
6qr
H |
7qr
H |
8qr
H |
9qr
H |
0qr
Л |
1qr
Л |
Рис.4. Машина Тьюринга для U((n)1
)=(n)10
Оценим сложность этого алгоритма. В начале работы каретка пройдет (n-1) символ при движении влево и (n-1) символ при движении обратно, т.е. 2(n-1). На втором проходе - 2(n-2) и т.д. Отсюда число пройденных палочек, а следовательно и выполненных команд будет равно n(n-1). Машина n раз выполнит команду, увеличения текущей цифры на 1. Количество просмотров цифр будет равно ([log10
n]+1)([log10
n]).Таким образом, получаем
n(n-1)+n+[log10
n]× ([log10
n]+1) @ n2
+[log10
n(log10
n+1)]
Пример 4. Построить машину Тьюринга, для сравнения двух чисел a и b, заданных в унарной форме.
если
Пусть на ленте числа a и b заданы в унарной форме. Каретка располагается над лентой так, как показано на рисунке 5,
Рис.5.
т.е. над крайне правым символом | числа a . Cравнивать числа a и b будем, стирая попарно одну палочку в записи a и одну палочку в записи b. Если останутся палочки только в записи a, то значит a>b, если только в записи b, то a<b, а если палочек не останется вовсе, то a=b. На рисунке 6 показана программа для Машины Тьюринга, вычисляющей U1
.
| L | | | x | 1 | 0 | |
| qo
|
Lqer
H |
xqr
H |
xqer
H |
||
| qr
|
LqCHL
Л |
xql
H |
xqr
П |
||
| ql
|
LqCHR
П |
xqr
H |
xql
Л |
||
| qCHL
|
Lqa=b
П |
|qa>b
H |
xqCHL
Л |
||
| qCHR
|
Lq’a=b
Л |
|qa<b
H |
xqCHR
П |
||
| qa=b
|
1!H | |qer
H |
Lqa=b
П |
||
| q’a=b
|
1!H | |qer
H |
Lq’a=b
Л |
||
| qa>b
|
Lq’a>b
Л |
|qa>b
П |
xqa>b
П |
||
| q’a>b
|
1!H | |qa>b
Л |
Lq’a>b
Л |
||
| qa<b
|
Lqer
H |
|qa<b
Л |
0q’a<b
Л |
||
| q’a<b
|
Lq’a<b
П |
|qer
H |
xq’a<b
Л |
1qer
H |
0!H |
Рис.6.
Теперь уместно спросить, в чем же принципиальные отличия записи алгоритмов, в форме Машины Тьюринга от того, которое мы использовали в лекции 1?
Прежде всего в представленных данных. В алгоритме Евклида нахождения НОД мы говорили, что а и b представляют числа.
Что такое число? Какова форма его записи?
От ответов на эти вопросы будут зависеть правила действий над ними для вычисления разности, сравнения чисел и т.д. Поэтому сказать, что а и b - это числа не достаточно. Необходимы соответствующие уточнения, договоренности между исполнителями.
У Машины Тьюринга данные - это слова в некотором алфавите. Слово в алфавите - это конечная последовательность символов из определенного множества, называемого алфавит.
Второе принципиальное отличие - действия. При интуитивном рассмотрении понятия алгоритма мы использовали действия: положи, умножь, сложи, сравни и т. д., смысл которых мы считаем по умолчанию общеизвестным. Хотя, если предположить, что речь идет о числах в логарифмической системе счисления (см. Каут. “Искусство программирования”), то вряд ли можно считать, что смысл операции умножения является общеизвестным. В то же время, сравнить два символа: совпадают они или нет может каждый человек и заменить один символ на другой тоже.
Поэтому, запись алгоритма в терминах Машины Тьюринга более строгая, в том смысле, что она не имеет двусмысленностей, понимается однозначно. Отсюда и рассуждения о ее свойствах более четкие и строгие, чем в интуитивном смысле.
Однако, возникает другой вопрос. А любую вычислимую функцию можно описать в виде Машины Тьюринга? Ответ на этот вопрос Тьюринг сформулировал в виде тезиса, названного его именем.
Тезис Тьюринга: Для любой интуитивно вычислимой функции существует МТ, ее вычисляющая.
Это тезис, а не теорема. Его нельзя доказать, так как в нем используется понятие интуитивно вычислимой функции, смысл которого определен интуитивно, т.е. не строго.
Выводы :
А реализуют лишь подмножество (класс вычислимых функций) функции, рассматриваемых в курсе математического анализа;
Алгоритмизация решения задачи состоит в разбиении задачи на подзадачи, подзадач на подподзадачи и т.д., до тех пор, пока решение очередной подзадачи мы не сведем к действиям надлежащего исполнителя;
МТ можно строить из ранее построенных МТ.
Вопросы:
Квадратный корень из x - вычислимая функция?
Что такое вычислимая функция?
Как отличить вычислимую функцию от не вычислимой?
Множество вещественных чисел перечислимо?
Что такое перечислимое множество?
Мн-во четных целых чисел разрешимо относительно мн-ва целых чисел?
Сформулируйте условие разрешимости мн-ва В относительно мн-ва М.
Перечислить параметры для уточнения поняти А.
Как в МТ задаются исходные данные?
Как в МТ задаются возможные результаты?
Как в МТ задаются промежуточные результаты?
Как в МТ задается правило начала работы А?
Как в МТ задается правило окончания работы?
Как в МТ извлекается результат?
Можно ли МТ строить из других МТ?
Как можно объединять несколько МТ в одну МТ?