13293-1 (Формализация понятия алгоритма), страница 2

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

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

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

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

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

Рис.3

Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание q_o. По условию 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.

Рис.4. Машина Тьюринга для U((n)₁)=(n)₁₀

Оценим сложность этого алгоритма. В начале работы каретка пройдет (n-1) символ при движении влево и (n-1) символ при движении обратно, т.е. 2(n-1). На втором проходе - 2(n-2) и т.д. Отсюда число пройденных палочек, а следовательно и выполненных команд будет равно n(n-1). Машина n раз выполнит команду, увеличения текущей цифры на 1. Количество просмотров цифр будет равно ([log₁₀n]+1)([log₁₀n]).Таким образом, получаем

n(n-1)+n+[log₁₀n] ([log₁₀n]+1) n²+[log₁₀n(log₁₀n+1)]

Пример 4. Построить машину Тьюринга, для сравнения двух чисел a и b, заданных в унарной форме.

если

Пусть на ленте числа a и b заданы в унарной форме. Каретка располагается над лентой так, как показано на рисунке 5,

Рис.5.

т.е. над крайне правым символом | числа a . Cравнивать числа a и b будем, стирая попарно одну палочку в записи a и одну палочку в записи b. Если останутся палочки только в записи a, то значит a>b, если только в записи b, то a1.

Рис.6.

Теперь уместно спросить, в чем же принципиальные отличия записи алгоритмов, в форме Машины Тьюринга от того, которое мы использовали в лекции 1?

Прежде всего в представленных данных. В алгоритме Евклида нахождения НОД мы говорили, что а и b представляют числа.

Что такое число? Какова форма его записи?

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

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

Второе принципиальное отличие - действия. При интуитивном рассмотрении понятия алгоритма мы использовали действия: положи, умножь, сложи, сравни и т. д., смысл которых мы считаем по умолчанию общеизвестным. Хотя, если предположить, что речь идет о числах в логарифмической системе счисления (см. Каут. “Искусство программирования”), то вряд ли можно считать, что смысл операции умножения является общеизвестным. В то же время, сравнить два символа: совпадают они или нет может каждый человек и заменить один символ на другой тоже.

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

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

Тезис Тьюринга: Для любой интуитивно вычислимой функции существует МТ, ее вычисляющая.

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

Выводы :

А реализуют лишь подмножество (класс вычислимых функций) функции, рассматриваемых в курсе математического анализа;

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

МТ можно строить из ранее построенных МТ.

Вопросы:

Квадратный корень из x - вычислимая функция?

Что такое вычислимая функция?

Как отличить вычислимую функцию от не вычислимой?

Множество вещественных чисел перечислимо?

Что такое перечислимое множество?

Мн-во четных целых чисел разрешимо относительно мн-ва целых чисел?

Сформулируйте условие разрешимости мн-ва В относительно мн-ва М.

Перечислить параметры для уточнения поняти А.

Как в МТ задаются исходные данные?

Как в МТ задаются возможные результаты?

Как в МТ задаются промежуточные результаты?

Как в МТ задается правило начала работы А?

Как в МТ задается правило окончания работы?

Как в МТ извлекается результат?

Можно ли МТ строить из других МТ?

Как можно объединять несколько МТ в одну МТ?

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/