Операции над машиной Тьюринга

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

 

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

X={x0, x1, x2, … , xn} - входной алфавит, содержащий пустую букву x0;

Y={y0, y1, y2,… ,yn} - выходной алфавит;

Q={q0, q1, q2, …, qm} - множество внутренних состояний, причем q0 - СТОП-состояние (в этом состоянии МТ не работает);

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

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

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

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

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

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

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

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

 

Рассмотрим два входных слова: x1=010110 и x2=00000, и их преобразование МТ (подчеркнутая буква означает, что она обозревается голов-
Таблица 5.1

А
А1 0RA2 0RA2
А2 1RA1 1LA0

 

кой). Соответствующие конфигурации представлены в табл. 5.2. Видно, что

МТ А применима к первому входному слову при конфигурации 1 и не применима к пустой ленте (конфигурация 2).

Таблица 5.2

Такт Состояние Слово на ленте Такт Состояние Слово на ленте
А1 …010110… А1 …00000…
А2 …000110… А2 …00000…
А1 …001110… А1 …01000…
А2 …001010… А2 …01000…
А0 …001010… А1 …01010…

 

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

(L) n+1 (R) … 0111…1 … , qi
Говорят, что МТ стандартно воспринимает натуральное число n в состоянии qi, если на её ленте имеется конфигурация:

 

(L) n1+1 n2+1 nm+1 (R) … 011…1011…10…011…10 … . qi  
где (L) - левая зона (без ограничений), (R) - правая зона (обязательно пустая), читающая головка находится под крайней левой единицей. Аналогично МТ стандартно воспринимает набор (n1, n2, …, nm) в состоянии qi, если на ленте имеется конфигурация:

 

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

1. М применима к каждому набору (a1, …, an), на котором y=f(x1, …, xn), определена, и если f(a1, …, an)=y0, то М, стандартно воспринимающая набор (a1, …, an) в начальном состоянии, через конечное число тактов приходит в СТОП-состояние, имея на ленте число y0.

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

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

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

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

В
В1 1SB0 1RB1

 

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

 

Операции над машиной Тьюринга

 

Рассмотрим две основные операции: композиция и итерация МТ. Пусть М1 и М2 - машины Тьюринга с общим алфавитом. Композицией (или произведением) машин Тьюринга М1 и М2 (в этом порядке) называется машина Тьюринга М (обозначение М=М1·М2), работающая следующим образом: если на вход машины М подать входное слово Р, то оно сначала преобразуется машиной М1, а затем полученное выходное слово подаётся на вход машины М2, и выходное слово машины М2 считается результатом преобразования входного слова Р машиной М: М(Р)=М2(М1(Р)).

Если известны функциональные схемы (ФС) машин М1 и М2, то ФС композиции М=М1·М2 строится следующим образом:

1. СТОП-состояние машины М1 отождествляется с начальным состоянием машины М2;

2. СТОП-состояние машины М2 объявляется СТОП-состоянием композиции М=М1·М2;

3. Остальные состояния М2 переобозначаются.

Пусть даны три МТ с общим алфавитом - М1, М2 и М3 и некоторое условие С. МТ, описываемая формулой , называется разветвлением машины М1 на машины М2 и М3 по признаку С, если она работает следующим образом: входное слово Р подаётся на вход машины М1, результат обработки ею слова Р (М1(Р)) подаётся на вход машины М2, если условие С выполнено, и на вход М3 - в противном случае.

Можно считать, что машина М1 имеет два СТОП-состояния и , таких, что машина М1 приходит в состояние в том случае, когда для М1(Р) выполнено условие С, и в - в противном случае.

Итерацией называется операция установления обратной связи от машины МJ к машине МI, при которой выходное слово машины МJ подаётся на вход машины МI (СТОП-состояние МJ отождествляется с начальным состоянием МI). При этом образуется цикл; начало и конец цикла будем обозначать точкой (·) над соответствующими буквами. Если в МТ содержится несколько циклов, то начала и концы циклов обозначаются двумя (··), тремя (···) и т.д. точками над соответствующими буквами.

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

Для построения ФС суперпозиции МТ поступают следующим образом (по умолчанию считаем, что у всех машин алфавиты одинаковы - 0 и 1).

1. Таблица составной машины имеет столько строк, сколько их в сумме во всех исходных машинах. Вначале эта таблица заполняется строками из ФС каждой исходной машины в том порядке, в каком они записаны в формуле (слева направо и сверху вниз).

2. Состояния в 1-й колонке формируемой таблицы заменяем состояниями общей машины так, чтобы их номера шли в порядке возрастания; во 2-й и в 3-й колонках проводим переобозначения состояний исходных машин в соответствии с проведенными заменами. При этом их СТОП-состояния не изменяются; не изменяются символы, записываемые на ленту, и символы команд на перемещение головки.

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

Пример 5.3.Пусть МТ С определена операцией умножения С=АВ[§], причём машины А и В заданы своими ФС (соответственно табл. 5.4. и 5.5).

Таблица 5.4 Таблица 5.5

А   В
А1 0RA2 0RA2 B1 0RB2 1RB3
А2 1RA1 1LA0 B2 1SB2 0LB1
  B3 0SB0 1LB3

 

Построим таблицу результирующей машины. Алфавит состояний для машины С будет: С={С0, C1, C2, C3, C4, C5}, где С1=А1, С2=А2, С3=В1, С4=В2, С5=В3; А0ºВ1=С3 - передача управления от А к В, С0ºВ0 - стоп-состояние общей МТ. ФС для машины М приведена в табл. 5.6.

Пример 5.4.Машины Тьюринга A, B и C заданы своими ФС (табл. 5.7-5.9). Суперпозиция этих машин описывается формулой: Построим ФС составной машины N.
Таблица 5.6

М
С1 0RC2 0RC2
С2 1RC1 1LC3
С3 0RC4 1RC5
С4 1SC4 0LC3
С5 0SC0 1LC5

Таблица 5.7 Таблица 5.8 Таблица 5.9

А   В   С
А1 1RA1 0LA2 В1 0RB2 0RB0(1) С1 0LC1 1RC2
А2 0RA2 1SA0 В2 1RB1 1SB0(2) С2 1RC1 0SC0

 

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

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

В соответствии с правилами формирования результирующей таблицы запишем алфавит состояний МТ N: {N0, N1, N2, N3, N4, N5, N6}; здесь обозначено: N1=B1, N2=B2, N3=C1, N4=C2, N5=A1, N6=A2.

 

Таблица 5.10

Передача управления и остановка машины N определяются следующими выражениями: B0(1)ºC1=N3, B0(2)ºA1=N5, A0ºB1=N1, N0ºC0. Переобозначив состояния в соответствии с приведенными выражениями, получим ФС машины N (табл. 5.10).  
N
N1 0RN2 1RN3
N2 1RN1 1SN5
N3 0LN3 1RN4
N4 1RN3 0SN0
N5 1RN5 0LN6
N6 0RN6 1SN1

 

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

 

1. Используя правила композиции и ветвления, составить программу (ФС) МТ N, которая состоит из машин A, B, C, D.

A   B   C   D
A1 0RA1 0SA2   B1 0RB2 1RB0(1)   C1 1RC1 0RC2   D1 0RD2 1SD0(1)
A2 0SA0(1) 1RA2   B2 1LB1 1SB0(2)   C2 0SC0(1) 1SC0(2)   D2 1LD1 1SD0(2)

1. 4.

 
 


2.

3.

 

2. Исследовать работу полученной машины М для приведённых конкретных конфигураций.

 


* Для простоты мы будем использовать входной алфавит, содержащий две буквы, x0=0 и x1=1.

[§] Здесь и далее знак умножения опускается