Методические рекомендации по выполнению практикума по учебной дисциплине "Теория алгоритмов" (Машина Тьюринга)

Министерство образования и науки Самарской области

Министерство имущественных отношений Самарской области

Государственное бюджетное образовательное учреждение

среднего профессионального образования

«Чапаевский губернский колледж»

 

 

 

 

 

 

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ СТУДЕНТАМ ПО ВЫПОЛНЕНИЮ ПРАКТИКУМА  ПО УЧЕБНОЙ ДИСЦИПЛИНЕ «Теория алгоритмов»

(Раздел 2. Конечные автоматы

Тема 2.2. Рекурсивные функции и понятие вычислимости)

 

специальность230115 Программирование в компьютерных системах

 

 

 

 

 

 

 

 

 

 

 

 

Чапаевск, 2014 год

Публикуется на основании решения

Методического совета

протокол № 2 от 10.01 2014

 

 

 

 

 

 

Автор:             Дикова В.Г., преподаватель общепрофессиональных и специальных дисциплин ГБОУ СПО «Чапаевский губернский колледж»

 

 

Редактор:       Следкова М.П., заместитель директора по учебно-методической работе образовательной программы среднего профессионального образования ГБОУ СПО «Чапаевский губернский колледж»

 

Рецензент:       Орлова Н.Н.,

 

 

 

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

Содержание

                                                                                                         Стр.

Пояснительная записка	4
Теоретическая справка	5
Примеры решения задач	9
Задания для самостоятельной работы	17
Контрольные задания	18
Список источников и литературы	20

 

Пояснительная записка

 

Методические рекомендации по выполнению практикума разработаны в помощь студентам специальности 230115 Программирование в КС для  изучения раздела «Конечные автоматы» по дисциплине «Теория алгоритмов».

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

При разработке практических заданий учитывались требования к результатам освоения учебной дисциплины, сформулированные в ФГОС СПО III поколения.

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

уметь:

-          строить принципиальные схемы конечных автоматов;

-          использовать систему команд машины Тьюринга для записи алгоритма решения задачи;

-          предупреждать недопустимые действия, ведущие к аварийной остановке машины.

знать:

-          основные модели алгоритмов;

-          методы построения алгоритмов;

-          способы построения конечных автоматов;

-          основной тезис Тьюринга;

-          устройство машины Тьюринга;

-          систему команд машины Тьюринга.

 

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

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

Теоретическая справка

 

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

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

Во-вторых, машина Тьюринга снабжена потенциально бесконечной памятью. Что значит «потенциально бесконечная память»? Это значит, что хотя в каждый момент ее память хранит лишь конечное количество информации, однако для этого количества информации нет никакой верхней границы. Вообразим такую память машины Тьюринга в виде ленты, разделенной на клеточки — ячейки памяти, — которая может быть продолжена вправо сколько угодно

В каждой ячейке может храниться только один знак из конечного множества знаков, называемого алфавитом машины Тьюринга, эти же знаки называются буквами алфавита. Ячейка может оказаться и пустой. Ради удобства договоримся: когда ячейка пустая, считать, что в ней хранится специальная буква алфавита, которую мы обозначим через s₀ и назовем пустой буквой. Таким образом, в каждой ячейке ленты в любой данный момент находится одна и только одна буква алфавита А = {s₀, s₁, s₂, ... ,s_k}, причем только конечное число ячеек заполнено буквами из А, отличными от пустой буквы s₀.

Машина Тьюринга снабжена (в нашем воображении) управляющей головкой, которая в каждый момент обозревает (воспринимает) лишь одну ячейку памяти и может изменить информацию, находящуюся в ней. Представить это можно следующим образом: если в какой-то момент букву в обозреваемой ячейке нужно заменить другой, то старая буква стирается и в ячейку вписывается новая (так же, как на магнитофонной ленте при новой записи автоматически стирается старая запись). Если эту операцию записать в общем виде «s_i®s_j», т. е. буква s_i заменена буквой s_j, то можно выделить следующие частные случаи:

а) i = j, т. е. буква в обозреваемой ячейке не изменилась;

б) i ¹ j – буква изменилась, при этом:

б₁) если i = 0, то в пустую ячейку вписана буква s_j, и б₂) если j = 0, то стерта буква s_i в обозреваемой ячейке.

Управляющая головка за один такт работы машины может также передвинуться влево и воспринимать соседнюю слева ячейку (этот сдвиг головки будем обозначать через Л), управляющая головка может передвинуться вправо и воспринимать соседнюю справа ячейку (этот сдвиг мы обозначим через П), управляющая головка может остаться на месте и воспринимать ту же ячейку (этот «сдвиг» обозначим через Н). На рисунке изображен фрагмент ленты, а также управляющая головка. В обозреваемой ячейке хранится буква s_i.

Машина Тьюринга имеет конечное множество внутренних состояний: Q = {q₀, q₁, q₂, …, q_m}. В каждый данный момент времени машина Тьюринга находится в одном из своих внутренних состояний. После выполнения очередного такта работы машина может изменить свое внутреннее состояние и воспринимать ячейку в следующий момент уже в новом состоянии. Разумеется, внутреннее состояние может остаться и прежним. Если машина в какой-то момент времени попадет в состояние q₀, то ее работа заканчивается (состояние q₀ называется пассивным). Из множества Q выделим еще одно состояние — q₁ — начальное состояние. В этом состоянии машина всегда начинает свою работу.

Что умеет воображаемая машина?

За один такт работы она может:

1)      изменить содержимое обозреваемой ячейки памяти, т.е. заменить содержащуюся в ней букву алфавита другой;

2)      совершить сдвиг влево или вправо на одну ячейку или остаться на месте и

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

И больше машина Тьюринга ничего не умеет делать.

Может показаться, что это очень мало. В действительности, это очень много.

Порядок работы машины Тьюринга с алфавитом A={s₀, s₁, s₂, …, s_k} и множеством состояний Q = {q₀, q₁, q₂, ..., q_m} полностью определяется программой, представляющей собой таблицу, содержащую k+1 столбец и m строк. В клетке таблицы на пересечении i-го столбика (i=0, 1, 2, ..., k) и j-й строки (j=1, 2, ..., m) вписана команда, которую должна выполнить машина Тьюринга.

 

 

Если машина в какой-то момент воспринимает управляющей головкой ячейку, в которой записана буква s_i, и машина находится в состоянии q_j, команда будет записываться в виде трехбуквенного слова s_hTq_p, где ТÎ{Л, Н, П}, т. е. обозначает один из сдвигов управляющей головки.

Для выполнения команды машина проделывает следующую работу:

1)      буква s_i, находящаяся в обозреваемой ячейке, меняется на s_h;

2)      управляющая головка совершает сдвиг Т, т. е. Л, Н или П;

3)      машина переходит в состояние q_p.

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

Примеры решения задач

 

1. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q₁ обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

В состоянии q₁ машина ищет правый конец числа, в состоянии q₂ — пропускает знак “+”, при достижении конца последовательности — останавливается. В состоянии q₃ машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.

 

2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q₁ обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

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

 

3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

Состояние q1 — уменьшаем младшую (очередную) цифру на 1. Если она не равна нулю, то после уменьшения сразу — останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. В клетку [a0, q1] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять.

 

4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

Состояние q1 — уменьшаем младшую (очередную) цифру на 1. Если она больше 1, то после уменьшения — сразу останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1, то вместо нее пишем 0 и переходим в состояние q2.

Состояние q2 — после записи “0” в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова a0).

Состояние q3 — если записанный “0” является старшей незначащей цифрой, то его надо удалить из записи выходного слова.

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

 

5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.

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

Решение

Состояние q1: если встретили “(”, то сдвиг вправо и переход в состояние q2; если встретили “a0”, то останов.

Состояние q2: анализ символа “(” на парность, в случае парности должны увидеть “)”. Если парная, то возврат влево и переход в состояние q3. Состояние q3: стираем сначала “(”, затем “)” и переходим в q1.

 

6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

aaa —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

a —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

bbb —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

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

ab —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q1 — движение по цепочке из букв “a”, а q2 — состояние движения по цепочке из букв “b”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q1 или q2, т.е. встретили a0, машина должна остановиться, мы обработали всю строку.

Рассмотрим следующие варианты входных слов:

bba —> abb

bbbaab —> aabbbb

aabbbaab —> aaaabbbb

Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “b” —> abb (заменить первую букву в этой цепочке на “a”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q2.

 

7. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

состояние q1 — поиск правой (младшей) цифры числа;

состояние q2 — умножение очередной цифры числа на 2 без прибавления 1 переноса;

состояние q3 — умножение очередной цифры числа на 2 с прибавлением 1 переноса.

 

8. Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q₁обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

Машина Тьюринга для этой программы выглядит тривиально просто — в ней всего одно состояние. Такая машина Тьюринга выполняет следующие действия: стирает самый правый штрих, ищет разделитель (пустую ячейку) и в эту пустую ячейку помещает штрих, тем самым сформирована непрерывная последовательность штрихов длины n + m.

состояние q1 — поиск разделителя;

состояние q2 — передвинули штрих;

состояние q3 — проверка на конец (все ли штрихи передвинули).

 

9. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q₁ обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n. Известно, что m > n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

Штрихи начинаем стирать с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет.

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

Состояние q1 — поиск разделителя между массивами штрихов при движении справа налево;

состояние q2 — поиск левого штриха в массиве m;

состояние q3 — удаление левого штриха в массиве m;

состояние q4 — поиск разделителя при движении слева направо;

состояние q5 — поиск правого штриха в массиве n;

состояние q6 — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним;

состояние q7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.

 

10. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решение

При решении этой задачи следует обратить внимание на правильное выписывание алфавита:

A = {a0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т}.

Состояние q1 — поиск правого конца числа;

состояние q2 — анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q3, иначе переход в состояние q5;

состояние q3 — запись буквы “Д” справа от слова на ленте;

состояние q4 — запись буквы “А” справа от слова и останов машины;

состояние q5 — запись буквы “Н” справа от слова;

состояние q6 — запись буквы “Е” справа от слова;

состояние q7 — запись буквы “Т” справа от слова и останов машины.

 

11. Рассмотрим машину Тьюринга, программа которой задана таблицей:

Алфавит этой машины Тьюринга A = {s₀, 0, 1,2, 3, 4, 5, 6, 7, 8, 9}, а множество состояний: Q = {q₀, q₁}

Какую задачу решает эта машина?

Решение

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

s0

s0

s0

Из рисунка видно, что машина в состоянии q₁ обозревает самый правый символ записи на ленте. Из программы следует, что соответствующая паре (5,q₁) команда имеет вид: 6Нq₀. Согласно этой команде машина стирает цифру 5 в обозреваемой ячейке и помещает в ней цифру 6, остается на месте и переходит в состояние q₀, т. е. останавливается. Таким образом, машина прибавила 1 к исходному числу.

 

12. Какую работу выполнит машина Тьюринга, если она работает по программе:

Решение

Пусть перед началом работы машины ее память (лента) имеет вид

s0

s0

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

Состояние ленты после первого такта работы машины будет таким:

s0

s0

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

Условимся представлять числа 0, 1, 2, 3, ... словами в алфавите {|}: |, ||, |||, ||||, ... соответственно. Для представления на ленте набора целых неотрицательных чисел x₁, x₂, ..., x_n мы будем писать соответствующее число раз букву |, оставляя в точности одну пустую ячейку между каждыми двумя словами (конечными последовательностями букв |). Так, набор чисел 3, 0, 2 запишется на ленте следующим образом:

s0

|

|

|

|

s0

|

s0

|

|

|

s0

s0

Учитывая это, работу рассмотренной машины (назовем ее машиной A) можно охарактеризовать следующим образом: машина A, воспринимая последнее число набора чисел (в стандартном положении), увеличивает его на единицу и останавливается, воспринимая полученное число.

 

Задания для самостоятельной работы

1. На ленте машины Тьюринга записан массив из N звёздочек («*»). Задание: если N>5, то вывести N-2; если N=5, то вывести 1; если N<5, то вывести 2N.
2. Дано число в десятичной системе счисления. Умножить его на 11.
3. Дано число в десятичной системе счисления. Разделить его на 5.
4. Дано некоторое слово из букв «a» и «б». Обработать его так, чтобы слева были буквы «a», а справа–«б». Каретка находится над крайней левой буквой.
5. Дано число в десятичной системе счисления и число в троичной системе счисления. Найти их сумму и ответ записать в десятичной системе счисления (например, 576+100). Каретка располагается над крайней правой цифрой правого числа.
6. Дано число в десятичной системе счисления. Записать его цифры наоборот.
7. Дано число в двоичной системе счисления. Записать его цифры наоборот.
8. Дано число в восьмеричной системе счисления. Записать его цифры наоборот.
9. Данное число в двоичной системе счисления перевести в число в восьмеричной системе. Каретка располагается над крайней левой цифрой.
10. Дано слово из букв «a», «b», «c», «d». Сосчитать количество букв «a», записать его слева от данного слова через одну ячейку. Каретка располагается над крайней левой буквой.
11. Дано слово из букв «и», «к», «н», «о». Сосчитать количество букв «и», записать его справа от данного слова через одну ячейку. Каретка располагается над крайней правой буквой.
12. Поставить восклицательный знак в конце данного слова.
13. Записать ноль в начале и конце восьмеричного числа.
14. Записать ноль после каждой цифры троичного числа.

Контрольные задания

 

1. Машина C воспринимает набор чисел x₁, x₂, ..., x_n в стандартном положении и через одну пустую ячейку справа от этого набора записывает число 0, после чего останавливается, воспринимая 0.
2. Машина B воспринимает любое число из набора x₁, x₂, ..., x_n, уменьшает число палочек в его записи на одну и останавливается, воспринимая уменьшенное число.
3. Изобразите на ленте в алфавите {s₀, |} набор чисел 2, 3, 4, и пусть машина В воспринимает второе число в стандартном положении. Изобразите ленту после работы машины. Какой набор чисел будет записан на ней?
4. Изобразите на ленте в алфавите {s₀, |} набор чисел 1, 2, 3 и имитируйте работу машины C (изобразите ленту после каждого такта машины до ее остановки).
5. Машина D, отправляясь от воспринятого в стандартном положении числа, не самого правого на ленте, заполняет промежуток из пустых клеток (если имеется такой) между этим числом и ближайшим справа, оставляя между ними пустую клетку, и останавливается, воспринимая в стандартном положении получающееся число.
6. Изобразите на ленте числа 3 и 2 в алфавите {s₀, |}, отделенные друг от друга четырьмя пустыми ячейками. Имитируйте работу машины D применительно к этой записи на ленте.
7. Машина r, примененная к произвольной записи на ленте, сдвигает воспринимаемую ячейку на одну ячейку вправо и затем останавливается, не изменяя записи на ленте.
8. Машина l, примененная к произвольной записи на ленте, сдвигает воспринимаемую ячейку на одну ячейку влево и затем останавливается, не изменяя записи на ленте.
9. Машина R, отправляясь от воспринятого в стандартном положении числа, не самого правого на ленте, идет вправо к стандартному положению ближайшего справа числа.
10. Машина L, отправляясь от воспринятого в стандартном положении числа, не самого левого на ленте, идет влево к стандартному положению ближайшего слева числа.
11. Машина Тьюринга производит следующую операцию: если на ленте дан набор чисел x₁, x₂, ..., x_n, воспринимаемый машиной в стандартном положении, то машина в заключительном состоянии имеет на ленте набор чисел x₁, x₂, ..., x_n, 3, воспринимаемый ею также в стандартном положении.

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

1.      В.И.Игошин. Математическая логика и теория алгоритмов. [Текст]:  В.И. Игошин. – М.: Академия, 2008 г. – 448 с.

2.      Б.Я. Фалевич. Теория алгоритмов. [Текст]:  Б.Я. Фалевич. – М.: Машиностроение, 2004 г. – 160 с.

3.      Интернет–ресурс.http://softsearch.ru/programs/45-346-interpretator-mashiny-posta-download.shtml.