Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TEMA_3_1.doc
Скачиваний:
3
Добавлен:
01.05.2025
Размер:
994 Кб
Скачать
☆

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) и тогда происходит выход из цикла и переход к ;

работает как Т++ с той разницей, что числа, которые она суммирует, разделены двумя видами маркеров: ~ и *. Для этой цели ко всем командам с маркером * в левой части добавлены такие же команды для маркера ~.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]