Формализация понятия алгоритма (стр. 2 из 3)
На рис. 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®2qsH; после этой последуют команды 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, т.е. выполнить одну из команд в столбце а), либо “перескочить” через эту цифру, выполнив одну из команд группы b), после чего остановиться, выполнив команду 11 b). Таким образом, после обработки k цифр наша Машина Тьюринга выполнит k команд, обработка последней цифры потребует 2-х команд. Тем самым, общее количество выполненных команд будет равно l+2=(l+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
Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание qoL. По условию 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 | LqerH | LqeH | 1qerH | 2qerH | 3qerH | 4qerH | 5qerH | 6qerH | 7qerH | 8qerH | 9qerH | 0qerH |
| ql | 1qrП | |qlЛ | 1qerH | 2qerH | 3qerH | 4qerH | 5qerH | 6qerH | 7qerH | 8qerH | 9qerH | 0qerH | |
| Продви-жение вправо до первой | , либо если нет | , то переход в q2l | qr | Lq2lЛ | |q2rH | 1qrП | 2qrП | 3qrП | 4qrП | 5qrП | 6qrП | 7qrП | 8qrП | 9qrП | 0qrП |
| Движе-ние влево до начала слова из цифр и стоп | q2l | L!H | |qerH | 1q2lЛ | 2q2lЛ | 3q2lЛ | 4q2lЛ | 5q2lЛ | 6q2lЛ | 7q2lЛ | 8q2lЛ | 9q2lЛ | 0q2lЛ |
| Движение вправо на | до первой пусто-ты | q2r | Lq3lЛ | |q2rП | 1qerH | 2qerH | 3qerH | 4qerH | 5qerH | 6qerH | 7qerH | 8qerH | 9qerH | 0qerH |
| Стираем палочку.Движемся до первойцифры и увеличиваем ее на единицу | q3l | LqerH | LqdЛ | 1qerH | 2qerH | 3qerH | 4qerH | 5qerH | 6qerH | 7qerH | 8qrH | 9q3lЛ | 0q2lЛ |
| qd | 1qrH | |qdЛ | 2qrH | 3qrH | 4qrH | 5qrH | 6qrH | 7qrH | 8qrH | 9qrH | 0qrЛ | 1qrЛ |
Рис.4. Машина Тьюринга для U((n)1)=(n)10
Оценим сложность этого алгоритма. В начале работы каретка пройдет (n-1) символ при движении влево и (n-1) символ при движении обратно, т.е. 2(n-1). На втором проходе - 2(n-2) и т.д. Отсюда число пройденных палочек, а следовательно и выполненных команд будет равно n(n-1). Машина n раз выполнит команду, увеличения текущей цифры на 1. Количество просмотров цифр будет равно
([log10n]+1)([log10n]).Таким образом, получаемn(n-1)+n+[log10n]× ([log10n]+1) @ n2+[log10n(log10n+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 | LqerH | xqrH | xqerH | ||
| qr | LqCHLЛ | xqlH | xqrП | ||
| ql | LqCHRП | xqrH | xqlЛ | ||
| qCHL | Lqa=bП | |qa>bH | xqCHLЛ | ||
| qCHR | Lq’a=bЛ | |qa<bH | xqCHRП | ||
| qa=b | 1!H | |qerH | Lqa=bП | ||
| q’a=b | 1!H | |qerH | Lq’a=bЛ | ||
| qa>b | Lq’a>bЛ | |qa>bП | xqa>bП | ||
| q’a>b | 1!H | |qa>bЛ | Lq’a>bЛ | ||
| qa<b | LqerH | |qa<bЛ | 0q’a<bЛ | ||
| q’a<b | Lq’a<bП | |qerH | xq’a<bЛ | 1qerH | 0!H |
Рис.6.
Теперь уместно спросить, в чем же принципиальные отличия записи алгоритмов, в форме Машины Тьюринга от того, которое мы использовали в лекции 1?
Прежде всего в представленных данных. В алгоритме Евклида нахождения НОД мы говорили, что а и b представляют числа.
Что такое число? Какова форма его записи?
От ответов на эти вопросы будут зависеть правила действий над ними для вычисления разности, сравнения чисел и т.д. Поэтому сказать, что а и b - это числа не достаточно. Необходимы соответствующие уточнения, договоренности между исполнителями.
У Машины Тьюринга данные - это слова в некотором алфавите. Слово в алфавите - это конечная последовательность символов из определенного множества, называемого алфавит.
Второе принципиальное отличие - действия. При интуитивном рассмотрении понятия алгоритма мы использовали действия: положи, умножь, сложи, сравни и т. д., смысл которых мы считаем по умолчанию общеизвестным. Хотя, если предположить, что речь идет о числах в логарифмической системе счисления (см. Каут. “Искусство программирования”), то вряд ли можно считать, что смысл операции умножения является общеизвестным. В то же время, сравнить два символа: совпадают они или нет может каждый человек и заменить один символ на другой тоже.
Поэтому, запись алгоритма в терминах Машины Тьюринга более строгая, в том смысле, что она не имеет двусмысленностей, понимается однозначно. Отсюда и рассуждения о ее свойствах более четкие и строгие, чем в интуитивном смысле.
Однако, возникает другой вопрос. А любую вычислимую функцию можно описать в виде Машины Тьюринга? Ответ на этот вопрос Тьюринг сформулировал в виде тезиса, названного его именем.
Тезис Тьюринга: Для любой интуитивно вычислимой функции существует МТ, ее вычисляющая.
Это тезис, а не теорема. Его нельзя доказать, так как в нем используется понятие интуитивно вычислимой функции, смысл которого определен интуитивно, т.е. не строго.