Задания для самостоятельной работы. 1. Преобразовать заданный автомат Мили в автомат Мура, а затем последний - в автомат Мили (в табличном и графическом виде)

 

1. Преобразовать заданный автомат Мили в автомат Мура, а затем последний - в автомат Мили (в табличном и графическом виде).

 

 

 

 

2. Для всех трёх автоматов из п. 1 определить реакцию на входное слово . Сравнить реакции автоматов и определить, являются ли они эквивалентными

5. МАШИНЫ ТЬЮРИНГА

Общие положения

 

Машина Тьюринга - это конечный автомат, снабжённый бесконечной лентой и читающей/записывающей головкой (просто головкой). Как и автомат, машина Тьюринга (МТ) описывается пятеркой (X, Y, Q, d, l). Здесь:

X={x₀, x₁, x₂, …, x_n} - входной алфавит, содержащий пустую букву x₀;

Y={y₀, y₁, y₂,…,y_n} - выходной алфавит;

Q={q₀, q₁, q₂, …, q_m} - множество внутренних состояний, причем q₀ - СТОП-состояние (в этом состоянии МТ не работает);

d: Q´X ®Q - функция переходов в следующее состояние;

l: Q´X ®Y - функция выходов.

В свою очередь, Y=X´U, где U={R, L, S} - команда на перемещение головки: R - сдвинуться вправо, L - влево, S - стоять на месте.

Задавая МТ [5], вместо двух функций можно пользоваться одной (совме-щающей работу входа и выхода): j: Q´X ® Q´X´U, сопоставляющей каждой паре (q_i, x_j) выходную тройку (q_k, u, x_l), uÎU. Функция j полностью описывает работу МТ и называется логической функцией машины Тьюринга. Таблица этой функции называется функциональной схемой, или программой машины Тьюринга. На каждом такте работы МТ головка обозревает в некоторой ячейке символ x_j, а сама МТ находится в некотором состоянии q_i, что описывается входной парой (q_i, x_j). В зависимости от входной пары МТ выполняет команду (q_k, u, x_l), u ÎU, т.е. записывает в обозреваемую ячейку символ x_l, передвигает головку в зависимости от значения u и переходит в новое состояние q_k. Если на некотором этапе работы МТ переходит в СТОП-состояние, то дальнейших изменений в машине не происходит - машина останавливается.

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

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

Пример 5.1. МТ А, описываемая пятеркой (X, Y, A, d, l), задана своей функциональной схемой (табл. 5.1) и имеет следующие алфавиты*:

 

Таблица 5.1

X={0, 1}; Y={y1, y2, y3}; A={A0, A1, A2}; y1=(0, R); y2=(1, R); y3=(1, L).     А
А1	0RA2	0RA2
А2	1RA1	1LA0

 

Рассмотрим два входных слова: x₁=0 1 0110 и x₂= 0 0000, и их преобразование машиной Тьюринга (подчеркнутая буква означает, что она обозревается головкой). Соответствующие конфигурации представлены в табл. 5.2. Видно, что МТ А применима к первому входному слову при конфигурации 1 и не применима к пустой ленте (конфигурация 2).

Таблица 5.2

Такт	Состояние	Слово на ленте	Такт	Состояние	Слово на ленте
	А1	…0 1 0110…		А1	… 0 0000…
	А2	…00 0 110…		А2	…0 0 000…
	А1	…001 1 10…		А1	…01 0 00…
	А2	…0010 1 0…		А2	…010 0 0…
	А0	…001 0 10…		А1	…0101 0 …

 

Условимся кодировать натуральные числа (с нулём) на ленте МТ, в алфавит которой входят буквы «0» (ноль) и «1» (единица), следующим образом: 0®1, n ®111…1 (n +1 единица).

(L) n+1 (R) … 0 1 11…1 …, qi

Говорят, что МТ стандартно воспринимает натуральное число n в состоянии q_i, если на её ленте имеется конфигурация:

 

(L) n1+1 n2+1 nm+1 (R) … 0 1 1…1011…10…011…10 …. qi

где (L) - левая зона (без ограничений), (R) - правая зона (обязательно пустая), читающая головка находится под крайней левой единицей. Аналогично МТ стандартно воспринимает набор (n₁, n₂, …, n_m) в состоянии q_i, если на ленте имеется конфигурация:

 

МТ М вычисляет функцию y = f (x₁, …, x_n), если выполнены следующие условия:

1. М применима к каждому набору (a₁, …, a_n), на котором y = f (x₁, …, x_n), определена, и если f (a₁, …, a_n)= y₀, то М, стандартно воспринимающая набор (a₁, …, a_n) в начальном состоянии, через конечное число тактов приходит в СТОП-состояние, имея на ленте число y₀.

2. М не применима к наборам, на которых функция f (x₁, …, x_n) не определена.

Функция называется вычислимой по Тьюрингу, если существует вычисляющая её МТ. Вычислимость по Тьюрингу является точным понятием.

Пример 5.2. Функция f(x) = x +1 вычислима по Тьюрингу, так как существует МТ В, которая вычисляет её. Функциональная схема МТ В приведена в табл. 5.3.

Пусть x = n -1 (на ленте записано n+1 единиц) и головка находится у левой границы числа. После n тактов машина передвинет головку к первому справа,

Таблица 5.3

В
В1	1SB0	1RB1

 

0, оставаясь в состоянии B₁; на следующем такте машина заменит 0 на 1 и остановится, не передвигая головку.