4. Операции над машинами Тьюринга
Для понимания того, что конкретная машина решает данную задачу, возникает необходимость в содержательных пояснениях. Для того, чтобы сделать эти пояснения более формальными и точными, будем использовать блок-схемы и некоторые операции над машинами Тьюринга.
Теорема 7.
Если функция
и
вычислимы по Тьюрингу, то их композиция
также вычислима по Тьюрингу.
Доказательство. Пусть Т1
– машина, вычисляющая
,
а Т2 – машина, вычисляющая
и множества их состояний соответственно
и
.
Построим диаграмму переходов машины Т
из диаграммы Т1 и Т2
следующим образом: отождествим начальную
вершину
диаграммы машины Т2 с
конечной вершиной
диаграммы машины Т1 (для
систем команд это равносильно тому, что
систему команд Т2 приписываем
к системе команд Т1 и при
этом
в командах Т1 заменяем на
).
Получим диаграмму с n1
+ n2
– 1 состояниями. Начальным состоянием
машины Т объявим
,
а заключительным –
.
Для простоты обозначений будем считать
f1 и f2
числовыми функциями одной переменной.
Пусть f2(f1(x))
определена. Тогда
и
.
Машина Т пройдет ту же последовательность
конфигураций с той разницей, что вместо
она перейдет в
.
Эта конфигурация является стандартной
начальной конфигурацией для машины Т2,
поэтому
.
Но так как все команды Т2
содержатся в Т, то
и, следовательно,
.
Если же f2(f1(x)) не определена, то Т1 или Т2 не остановится, а значит, и машина Т не остановится. Следовательно, машина Т вычисляет f2(f1(x)).
Построенную таким образом машину Т будем называть композицией машин Т1 и Т2 и обозначать Т2(Т1), а также изображать блок-схемой (рис. 3.5).
Рис. 3.5. Блок-схема композиции Т2(Т1)
Эта блок-схема всегда предполагает, что исходными данными машины Т2 являются результаты Т1. При этом они уже «готовы к употреблению», так как благодаря вычислимости (которая существенна при композиции) заключительная конфигурация Т1 легко превращается в стандартную начальную конфигурацию Т2.
Так как машина Тьюринга вектор над
воспринимает как слово в алфавите
,
определение композиции и теорема 7
остается в силе, если Т1 и
Т2 вычисляют функции от
нескольких переменных. Важно лишь, чтобы
данные для Т2 были в
обусловленном виде подготовлены машиной
Т1. Это хорошо видно на
следующем примере.
Пример 6.
Рис. 3.6. Диаграмма переходов машины
Машина, диаграмма которой приведена на
рис. 3.6, – это машина Т+(Ткоп).
Она вычисляет функцию f(x)=2x
для
.
При том машина Ткоп строит
двухкомпонентный вектор, а Т+
вычисляет функцию от двух переменных.
Для удобства последующих построений установим следующий важный факт.
Теорема 8. Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой. Иначе говоря, для любой машины Тьюринга Т существует эквивалентная ей машина TR с правой полулентой (аналогичная теорема формулируется для левой полуленты).
Рассмотрим теперь вычисление предикатов
на машинах Тьюринга. Говорят, что машина
Тьюринга вычисляет предикат
(
– слово в
),
если
,
где
Т,
когда
истинно, и
F,
когда
ложно. Если
не определен, то машина Тьюринга не
останавливается. При обычном вычислении
предиката уничтожается
,
что не всегда удобно, особенно если
после Т должна работать другая
машина. Поэтому введем понятие вычисления
с восстановлением. Говорят, что машина
Тьюринга вычисляет
с восстановлением, если
.
Лемма.
Если существует машина Тьюринга (
),
вычисляющая
,
то существует и
,
вычисляющая
с восстановлением.
Доказательство. Вычисление с восстановлением можно представить следующей последовательностью конфигураций:
.
Первая часть этой последовательности
реализуется машиной Ткоп;
вторая – простым сдвигом головки до
маркера *; третья – машиной ТR,
вычисляющей
на правой полуленте(одного копирования
мало для восстановления, так как копию
может испортить основная машина Т,
нужна машина, не заходящая влево от
);
четвертая – переносом
в крайнее левое положение. Машина Т
является композицией указанных четырех
машин.
Пример 7.
Рис. 3.7. Диаграмма переходов машины « – четное число»
Машина с диаграммой на рис. 3.7 вычисляет предикат « – четное число»: головка достигает конца числа в состоянии q2, если число единиц четно, и в состоянии q3, если число единиц нечетно, после чего она перемещается в исходное положение в состоянии q4 либо q5 и печатает Т или F соответственно.
Для того, чтобы этот предикат вычислялся
с восстановлением, достаточно в петлях
q4 и q5
не стирать, а сохранять единицы, т.е.
заменить команды
на команды
.
Так как машина Тьюринга с алфавитом А*
= {T, F}
и командами q1T
qzFE
и q1F
qzTE
вычисляет отрицание логической
переменной, то из вычислимости всюду
определенного предиката
следует вычислимость
.
Пусть функция
задана описанием: «если
истинно, то
,
иначе
».
(Под «иначе» имеется в виду «если
ложно»; если
не определено, то
также не определено.) Функция
называется развилкой или условным
переходом к
и
по условию
.
Теорема 9. Если функции , и предикат вычислимы по Тьюрингу, то развилка и по условию также вычислима.
Доказательство. Пусть Т1
– машина с состояниями
и системой команд
,
вычисляющая g1;
Т2 – машина с состояниями
и системой команд
,
вычисляющаяся g2;
Тр вычисляет с восстановлением
.
Тогда машина Т, вычисляющая развилку
и
по условию
,
– это композиция Тр и
машины Т3, система команд
которой имеет следующий вид:
Т
F
.
Первые две из новых команд передают управление системе команд или в зависимости от значения предиката . Третья команда введена для того, чтобы Т3 имела одно заключительное состояние q2z. Отсутствие символа ленты в этой команде означает, что она выполняется при любом символе.
Построенную в теореме 9 машину Т будем называть развилкой машин Т1 и Т2 по условию Тр и обозначать Траз(Т1, Т2, ТР), а также изображать блок-схемой (рис. 3.8).
Рис. 3.8. Блок-схема развилки машин Траз(Т1, Т2, ТР).
Пусть функция
задана описанием: «пока истинно
,
вычислять
,
иначе
».
Функция
называется повторением или циклом
от
и
по условию
.
Теорема 10. Если функции , и предикат вычислимы по Тьюрингу, то цикл и по условию также вычислим.
Доказательство. Сохраняя обозначения из доказательства предыдущей теоремы, введем машину Т, вычисляющую и по условию , – это композиция Траз и машины Т3, система команд которой имеет следующий вид:
Т
F
.
Первые две из новых команд передают управление системам команд или в зависимости от значений предиката . Третья команда отождествляет начальную вершину qp1 диаграммы машины Траз с конечной вершиной q1z диаграммы Т1 (т.е. после вычисления переходим к новой проверке условия ). Конечное состояние машины Т есть состояние q2z.
Построенную в теореме 10 машину Т будем называть циклом машин Т1 и Т2 по условию Тр и обозначать Тцикл(Т1, Т2, ТР), а также изображать блок-схемой (рис. 3.9).
Рис. 3.9. Блок-схема цикла машин Тцикл(Т1, Т2, ТР).
Пример 8. В примере 4 было описано построение машины Т+ для сложения двух чисел. На рис. 3.10 приведена диаграмма машины Т++ для сложения n чисел (n = 1, 2, …). Цикл из состояний q1, q2, q3 – это немного модифицированная и «зацикленная» машина Т+, в которой заключительное состояние совмещено с начальным. Сумма, полученная в очередной итерации цикла, является первым слагаемым следующего цикла. Состояние q4 реализует развилку. В нем проверяется условие – есть ли второе слагаемое. Если да (о чем говорит наличие маркера *), то происходит переход к следующему циклу; если нет ( о чем говорит после единицы), то машина выходит из цикла.
Рис. 3.10. Диаграмма переходов машины Т++.
Благодаря вычислимости композиции, развилки и цикла, словесные описания и язык блок-схем можно сделать достаточно точным языком описания работы машин Тьюринга. Каждый блок – это множество состояний, в котором выделены начальное и заключительное состояния и система команд. Переход к блоку – это обязательно переход в его начальное состояние. Машина Тьюринга, описываемая блок-схемой, – это объединение состояний и команд, содержащихся во всех блоках. В частности, блоком может быть одно состояние. Блоки, вычисляющие предикаты, обозначим буквой Р.
Пример 9.
На рис. 3.11 приведена блок-схема машины
Тьюринга
,
осуществляющая умножение двух чисел:
.
Ее заключительное состояние – q03.
Рис. 3.11. Блок-схема машины .
Блоки реализуют следующие указания и вычисления:
P1 – вычислить с восстановлением предикат «оба сомножителя больше нуля»;
Т1 – стереть все непустые символы справа;
Т2 – установить головку у ячейки, следующей (вправо) за маркером *, маркер * заменить на ~;
Ткоп – см. пример 5, в
котором команду
надо заменить на команду
~
;
эта машина
раз копирует
;
после i-го цикла она
останавливается в конфигурации
(~
~
;
Т3 – вернуть головку к
крайнему слева непустому символу. После
-го
цикла этим символом оказывается ~ (или
*, если а = 1) и тогда происходит выход
из цикла и переход к
;
работает как Т++ с той разницей, что числа, которые она суммирует, разделены двумя видами маркеров: ~ и *. Для этой цели ко всем командам с маркером * в левой части добавлены такие же команды для маркера ~.
