Реферат: Формализация понятия алгоритма

где q_o - начальное состояние, а ! - конечное.

Нижеприведенная последовательность команд, реализует требуемую функцию.

№ команды	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. Команда 9q_o ®0q_o Л учитывает возникновение единицы переноса в старший разряд. Обратите внимание, что состояние q_o сохраняется. Именно в этом состоянии мы увеличиваем цифру, в очередной клетке на единицу. Команда 11 в столбце а) - L q_o ®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.

Рассмотрим в качестве примера работу только что построенной Машины Тьюринга U₁ для случая n=231. Первой выполненной командой будет команда 1a): 1q_o ®2q_s H; после этой последуют команды 4b): 3q_s ®3q_s Л и 2b): 2q_s ®2q_s Л и наконец, 11b): Lq_s ®L!H. Таким образом, сложность этого вычислительного процесса будет равна 4.

В общем случае сложность этого алгоритма будет равна k+1, где k - число десятичных цифр в записи числа. Докажем это утверждение. Для k=1 истинность этого утверждения очевидна. Пусть это утверждение верно для k=l. Докажем, что оно сохранит истинность и для k=l+1. Появление очередной цифры в старшем разряде числа потребует от нас вместо исполнения команды Lq_s ®L!H или команды Lq_o ®1!Л либо увеличить эту цифру на 1, т.е. выполнить одну из команд в столбце а), либо “перескочить” через эту цифру, выполнив одну из команд группы b), после чего остановиться, выполнив команду 11 b). Таким образом, после обработки k цифр наша Машина Тьюринга выполнит k команд, обработка последней цифры потребует 2-х команд. Тем самым, общее количество выполненных команд будет равно l+2=(l+1)+1, что и требовалось доказать.

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

Пример 2. Построить Машину Тьюринга, вычисляющую

U((n)₁ )=(n-1)₁ ,

где n>0 и (n)₁ означает запись числа n в унарной форме, т.е. в виде . Другими словами, эта Машина Тьюринга с алфавитом D={ L, | }должна стирать одну палочку в записи числа. На рисунке 3 показана программа для этой машины.

|	L
qo	Lqs Л	|qo Л
qs	|qs Л	L!H

Рис.3

Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание q_o L. По условию n>0. Поэтому в этом “неправильном” случае машина будет зацикливаться. Нетрудно подсчитать, что сложность этого алгоритма равна n+1.

Пример 3. Построить Машину Тьюринга

U((n)₁ )=(n)₁₀ ,

где n>0 и (n)₁₀ - запись числа n в десятичной системе. Другими словами эта Машина Тьюринга приводит запись числа n из унарной формы в десятичную. Работу этой машины организуем следующим образом.

Изначально на ленте находится слово из одних | символов и каретка находится над крайне правым | символом. Сотрем один символ |, а перед словом из символов | поставим цифру 1. Затем опять сотрем крайне правый символ | , а затем увеличим цифровую запись слева от слова из | на 1 и т.д. Обратим внимание, что стирать палочки мы умеем, это делает Машина U₂ ((n)₁ )=(n-1)₁ и увеличивать десятичную запись числа на 1 тоже умеем, это делает машина U₁ ((n)₁₀ )=(n+1)₁₀ . Программа для этой машины показана на рисунке 4.

L	|	1	2	3	4	5	6	7	8	9	0
Нач. состояние Сти раем палочку (крайнеправый сим вол |)	« 1 2 3 4 5 6 7 8 » К-во Просмотров: 372 Бесплатно скачать Реферат: Формализация понятия алгоритма >>> Скачать <<< Меню Поиск