Практическая работа № 10

«ПРИМЕНЕНИЕ МАШИНЫ ТЬЮРИНГА К СЛОВАМ»

 

Цель работы: овладеть навыком работы с машиной Тьюринга

 

Ход выполнения работы:

 

1. Изучить теоретический материал.

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

3. Выполнить задание.

4. Ответить на контрольные вопросы.

5. Защитить выполненное задание.

 

Теоретический материал

 

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

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

Машина Тьюринга располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит А = { а ₀, а ₁..., а_n }.

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

Ради единообразия удобно считать, что среди букв внешнего алфавита А имеется «пустая буква», и именно она записана в пустую ячейку ленты. Условимся, что «пустой буквой» или символом пустой ячейки является буква а ₀.

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

Далее, в каждый момент времени машина Q способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых образует множество Q = { q ₀, q ₁,..., q_m }.

Среди состояний выделяются два – начальное q ₁ и заключительное (состояние остановки) q ₀. Находясь в состоянии q ₁ машина начинает работать. Попав в состояние q ₀, машина останавливается.

Работа машины Q определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда T (i, j) (i = 1, 2,..., m; j = 0, 1,..., n) представляет собой выражение одного из следующих видов:

 

 

где 0 £ k £ m, 0 £ l £ n. В выражениях первого вида символ С будем часто опускать.  

            Находясь в какой-либо момент времени в состоянии, отличном от состояния q ₀, машина совершает шаг, который полностью определяется ее текущим состоянием q_i и символом a_j, воспринимаемым ею в данный момент на ленте.

При этом содержание шага регламентировано соответствующей командой

 

 

где X Î {С, П, Л}.

Шаг заключается в том, что:

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

2) машина переходит в новое состояние q_k (оно также может совпадать с предыдущим состоянием q_i);

3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х = П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С.

В следующий момент времени (если q_k ¹ q ₀) машина делает шаг, регламентированный командой   и далее аналогично.

Поскольку работа машины, по условию, полностью определяется ее состоянием q_i, в данный момент и содержимым а_j обозреваемой в этот момент ячейки, то для каждых q_i и а_j (i = 1, 2,..., m; j = 0, 1,..., n) программа машины должна содержать одну и только одну команду, начинающуюся символами q_ia_j.

Поэтому программа машины Тьюринга с внешним алфавитом А = { а ₀, а ₁,..., a_n } и алфавитом внутренних состояний Q = { q ₀, q ₁,..., q_m } содержит m (n + 1) команд.

Слово в алфавите А или в алфавите Q, или в алфавите A È Q ­– любая последовательность букв соответствующего алфавита.

k -я конфигурация – изображение ленты машины с информацией, сложившейся на ней к началу k -го шага (или слово в алфавите А, записанное на ленту к началу k -го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина.

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

Конфигурация – заключительная, если состояние, в котором при этом находится машина, заключительное.

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

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

Будем говорить, что непустое слово a в алфавите А \{ а ₀} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово a.

Стандартное положение – начальное (заключительное), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q ₁ (соответственно в состоянии остановки q ₀).

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

 

Образец выполнения

 

1. Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 – символ пустой ячейки), алфавитом внутренних состояний Q = { q ₀, q ₁, q ₂} и со следующей функциональной схемой (программой):

 

В какое слово переработает эта машина слово 101, исходя из стандартного начального положения.

 

Решение

 

Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение:

На первом шаге действует команда: q ₁1 ® q ₁1П. В результате на машине создаётся следующая конфигурация

На втором шаге действует команда: q ₁0 ® q ₂0П. В результате на машине создаётся следующая конфигурация

       Третий шаг обусловлен командой q ₂0 ® q ₀1. В результате него создаётся конфигурация

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q ₀.

Таким образом, исходное слово 101 переработано машиной в слово 10101.

Задания

 

1. Дана машина Тьюринга с внешним алфавитом А = { а ₀, 1}, алфавитом внутренних состояний Q = {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇} и со следующей функциональной схемой (программой):

 

 

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

 

1) 11111

2) 111111

3) 1111

4) 1111111

5) 111

6) 1a₀111a₀a₀1111

7) 11а₀а₀111111

8) 11а₀111

 

Контрольные вопросы

 

1. Что такое машина Тьюринга

2. Что такое внешний алфавит и алфавит внутренних состояний машины Тьюринга

3. Как записываются команды машины Тьюринга

4. Из какого состояния машины Тьюринга начинает работу

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