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

СОДЕРЖАНИЕ

Введение………………………………………………………………………	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.