Формализация понятия алгоритма Машина Тьюринга (1006344)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

28 Формализация понятия алгоритма. Машина Тьюринга.

Алгоритм - точное предписание, которое задает потенциально осуществимый вычислительный процесс, начинающийся с произвольного исходного данного, из класса исходных данных, к которым данный алгоритм применим, и направленный на получение результата, полностью определенного этими исходными данными

Основные понятия теории алгоритмов.

Определение 1. Говорят, что алгоритм А вычисляет функцию (х), если:

1) область определения (х) и область применимости А совпадают;

2) Для любого х из области определения  верно: (х) = А(х) В этом случае функция (х) называется вычислимой функцией.

Определение 2. Говорят, что Алгоритм А разрешает множество М относительно множества X, где МХ, если:

1)Для любого х из множества М верно, что А(х) = "истина";

2)Для любого у из X, но у не принадлежит М, А(у) = "ложь ". В этом случае говорят, что множество М разрешимое.

Определение 3. Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел М, а совокупность результатов есть множество В. В этом случае В называется перечислимым множеством.

Основные свойства вычислимой функции:

1. Область применимости любого алгоритма - перечислимое множество. Следствие: алгоритмы не могут работать на множестве вещественных чисел.

2. Функция (х) вычислима тогда и только тогда, когда перечислим ее график, т.е. множество {(х,  (х))} перечислимо.

3. Множество МХ разрешимо относительно множества X, когда М и Х\М перечислимы.

Формализация понятия алгоритма.

Каждый алгоритм характеризуется 7 основными параметрами:

1. Совокупность возможных исходных данных;

2. Совокупность возможных результатов;

3. Совокупность возможных промежуточных результатов;

4. Правила непосредственной переработки (действия);

5. Правило начала;

6. Правило окончания;

7. Правило извлечения результата.

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

Машина Тьюринга вводится как уточнение вышеперечисленных 7 параметров.

Исполнитель алгоритмов - автомат, состоящий из:

• бесконечной ленты, разбитой на ячейки (в каждой ячейке ленты может быть записан только один символ из определенного множества символов, называемого алфавитом);

• каретки, способной передвигаться над лентой, от ячейки к ячейке, считывать символы, записанные на ленте, записывать символы в ячейки.

За одно срабатывание каретка способна выполнить следующие действия:

• считать символ из ячейки, над которой она находится;

• записать символ в ячейку, над которой она находится;

• переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте.

• изменять свое внутреннее состояние.

Машина Тьюринга

1. Совокупность возможных исходных данных - алфавит D;

2. Совокупность возможных результатов - алфавит D,

3. Совокупность возможных промежуточных результатов - алфавит D,

4. Множество действий:

множество правил вида ар—>bqw, где a,bD; р,qQ; w{Л, П, Н}, где

D - алфавит символов, которые могут появляться на ленте;

Q - множество символов, обозначающих состояния каретки;

Л, П, Н - символы, обозначающие передвижение каретки налево, направо или на месте соответственно.

Смысл правила ар—bqw состоит в следующем. Если каретка находится над ячейкой,
в которой записан символ а, и каретка находится в состоянии p, то каретка должна:

• записать в эту ячейку символ b (символ а при этом стирается),

• из состояния р перейти в состояние q,

• переместиться на следующую ячейку влево если w=Л, - вправо, если w=п или остаться на месте если w=н.

5. Правило начала: каретка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии q₀;

6. Правило окончания: есть специальное состояние, мы его будем обозначать
символом ! из алфавита Q. Как только каретка переходит в состояние !, она
останавливается.

Например, если правило имеет вид ар—>b!w , то после его выполнения
вычисление считается законченным.

7. Правило расположения результата: справа от каретки до первого символа
пустоты.

Машина Тьюринга

Пример 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={q₀, q_s, !}, q₀ - начальное состояние, а ! - конечное.

Сложность этого алгоритма равна k+1, где k - число десятичных цифр в
записи числа

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

Примеры машин Тьюринга:

1.U(n) = n+1;

2.U( <n в ун. записи> ) = <n-1 в ун. записи>;

3.U( <n в ун. записи> ) = n;(строиться как композиция МТ1 и МТ2)

Для каждого примера подсчитывается сложность.

1) А(n) = n+1

D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, П}

Первоначально каретка находится над последним символом.

0 1 2 3 4 5 6 7 8 9 П

A 1ЛQ 2ЛQ 3ЛQ 4ЛQ 5ЛQ 6ЛQ 7ЛQ 8ЛQ 9ЛQ 0ЛA 1Л!

Q ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ !

Сложность (кол-во выполненных правил подстановки): log₁₀ n+1

2) Унарная запись натурального числа : D = { |, П }

A(n) = n-1

Первоначально каретка находится над последним символом ‘|’.

| П

A ПЛQ |Л!

Q ЛQ !

Сложность: n (линейно зависит от величины исходных данных)

3) Унарная запись -> десятичная.

1. Стираем палочку

2. Влево до цифры или пустоты

3. Увеличиваем число на 1

4. Вправо до последнего '|'

5. Если ее нет, то влево до пустоты, стоп.

Выводы:

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

• Алгоритмизация решения задачи состоит в разбиении задачи на подзадачи, подзадач на подподзадачи и т.д.;

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

3

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)