Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 34
Текст из файла (страница 34)
Однако в конкретных случаях возможны и более простые способы восстановления а. Пример 5.6. Машина с диаграммой па рис, 5.7 вычисляет предикат «а — четное число»: головка достигает конца числа в состоянии дм если число единиц четно, и в состоянии д„если число единиц нечетно, после чего она перемещается в исходное положение в состоянии д» либо дз и печатает И либо Л соответственно.
Для того чтобы этот преднкат вычислялся с восстановлением, достаточно в петлях д4 н д5 не стирать, а сохранять единицы, т. е. заменить команды 1-+ХТ. на команды 1-~-1.. Так как машина Тьюринга с алфавитом А„,„=(И, Л) и командами д,И-~д,ЛЕ и д~Л-~.д, ИЕ вычисляет отрицание логической переменной, то из вычислимости всюду определенного Р(а) следует вычислнмость Р(о).
Пусть функция 1(и) задана описанием; «если Р(а) истинно, то 1(а) =д1(а), иначе 1(и) =52(а)» (под «иначе» имеется в виду «если Р(а) ложно»; если же Р(и) не определен, то 1(а) также не определена). Функция )(а) называ- ется разветвлением нли условным переходом нд~ (и) и я»(а) по условию Р(а). Теорема 5.3. Если д~(и), д2(а) и Р(а)'вычислимы по Тьюрингу, то разветвление а, и д, по Р также вычислимо.
ПУсть Т~ — машина с состоЯниЯми Чп, Чнь ..., Чьь и системой команд Хн вычисляющая я',; Тз — машина с состояНиЯми Чм, Ч»», ..., Чьм и системой команд Хм вычислЯющаЯ д»; Те вычисляет с восстановлением Р(а). Тогда машина Т, вычисляющая разветвлепне д, и д~ по Р, — зто композиция Т, и машины Т„система команд Х, которой имеет следующий вид: В» = зч0л2(.) (Чи Π— '7 Ч»1 7с Ч»1'Ч-')421 7с Чм-~. Ч2гЕ) .
Первые две из новых команд передают управление'системам команд Х, или Х» в зависимости от значения предиката Р(а). Третья команда введена для того, чтобы Т, имела одно заключительное состояние Ч2з. Отсутствие символа ленты в этой команде означает, что она выполняется при любом символе. П Разветвление встречается в структуре диаграмм переходов многих машин Тьюринга. Пример 5.7. а. В примере 5.4, а было описано построение машины Т+ для сложения двух чисел.
На рис, 5,8 приведена диаграмма машины Т+ч. для сложения и чисел (и= =1, 2...). Цикл из состоЯний Чь Чм Ч, — это «зацикленнаЯ» машина Т+, в которой заключительное состояние совмеще- 7. 1Е 1~ 1й Рис. 6.8 166 ачальным. Сумма, полученная на очередном цикле, ся первым слагаемым следующего цикла. Состоя- реализует разветвление. В нем проверяется условие— н второе слагаемое.
Если да (о чем говорит наличие а ), то происходит переход к следующему циклу; т (о чем говорит Х после единиц), то машина выходит ла. Пусть машина Т с алфавитом Аг н с А„„=(1) не яв- правильно вычисляюще6 и ее заключительная конф урацня стандартна, но может содержать любые символы из Аг (кроме пробелов), а результат интерпретируется как число, равное числу единиц на ленте. Построим для Т машину Т', которая работает как Т~+, а все символы, кроме 1 и Х, она воспринимает как маркеры, т. е.
команды для них — те же, что и для ', Тогда Т' соберет все единицы , ++ в один массив и, следовательно, Т+ (Т(а)) правильно вычисляет' функцию, вычисляемую машиной Т. Пример 5.7, а иллюстрирует важный частный случай разветвления — выход из цикла по условию, хорошо известный в программировании. В словесных описаниях (см. пример 5.1) н во многих языках программирования (например, в АЛГОЛе) этот случай формулируется так: повторять вычисление (~ до тех пор, пока истинно условие Р; если Р ложно, пеРейти к вычислению 1ь Благодаря вычислимости композиции и разветвления словесные описания и язык блок-схем можно сделать вполне точным языком для описания работы машин Тьюринга. Каждый блок — это множество состояний, в котором выделены начальное и заключительное состояния, и система команд. Правильное вычисление для промежуточных блоков не обязательно, поэтому при стыковке блоков важно согласовывать всю конфигурацию. Переход к блоку — это обязательно переход в его начальное состояние.
Машина Тьюринга, описываемая блок-схемой, — это объединение состояний и команд, содержащихся во всех блоках. В частности, блоком может быть одно состояние. Блоки, вычисляющие предикаты, обозначим буквой Р. Пример 5.8. На рис. 5.9 приведена блок-схема машины Тьюринга Т„, осуществляющей умножение двух чисел: Т„(1'+ 1") =1'ь. Ее заключительное состояние — дш. Блоки реализуют следующие указания и вычисления: Р~ — вычислить с восстановлением предикат «оба слагаемых больше нуля»; !67 Т, — стереть все непустые символы справа; Т, — установить головку у ячейки, следующей (вправо) за маркером °; маркер заменить на Т,,„— см.
пример 5.4, б, в котором команду ц,Х вЂ” н),»т' надо заменить на команду д, -»-дЯ; Рис. Б.9 Т„„(а — 1) раз копирует 1"; после»'-го цикла она останавливается в конфигурации 1'-'-'( 1')'-' д1» ° 1»; Т» — вернуть головку к крайнему слева непустому символу. После (а — 1)-го цикла этим символом окажется '(или «, если а=1), и происходит выход из цикла и переход к Т« „. Т~+работает как Тээ (см. пример 5.7, а) с той разницей, что числа, которые она суммирует, разделены двумя видами маркеров: и °; для этой цели в нее к командам с маркером ° в левой части добавлены такие же команды для маркера —.
Аналогично тому, как нз машины Т+ была построена Тч..», можно из Тх построить машину Тхх, которая перемножает несколько чисел, и по схеме, аналогичной приведенной на рнс. 5.9, с использованием Тхх вместо Т+„построить машину, осуществляющую возведение в степень. Другой важный пример, который читатель может либо построить, либо найти в [44, 47), — перевод унарного представления чисел в позиционное †двоичн или десятичное. Универсальная машина Тьюринга.
Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного механизма, и как программу, т.е, со- 168 вокупность предписаний, однозначно приводящих к результату. При разборе примеров любой читатель невольно принимает вторую интерпретацию, выступая в роли механизма, который способен воспроизвести работу любой машины Тьюринга.
Уверенность в том, что все это будут делать одинаково (если не наделают ошибок, что, кстати, предполагается и при работе машины Тьюринга),— это по существу уверенность в существовании алгоритма воспроизведения работы машины Тьюринга по заданной программе, т.е. системе команд. Действительно, словесное описание такого алгоритма дать нетрудно. Его основное действие, циклически повторяющееся, состоит в следующем. «Для текущей конфигурации сс1а~д;а;а2 найти в системе команд команду с левой частью инар Если правая часть этой команды имеет внд д',а,'. Р, то заменить в текущей конфигурации инаг на а',.
~,' (получится конфигурация а~ага,'.д;.аз); если же правая часть имеет внд о',а'Ь, то заменить а~д;а~ на д', ага,'. (как видно из примера 5.3, случай с Е можно не рассматрйвать)». Как уже говорилось в $ 5А, словесное описание алгоритма может быть неточным и нуждается в формализации. Поскольку в качестве такой формализации понятия алгоритма сейчас обсуждается машина Тьюринга, то естественно поставить задачу построения машины Тьюринга, реализующей описанный алгоритм воспроизведения. Для машин Тьюринга, вычисляющих функции от одной переменной, формулировка этой задачи такова: построить машину Тьюринга (Г, вычисляющую функцию от двух переменных, и такую, что для любой машины Т с системой команд Хг И(Ег, а) =Т(и), если Т(а) определена (т.е.
если машина Т останавливается при исходных данных сс), и (/(Хг, а) не останавливается, если Т(а) не останавливается. Любую машину К обладающую указанным свойством, будем называть универсальной мишиной Тьюринга. Нетрудно обобщить эту формулировку на любое число переменных. Первая проблема, возникающая при построении универсальной машины У, связана с тем, что (У, как и любая другая машина Тьюринга, должна иметь фиксированный алфавит Аи и фиксированное множество состояний (~и. Поэтому систему команд Хг и исходные данные Произвольной машины Т нельзя просто переписать на ленту машины У (всегда найдется машина Т, алфавиты Аг и Яг кото- рой превосходят по мощности Ап, Яп или просто не совпадают с ними).
Выход заключается в том, чтобы символы из Аг и Яг кодировать словами в алфавите Ап. Пусть ~)Аг] =гп», ') с„»~ пт. Будем всегда считать, что а,=1, а =), (этн два символа всегда есть в алфавите любой ма'"т шины, работающей с числами). Обозначим коды г)» и а» через 5(п») и 5(а») и определим их'следующим образом: 5(Х) ), г, для любого другого а» 5(а;) =а), г 1',для "т заключительного состояния г)гз 5(г)»,) =г))» т, 5(Ч») = и г — г-1 =г)Х г 1', если (чьпг.
Код 5(аг) для данной машины Т всегда имеет длину (формат) тг, а код 5(»)») — форматпг. Символы Р, Ь, -ь введем в Аю т.е. 5()с) =)с, 5(Ь) =Е, 5(-+) =-»-, Код слова а, образованный кодами символов, составляющих это слово, обозначим 5(сс). Таким образом, окончательное уточнение постановки задачи об универсальной машине У сводится к тому, что для любой машины Т и слова сс в алфавите Аг 1»(5(Е»), 5(сс)) =Т(гз), План построения машины У таков.
Будем считать, что машина Т всегда работает на правой полуленте'. Тогда ленту 0 можно разделить на две бесконечные полуленты с границей 2 между ними: в правой полуленте записывается текущая конфигурация машины Т (в силу нашего предположения конфигурация машины Т при этой имитации никогда не зайдет на левую полуленту), а в левой полуленте записан код системы команд 5(Х»). В частности, начальная конфигурация У имеет внд и5(Б,)Х5(д~)5(а) (и» вЂ” начальное состояние машины У, д, — начальное состояние Т, сс — исходное слово Т). Например, начальной конфигурации машины из примера 5.2, а с исходным словом 11 соответствует следующее слово на ленте машины У: д1а1 г)1аЖг)177 ьг)1а)гсХг)1а)а1. Выполнению одной команды Т соответствует цикл машины 1»', реализующей основное действие, описанное ранее, с той разницей, что оно будет осуществляться не над конфигурацией К машины Т, а над ее кодом 5(К).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
