С.В. Яблонский - Введение в дискретную математику (1060464), страница 20
Текст из файла (страница 20)
В клетках Ч таблицы Т„для которых р(ц)=1, в таблице Т стоит также пустая команда. Легко видеть, что маптинз И в определенном смысле является итерацией машины И„ т. е. ее работа эквивалентна многократной работе машины И,. в 2. Один метод построения машин Тьюринга Здесь будет описан способ построения машки Тьюринга, который использует композиции машин и специальный операторный язык для записи алгоритмов. Этот язык впервые был предложен А. А. Ляпуновым в 1953 г. (см, !211). Поскольку сам язык носит вспомогательный характер, то не имеет смысла давать его строгое формально-логическое определение.
й!ы остановимся лишь на кратком описании операторного языка и рассмотрим серию примеров. 1. Исходными объектапп являются операторы, которые подразделяются на три группы: а) операторы, осуществляющие преобразовакие записи ленты, состояний маппппз н перемещение головки машины. Эти операторы обознача|отся заглавными латинскими буквами Л, В, ... (ипогда снабженными индексами); 1ЗЕ Ч Ь ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ б) операторы проверки логических условий, обозначаемые символами р) или Р1 и иногда снабженные индек- 1 сами; в) специальные операторы, обозначаемые символами «п о.
2. Из операторов по определенным правилам строятся операторные схемы. Операторная схема представляет собой некоторую последовательность операторов, в которой для всех стрелок в операторах проверки логических условий указаны операторы, к которым зти стрелки ведут. Например, выражение ) 1 »АэРАР будет операторной схемой. 3. Каждой операторной схеме сопоставляется некоторый алгоритм, характеризующий преобрааование записи ленты, состояний машины и перемещение головки машины. Последние осуществляются при помощи следующих правил. а) Операторы в схеме «работают» в определенной последовательности. В данный момент начинает работать тот оператор, перед которым стоит символ».
б) Пусть мы имеем «А. Тогда запись на ленте, состояние машины и положение головки на ленте, имеющиеся к данному моменту, преобразуются оператором А в некоторую запись на ленте, некоторое состояние машины и некоторое положение головки. После этого фрагмент схемы»А перейдет в фрагмент А«, что означает, что преобразуется также и операторная схема. в) Пусть мы имеем «р) (или»Р1(. В этом случае 1Т происходит вычисление предиката р по имеющейся записи на ленте и состоянию машины. В случае, если р 1, то фрагмент «р) преобразуется в р)», т.
е. Мы перейдем к выполнению следующего оператора; если Р = О, то фрагмент»Р) преобразуется в Р), т. е. выполняется далее оператор, к которому ведет стрелка. Для «Р1 — аналогичное правило, здесь р — трехзнач- 1 ный предйкат, и в зависимости от его значения по соглашению происходит одна из трансформаций » 1 1 1 1 Р1 =«Р1 " »Р1 ~ Р1 Р1 =«Р1 гл. о.
вычпслпмыи эвикции тгв г) Сочетание «в обозначает конец преобразований или окончание работы. П р и и е р 3. Рассмотрим операторную схему ! о «.4орАъоь Пусть операторы А, и А, обозначают преобразования записи ленты, состояний и положения головки, осуществляемые соответственно машинами й, и й,. Предположим, что состояния машин йо и й, не пересекаются. Пусть, наконец, р=р(х) — предпкат, определенный на номерах ячеек (т. е. совокупности пар (а, х)), на которых машина й, останавливается.
Тогда операторная схема осуществляет следующее преобразование. 1. Имеем «А,. Работает машина йо до останова (еслп он происходит) в ячейке с номером, скажем, тв Схема перейдет в ! 4о РАооо. 2. Имеем «р. Вычисляется преднкат р и: а) если р 1, то получаем схему ! А«Р «Аооо! б) если р = О, то получаем схему А рА»еь 3. а) Имеем «А,, Работает машина й,. В случае оста- нова машины й„приходим к схеме Го АорАо «оо. б) Имеем «оо.
Преобразование закончено. Преобразование, осуществляемое данной операторной схемой, является преобразованием, осуществляемым последовательным подключением машины й, к й„относительно предиката р(х). Пример 4. Легко видеть, что операторная схема ! «Аорю 424 ч. ь ФункциОнАльные системы с ОпеРАциями может интерпретироваться как схема, задающая преобразование, которое получается прн итерации машины относительно предиката р. Теперь перейдем к описанию технологии программирования для машин Тьюринга, т. е. к описанию метода построения программы машины Тьюринга, осуществляющей заданное преобразование. Этот метод параллельно будет иллюстрироваться одним примером.
Весь процесс программирования разбивается на четыре этапа. о ноаопьньй нонною ьонпюаоюепьнюо нонною Рнс. 5 1 этап. Пусть задано некоторое преобразование записи на ленте и положения головки. Допустим, что существует машина Тьюринга, осуществляющая это преобразование. Сначала из неформальных соображений составляют план осуществления данного преобразования. При этом стараются данное преобразование расчленить на более «простые преобразованияь, т. е.
такие, для которых либо мы уже ранее построили машину Тьюринга, либо ее легко можно построить. Пример 5. Пусть ьо=2. Предположим, что требуется построить машину Тьюринга, которая осуществляет сдвиг массива из а+1 единиц (а=О, 1, ...) влево на к+1 ячеек (э=1, 2, ...) (вне массива лента пустая). Величину сдвига э+1 можно задать путем специальной установки головки в начальный момент, На рис. 5 изображены ааписи на ленте и положение головки в начальный и в заключительный моменты. Требуемое преобразование можно осуществить так; 1) Отмечаем начальную ячейку путем замены в ней символа О на символ 1. Оператор для этого преобразования обозначимчерез Ф(О -ь.1~) В скобках показано, что символ О заменяется на 1 и головка остается на месте.
2) Движемся вправо (оператор о(,) до левой единицы масспва. ГЛ. О. ВЫЧИСЛИМЫЕ ФУНКЦИИ 125 3) Обозначпм через а' н ао соответственно символ, обозреваемый в данный момент, и символ, расположенный непосредственно справа от а'. Здесь а' 1. Выясняем, является ли единица, т. е. а', последней единицей в массиве. Для этого вычисляем предикат р(а', ао), где (О при я" =О, (1 при а"=1, В случае р = 1 4) Стираем а' (оператор 0(а'))'. 5) Возвращаемся влево до ближайшей единицы (оператор А,).
6) Приписываем справа от этой единицы еще одну единицу. Обоаначим через Ф(1~-»-11 ) соответствующее преобразование. 7) Возвращаемся (оператор р„ р, — предикат, равный тождественно нулоо) к А,. В случае р 0 8) Массив состоит из одной единицы. Производим 0 (а') — стирание единицы. 9) Возвращаемся влево (оператор А,) до ближайшей единицы. 10) Движемся влево (оператор Ц через массив из единиц и останавливаемся над левой единицей. П этап. Переход от составленного плана преобразования к операторной схеме. Продолжение промера 5.
В нашем случае операторная схема имеет вид оФ(0~-»1') ~А р(аао)30(а) А Ф(1' 11») Ро~ »0(а)А»Лоз. Замечание. При составлении операторной схемы важно, чтобы заключительное положение головки после выполнения очередного оператора совпадало с начальным положением следующего оператора. Иногда для этого приходится вводить дополнительные согласующие операторы. В нашем примере согласование получается естественным образом, кроме оператора р(а'а"), для которого мы считаем, что после его выполнения головка встает над а .
П1 зтап. Переход от операторпой схемы к программе машины. Сначала составляют программы для каждого из операторов данной операторной схемы (кроме операторов ~» Ро» ю) щ ч. 1. Функциональные системы с опеглгп1ями Продолжение примера 5. Мы имеем следующие программы для операторов, входящих в схему (если операторы встречаются в схеме несколько раз, то программу составляем для одного нз них; см. табл. 6).
Твбллцв 6 в(а'в-> А, х, х, х, х, ОЬх 1ьхв Ояхв 1ях, 1дхв х, Оях 1сх Обхв При написании программ для операторов состояния выбираем так, чтобы множества состояний для разных операторов не пересекались. Далее, операторную схему можно рассматривать как схему, определяющую композицию программ (машин). Для этого сначала «оборвев~» все стрелки (кроме стрелок типа').
Будем считать, что каждый конец стрелки ведет к своему состоянию останова. В примере 5 получим следующую схему: ° Ф(01- 11)А,р(а'а")'0(а')АвФ(1'- 11')рмО(а')А,.Еы. Затем, беря фрагмент этой схемы А,р(а'а )'0(а')АвФ(11- 11')', строим программу, являющуюся последовательным подключением соответствующих программ. После этого переходим к фрагменту З А,р(а'а")~0 (а') АсФ (11-в-11') р, ) и строим программу, применяя операцию итерации к предыдущей программе относительно преднката р,. Далее, берем фрагмент в Ф (О"-~1 ) в А, р (а'а") 10 (а') АвФ (1' -в.
11в ) рв Гл. а Вычислимые Функции $27 и по нему строим программу, беря последовательное подключение предыдущей программы к программе для Ф(0'- 1'). И, наконец, вся схема ° Ф (О -«-1~)) А(р(аа") 0(а ) АаФ(1~-а-11~) ро)0(а) Аорто) приводит к программе, являющейся последовательным подключением по.троенпой программы и программ для Таблица 7 о(а') е(о)-(» р(а'а") 0(а'), А, и Т. Окончательный вид атой программы дан в табл. 7. 3 а и е ч а н и е. При последовательном подключении программ, соответствующих двум соседним операторам В' и В" операторной схемы, образующим фрагмент В'В", предикат р полагается равным тождественно 1, если оператор В' является оператором, преобразующим запись ленты, состояния машины и положения головки.
Если В' есть оператор проверки логического условия, то выбор преднката р согласуется с этим логическнм условием. 1Ч этап. Упрощение программы. Построенные данным методом программы иногда допускают значительное упрощение по числу состояний. Здесь мы сформулируем некоторые принципы упрощений. Допустим, что программа имеет два состояния к' и ма таких, что соответствующие им столбцы имеют пустые 123 ч. ь ФУпкционлльные систкмы с опеглцнямн Таблица 9 ;х„ Ха Х4 х, Х44 х,„ Х,4 х„ Олх4 онкую О 1вх4 1ях Обх4 Олх4 04,х4 1бх4 1лх44 !ях44 Одхз ОЬх44 1их4 1йх4 044х44 ЫХ44 Обх,4 15х44 того жв столбца.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
