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

Глава 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 и двигается влево.