Детерминированные машины Тьюринга

СОДЕРЖАНИЕ

Введение………………………………………………………………………	5
ГЛАВА 1. Способы представления детерминированных машин Тьюринга……………………………………………………………………	6
Детерминированные машины Тьюринга………………………….. Способы представления машины Тьюринга…………………….... Новое представление машины Тьюринга в виде блок-схемы……	6 8 10
ГЛАВА 2. Сборник задач по теме «Детерминированные машины Тьюринга»……………………………………………………………………	13
Классификация задач по теме «Машины Тьюринга» по трудоемкости решения………………………………………………………… Принципы формирования сборника задач………………………..	13   18
ЗАКЛЮЧЕНИЕ	19
СПИСОК ЛИТЕРАТУРЫ………………………………………………….	20
ПРИЛОЖЕНИЕ. Сборник задач	21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Данная выпускная квалификационная работа представляет собой сборник задач по теме: «Детерминированные машины Тьюринга».

Цель исследовательской работы: целью данной работы является разработка сборника задач по разделу «Детерминированные машины Тьюринга» курса  «Анализ алгоритмов» для студентов направления 010300 Фундаментальная информатика и информационные технологии.

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

В первой главе идет теоретическое знакомство с машиной Тьюринга (определение, устройство, принцип работы). На примере показаны разные способы представления машины Тьюринга (в виде таблицы, в виде программы, в виде графа). Подробно расписано новое представление машины Тьюринга в виде блок-схемы.

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

В заключении представлены выводы о проделанной работе.

Приложение содержит сборник задач.

Новизна исследовательской работы:

• предложена классификация задач по теме «Детерминированные машины Тьюринга» по трудоемкости решения
• предложен новый способ представления машин Тьюринга в виде блок-схем.

Практическая значимость  заключается в том, что разработанное методическое пособие может быть использовано преподавателем  для проведения для проведения курса «Анализ алгоритмов»

 

Глава 1. Способы представления детерминированных машин Тьюринга

1.1 Детерминированные машины Тьюринга

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

1. Бесконечная лента,  разбитая на ячейки (равные клетки).  В клетке может быть записан только один символ  (буква)  из внешнего алфавита A. Пустая ячейка обозначается символом В.
2. Считывающая головка,  перемещающая вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А.  Она может сдвигаться только на одну ячейку вправо  (R),  влево  (L)  или оставаться на месте  (S).
3. Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний Q = {q0, q1, q2,..., qm}.

Два состояния машины имеют особое значение: q1 –  начальное состояние,  q0 – конечное состояние.

4. Устройство управления.

Выполняет следующие действия:

• изменяет считываемый  символ на новый символ;
• передвигает головку в одном из следующих направлений: R, L, S;
• изменяет на новое имеющееся состояние машины;

Такие действия устройства управления называют командой, которую можно записать в виде: 1q1->Вq2R,

где q1- состояние машины в данный момент;

1. считываемый символ;

В - символ, на который изменяется символ 1;

q2 - состояние машины в следующий момент.

 

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

На примере задачи покажем пример машины Тьюринга.

Пример: Даны два числа a и b, представленные в унарной системе счисления. На машине Тьюринга составить программу, которая найдет сумму этих чисел.

Машина начинает свою работу, обозревая самый левый непустой символ

	1	1	1	В	1	1
	В	1	1	В	1	1
	В	1	1	В	1	1
	В	1	1	В	1	1
	В	1	1	1	1	1

 

В начальный момент времени машина Тьюринга обозревает крайний левый непустой символ.

Когда машина видит первую единицу, она заменяет ее на пустой символ (В). Далее пропускает единицы, при этом двигается вправо (R). Если видит пустую ячейку, то записывает в нее символ 1.

Машина завершает свою работу (S).

 

1.2 Традиционные способы представления машины Тьюринга.

 Существует три традиционных способа представления машины Тьюринга: в виде программы, в виде таблицы, в виде графа.

Разберем на примере эти способы представления машин Тьюринга.

Пример: Даны два числа a и b, представленные в унарной системе счисления. На машине Тьюринга составить программу, которая найдет сумму этих чисел.

Машина начинает свою работу, обозревая самый левый непустой символ

1. Представление машины Тьюринга в виде программы:

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

Начальному шагу соответствует начальное состояние q1.

В левой части команды находится то, что видит машина в данный момент, а в правой части находится  то, что должно получиться и какое действие надо выполнить.

В качестве примера рассмотрим совокупность команд машины Тьюринга, которая найдет сумму двух чисел, представленных в унарной системе счисления:

            Bq1 -> Bq1R

1q1 -> Bq2R

Bq2 ->1q0S

1q2 -> 1q2R,

где q1- начальное состояние машины Тьюринга;

q0 –конечное состояние;

В – пустой символ;

L – движение машины влево;

R -  движение машины вправо.

 

2. Представление машины Тьюринга в виде таблицы:

Данное представление машины Тьюринга более упрощенное.  Первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит).

Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутреннее состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Нахождение суммы чисел в унарной системе счисления в таблице записано  следующим образом:

	1	В
q1	Bq2R	Bq1R
q2	1q2R	1q0S

 

где q1- начальное состояние машины Тьюринга;

q0 –конечное состояние;

В – пустой символ;

L – движение машины влево;

R - движение машины вправо.

 

 

3. Представление в виде графа:

Рассмотрим еще одно альтернативное представление машины Тьюринга в виде графа, где вершинами являются состояниями, возможные переходы между ними — ребрами.

Начало ребра помечено символом, который должен быть на ленте для активации перехода, а конец ребра помечен символом, который пишется на ленту, и командой перемещения головки («L», «R», «Н»).

Нахождение суммы чисел в унарной системе счисления в виде графа будет записано следующим образом:

 

 

 

1.3 Новое представление машины Тьюринга в виде блок-схемы:

В своей работе я предлагаю новое представление машины Тьюринга, которое сформировано в виде блок-схем.

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

 

Разберемся для начала с обозначение каждого блока.

Где - начальное состояние;

- действующая ячейка, например, если в ячейке 1,то работа машины идет по правой ветке блок-схемы, если не 1 (0) то пишется else,работа машины идет по левой ветке блок-схемы;

- команда, которую должна выполнить  машина;

- состояние перехода;

• - конечное состояние (завершение работы).

 

На примере задачи для нахождения суммы двух чисел в унарной системе счисления, решение представленное в виде блок схемы выглядит следующим образом:

 

Если в состоянии q1 машина видит 1, то работа работы идет по правой ветке  блок-схемы и видит команду, которая записана в блоке. Машина будет переходить в состояние q1 до тех пор, пока видит символ 1.

Если же встретился символ В (пустая ячейка), то работа машины идет по левой ветке блок-схемы и над веткой пишется слово else. Встретив символ В, машина переходит в состояние q2 и движение происходит влево.

В состоянии q2 машина будет переходить в то же состояние до тех пор, пока видит 1. Работа машины будет происходить по левой ветке блок-схемы. Но если встретиться В (пустая ячейка), автомат записывает в нее 1, переходя в следующее состояние q3. Работа будет происходить по правой ветке блок-схемы.

В состоянии q3 машина будет переходить в то же состояние до тех пор, пока видит 1. Работа будет происходить по правой ветке блок-схемы. Если встретиться В (пустая ячейка), автомат завершает свою работу, переходит в состояние q0.

Глава 2. Сборник задач по теме: «Детерминированные машины Тьюринга»

2.1 Классификация задач по теме «Машины Тьюринга» по трудоемкости решения

В сборнике предложена классификация задач в зависимости от трудоемкости решения.

Чем старше класс, тем решение задачи, находящейся в данном классе, сложнее.

Первый класс:

Первый класс задач по способу и алгоритму решения самый простой. Рассмотрим пример задачи первого класса.

Пример:  Считая слово Р записью числа в унарной системе счисления, увеличить это число на 1, приписав слева  символ 1. Машина начинает работу, обозревая самый левый непустой символ.

Решение:

 

q1 - пропускает знак В (пустой символ).

q2 – видит 1, переходит налево и записывает на пустом месте 1.

 

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

 

Второй класс задач:

Второй класс задач в отличие от первого немного сложнее.

Рассмотрим пример задачи второго класса.

Пример: На ленте машины Тьюринга записана последовательность, состоящая из 0 и 1. Разработать программу, которая найдет первую 1.

Машина начинает работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должна быть первая

слева 1.

Решение:

 

q1 - пропускает нули, но когда видит единицу - останавливается.

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

 

Третий класс задач:

Рассмотрим пример задачи третьего класса.

Пример: На ленте машины Тьюринга записано число в унарной системе счисления. Разработать программу, которая прибавит к этому числу 1.

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

 

Решение:

q1 - пропускает единицы, автомат двигается вправо(R);

q2 – пропускает единицы, автомат двигается влево (L);

q3 – в пустую ячейку записываем единицу и останавливаемся(S)

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

 

Четвертый класс задач:

Рассмотрим пример задачи четвертого класса.

Пример: На ленте машины Тьюринга содержится последовательность символов. Напишите программу для машины Тьюринга, которая каждый второй символ «+» заменит на «-».

Машина начинает свою работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должен быть самый левый непустой символ.

Решение:

q1 - пропускает символ «+», автомат двигается вправо (R);

q2 – автомат двигается влево, пропуская «+»;

q3 – автомат двигается влево, при этом заменяя каждый второй «+ »  на «-».

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

Пятый класс задач:

Рассмотрим пример задачи пятого класса.

Пример: Дана строка из символов a и b. Разработать машину Тьюринга, которая переместит все символы «а» в левую, а символы «b» - в правую части строки.

Машина начинает свою работу, обозревая самый левый непустой символ.

Решение:

 

 

q1 - пропускает символы а и b, двигаясь вправо (R);

q2 – пропускает символы b и двигается вправо (R), но когда видит символ а меняет на b, при этом двигается уже влево (L);

q3 - пропускает символы а и двигается вправо (R), когда видит b пропускает и двигается влево (L);

q4 – видит символ b, заменяет на а, двигаясь вправо (R).

 

В пятом  классе особенность заключается в том, что существует решение в виде машины Тьюринга, которое превышает по трудоемкости 1-4 классы задач.

2. 2. Принципы формирования сборника задач

В сборнике задачи  классифицированы по трудоемкости решения. Чем старше класс, тем решение задачи сложнее.

В сборнике представлено пять разделов. Разделы 1-5 содержат формулировки задач  разбор решения одной из задач раздела.

В каждом классе приводятся по пять задач. Для каждого класса приводится подробный пример решения задачи, представленный в текстовом варианте, в виде таблицы и в виде блок-схемы.

В конце сборника приводятся варианты решения всех задач, представленные в виде таблицы и в виде блок-схемы.

 

 

 

 

 

 

 

 

Заключение

 

Для достижения поставленной в начале работы цели было сделано следующее:

• Предложен новый способ представления машин Тьюринга в виде блок-схем.
• Предложена классификация задач по теме «Детерминированные машины Тьюринга» по трудоемкости решения.
• Составлен сборник задач по теме «Детерминированные машины Тьюринга».

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1.  Пильщиков В.Н. Учебно-методическое  пособие. Машина

Тьюринга и алгоритмы Маркова. Решение задач / Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. - М.: МГУ, 2006. – 47 с.

 2.  Фалина И.Н. Тема "Машина Тьюринга" в школьном курсе информатики [Текст] : к изучению дисциплины / И.Н. Фалина // Информатика (ПС). - 2006. - №8. - С. 11-16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  Приложение. Сборник задач

 

 

Cодержание

Введение…………………………………………………………………….	22
Раздел 1. Класс 1…………………………………………………………...	23
Раздел 2. Класс 2…………………………………………………………...	25
Раздел 3. Класс 3…………………………………………………………...	27
Раздел 4. Класс 4…………………………………………………………...	29
Раздел 5. Класс 5…………………………………………………………...	32
Варианты решения……………………………………………………….	35
Список литературы……………………………………………………….	58

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение:

 

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

Структура сборника позволит студентам перейти от простых задач к более сложным. Разделы в сборнике представлены по их нарастающей сложности.

В каждом разделе для каждой группы приводится пример решения задачи в виде таблицы и в виде блок-схемы.

В конце сборника приводятся варианты решения всех задач.

Сборник состоит из пяти разделов. В каждом разделе по пять задач.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Раздел 1. Класс 1.

Задача 1.1:

Считая слово Р записью числа в унарной системе счисления, увеличить это число на 1, приписав слева  символ 1. Машина начинает работу, обозревая самый левый непустой символ [1].

Решение:

Разберем подробно решение данной задачи.

Если в состоянии q1 машина видит 1,  то оставляет 1 и двигается вправо, при этом переходит в состояние q2.

В состоянии q2 машина видит пустой символ, записывает туда  1 и останавливается. Машина завершает свою работу.

Табличное представление решения задачи:

	B	1
q1	BRq1	1Lq2
q2	1Sq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

Задача 1.2:

Дан алфавит А ={a, b}.

Приписать слева к непустому слову его первый символ.

Машина начинает работу, обозревая самый левый непустой символ. [2]

 

 

Задача 1.3:

На ленте записан один символ из алфавита {1, 2}, если записан

символ 1 , то слева от него приписать одну звёздочку,

если записан символ 2, то слева от него приписать две звёздочки.

Машина начинает работу,  обозревая самый левый непустой символ.

 

Задача 1.4:

На ленте записан символ d.

Приписать к нему слева символы, чтоб получилось слово kod.

Машина начинает работу, обозревая самый левый непустой символ.

 

Задача 1. 5:

 

Дан алфавит А={p,h}. На ленте записано слово. Удалить в слове Р второй символ, если такой имеется.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

 

 

 

 

 

 

Раздел 2. Класс 2

Задача 2. 1:

На ленте машины Тьюринга записана последовательность, состоящая из       0 и 1. Разработать программу, которая найдет первую 1.

Машина начинает работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должна быть первая

слева 1.

Решение:

Разберем подробно решение данной задачи.

Машина двигается вправо до тех пор, пока видит символ 0, пропуская его. Если увидит символ 1, завершает свою работу.

Табличное представление решения задачи:

	0	1	B
q1	0Rq1	1Sq0	BSq0

 

Решение задачи, представленное в виде блок-схемы:

 

 

 

Задача 2.2:

Дан алфавит А = {a,b}. На ленте записано слово Р. Заменить в слове Р каждое вхождение символа а на b.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

Задача 2. 3:

На ленте записано слово в алфавите А = {a, b, c}.  На машине Тьюринга разработать программу, которая удалит слово.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

Задача 2. 4:

Даны два числа a и b, представленные в унарной системе счисления. На машине Тьюринга разработать программу, которая вычислит выражение a+b+1.

Машина начинает свою работу, обозревая самый левый непустой символ.

Задача 2.5:

Даны два числа a и b, представленные в унарной системе счисления. На машине Тьюринга составить программу, которая найдет сумму этих чисел.

Машина начинает свою работу, обозревая самый левый непустой символ. [1]

Задача 2.6:

Построить машину Тьюринга, проверяющую число на четность. Если входное число четное, то на ленте должно остаться «ч», в противном случае – «н». Число записано в двоичной системе счисления.

Машина начинает свою работу, обозревая самый левый непустой символ. [2]

 

Раздел 3.  Класс 3

Задача 3.1:

На ленте машины Тьюринга записано число в унарной системе счисления. Разработать программу, которая прибавит к этому числу 1.

Машина начинает свою работу, обозревая самый левый непустой символ.

В момент остановки машины текущим символом должен быть самый левый непустой символ.  [1]

Решение:

Разберем подробно решение данной задачи.

В этом классе задач машина проходит в одну сторону ленты и в обратную. В состоянии q1 машина пропускает все единички, при этом двигается вправо. Когда видит пустой символ, переходит в состояние q2 и двигается влево.