lekcii3 (Лекции), страница 3

Используя ны Х: символы машин С и —, мы можем составить следующую диаграмму маши- я К г ° вг ° и и ~~с 'к к,)к к с ~ ' г ~ '=. з г ' (ЛпЛпЛфЛИ'Лш(Л)Л >»* (ЛнЛпЛи:(Л) Л > . (черсз % обозначено слово над расширенным алфавитом машины Х (точнее, цепочка слов), представляющее промежуточные результаты вычисления ПОД), Диаграмма маши- ны Ж может иметь вид ° ° ° ° ! ° М ° ! ° ° ~ ° и~ Л е ~ ° $ е атее ~ ° ~йф ч----- Л ''.

В последней диаграмме использована машина Т~, построенная в п, 2.6.6. ! 1ерейдем к конструированию машин С и —. Прежде всего необходимо отметить, что эти машины могут конструироваться независимо одна от другой и в любой последовательности. Иными словами, исходная задача конструирования машины Х сведена, к двум независимым более простым задачам конструирования машин С и —. Сравнение двух натуральных чисел будем проводить, вычитая из каждого числа по единице и следя за тем, какое из них раныпе обратится в нуль. Этот способ в позиционных системах счисления не применяется,но придает нашей задаче простоту, свойственнунз действиям в натуральной Построенная диаграмма машины Х содержит символы элементарных МТ г, 1 и ф (помещает в рабочую ячейку знак уг), символы машин 1~„(см.

п. 2.2.3, а также 2.6.1) и символы машин —, С, Х, которые еще не сконструированы. Следовательно, задача, конструшрования машины Х сведена к задаче конструированная более простых машин Х,— и С. Машина Х пормирует вычисление, т.

е. убирает все промежуточные результаты и помещает окончательный результат вслед за аргументами: системе счисления. Для этого нам потребуется машина Т л, уменьшающая натуральное число в десятичной позиционной записи на единицу: [ЛИ'Ли(Л)Л >==~* [ЛИ'ЛиЛп(Л)Л >, где р(в) = р(и) — 1, и машина Т~а, вычислялощая значение предиката «натуральное число, записанное на леллте, отлично от пуля»: ТФ» [ЛИ'Ли(Л)Л >=~* [ЛИ "ЛиЛб(Л)Л >,. где 6 -- И [истина), если р(и) ф О, и д Л [ложь), если р(и) = О. Диаграмма машины С: Т~9 К Т Т, К ус ! 99 т л,=О /' кг, 2 2 49 4 Т9 4 '-',Л ° г ° й е В этой диаграмме исллользован символ машины Л, вычисляющей колгьюпкцию (Й).

Диаграмма, машины Л настолько проста, .что мы се составим сразу: Вычитание натуральных чисел при условии, что уменьшаемое больше вычитаемого, будем также производить с псгелощьк> машин Т л и Т4ш вычитая из уменьшаемого и вычитаемого по единице до тех пор, пока вычитаемое не обратится в пуль. Здесь 1эазпость двух натуральных чисел получается по определеншо натурального числа как превышение количества единиц в одном числе пад натуральным значением другого числа. Этот способ также выбран для простоты реализации. Таким образом, диаграмма машины [ — ) может иметь вид ° г ° а ° т ° К ~ ~~ ~ Т ° [.—,— — ° К Т К 2 И 3 2 3 ~0 ', 4 ~ 4 И 4 ,— +» К 1 И 2 ! 3 2 е Т ° $ е Т ° гл, ° [ е' 3 '.л., т.л. и ,.е Г е и К ° ! ', Я 6 ' — в.

к ° ~.!', 9 ° И е.- 4 'Ф Т ° ЛТ ° --- ' 4 И Чтобы закончить составление диаграммы машины Х, осталось сконструировать МТ 'Г л и '1~щ Диаграммы этих машин настолько просты. что их можно выписать сразу. !"ели считать, что слово, к которому применяется машина Т д. изображает число, отличное от нуля. то диаграгима ма«пины 'Г л может иметь вид О г е г к ! е 2 О 1 2 9' 8 °-- Диаграмма машины Т~„. О ° Г ° л» ° Г»Ке)е — — ле~е 2 ° Ие — —, е Г ° 'ге ! 1 ! Г еЛ вЂ” - — ' Последние две диаграммы содержат только символы элементарных МТ и ранее сконструированных МТ. Поэтому построение ма|пины Х, вычисляющей ВОД двух натуральных лисел, на этом заве1эшается.

Из примера 2.7.1 видно, что, применяя метод констручлроваиия МТ «сверху вниз», можно на каждом этапе рассматривать достаточно простые диаграммы. МТ, символы которых используются при составлении диаграмм более высокого уровня, определяются в процессе разработки этих диаграмм. Вводя эти символы, мы сводллм исходную задачу к нескольким незавллсимым задачам констру.ирования более простых МТ. Таким образом, технллка описания программ МТ с помощью диаграмм, нормирование вычислений и метод нисходящей разработки («сверху вниз») открывают возможность систематического конструирования достаточно сложных МТ; При этом теоремы о сочетаниях алгоритмов позволяют обосновать процесс конструирования с тем, чтобы по завершении конструирования МТ иметь уверенность в том, что разработанная МТ выполняет именно ту обработку сообщений, которая требовалась в задаче.

91 2.7.2 Определение схемы машины Тьюринга Процесс конструирования МТ «сверху вниз» состоит в последовательной разработке диаграмм все более и более простых МТ, причем каждая из последующих диаграмм описывает работу МТ, символ которой содержится по крайней мере в одной из ранее составленных диаграмм. Следовательно, каждая из диаграмм, составленных в процессе конструирования «сверху вниз», должна бь>ть такой, чтобы ее ъюжпо было зал>епить символом описываемой е>о МТ.

Этому требованию удовлетворяют не все диаграълмы, а только такие, которые оГГисывают МТ, имеющие одно начальное и то:Гько одно конечное состояние. Дело в том, что каждый символ элементарной МТ на диаграмме Тьн)ринга соответствует ка,кому-нибудь одному состоянию МТ, описываемой этой диаграммой: если же в диаграмме Тьн>ринга, встречается символ нсэлементарной МТ, то это означает, что на уровне указа.е!еГОй диаг1)аммы на"п>льно\> и кОнсчное сОстОяния указа»>ной неэ>Гек>ентец)нОЙ М 1 как бы «склеиваются» в одно.

В случае, если конечных состояний несколько, такая «склейка (или «отождествление») состояний становится невозможной. Отметим, что МТ с несколькими конечным>л состояниями сконструировать нетрудно. В п. 2Л.2 при доказательстве П теоремы Шеннона была построена, МТ, подсчитывающая количество палочек над алфавитом ~!), которая имеет 2г. 1 1 конечных состояний (здесь г — номер буквы алфавита МТ, которая моделируется над алфавитом (!1). Эта МТ входит в состав диаграммы, описывающей МТ, которая имеет только одно конечное состояние. МТ, подсчитывающая количество палочек, не может быть заменена одним символом в диаграмме, в состав которой она входит. Всякую МТ, которая имеет одно начальное и одно конечное состояние, будем называть собственной.

Выше было показано, что в состав диаграммы, описывающей собственную МТ; могут входить несобственные МТ. Если это не имеет места, т. е. если диаграмма, описывающая некую МТ, содержит только собственные МТ, то МТ, описываемая этой диаграммой, называется МТ со структурированным управлением, или структурной МТ. Легко видеть, что в процессе конструирования «сверху вниз» мы применяем только такие спо<:обы декомпозиции, при которых получаются имешю структурные МТ. Диаграммы структурных машин мы будем называть схемами. Таким образом, схема МТ это частный случай диаграммы Тьюринга. Определение 2.7.2.

Понятие схемы машины '1ьк>ринга определим следующим образом, отражающим нисходящий процесс конструирования: 1. символ ° составляет схему; 2. если б», Ьэ,..., .»„Схемы, то их последовательная ко)пюзиция .)Г Ь2... О„является схемой: 3. если СГ, Сэ,..., С„схемы МТ, вычисляющих предикаты РГ, Р2,..., Р„соответственно, и»Г, .5»,..., К, схемы, то и конструкции ' Л ! / И ~ с и с ° ~ 'Л являются схемами; 4.

символы элементарных магнии Тьюринга, составляют схемы; 5. никакие другие объекты схемами не являются. Все диаграммы, построенные в примере 2.7.1, являются схемами. 2.7.3 Эквивалентность схем и диаграмм Из определения 2.7.2 следует, что всякая схема МТ является диаграммой Тьюринга,, но не всякая диаграмма является схемой. Так, диаграммы, составленные при доказательстве 1 теоремы Шеннона,не являются схемами.

11оскольку при конструировании МТ «сверху вниз» получаются обязательно схемы, возникает вопрос; для лк>бого ли алгоритма существует МТ, которую можно сконструировать нисходящим образом? Ответ на этот вопрос дает следуюгцая теорема. Теорема 2.7.3. (Бойма-Якопини-Миллса) Для любой машины Тьюринга Т можно эффективно построить машину Тьюринга б, которая является структурной (т.

е. диаграмма которой является схемой) и которая моделирует машину Т. Доказательство этой теоремы состоит в преобразовании каждой части диаграммы машины Т в одну из трех структур, приведенных в определении 2.7.2. Каждое такое преобразование (мы будем называть его структурируннцим преобразованием) уменьшает неструктурную часть диаграммы. После достаточного количества структурирующих преобразований неструктурная часть диаграммы исчезает. Возможность проведения структурирующих преобразований вытекает из первой теоремы Шеннона, так как каждое такое преобразование сводится к уменьшению числа состояний моделируемой МТ. При этом, естественно, рабочий алфавит моделируемой МТ расширяется (в него вводятся дополнительные буквы).

Полного доказательства теоремы 2.7.3 мы приводить не будем из-за его громоздкости. Теорема 2.7.3 была сформулирована Боймом и Якопини в 1966 г., однако, как было впоследствии установлено сотрудником фирмы 1ВМ Миллсом, их доказательство было неполным. Полное доказательство было опубликовано Миллсом в 1972 году [42, 38]. 11иже следует полученное Д. В. Рисенбергом чисто тьюринговское, диаграммное дока; зательство теоремы, основанное на идеях Клода Шеннона о сокращении числа состояний произвольной машины Тьюринга за счет увеличения числа букв рабочего алфавита. 2.7.3.1 Доказательство Пусть машина Т имеет алфавит А = 1а„..., а„) и набор состояний Я~ = (цо,..., с!»'!.

Тогда алфавит машины Т' будет содержать помимо алфавита А еще (р + 1)(в + 1) знаков 6, Каждой команде из программы монтаны Т', нс являющейся терминальной (ф, аз,,1, ф), поставим в соответствие нс которую структурную машину В; по следующему правилу: 1. Если команда, машины Т имеет вид (д,, а, аы д~), то ей соответствует машина перезаписи буквы В,, !ьы 2.

Если команда машины Т имеет вид (с7ь а, о, ур), г Е 11, г), то ей соответствует машина дви жения ао !во !ол 3. Если команда машины Т имеет вид (д,, а, в, щ) (/ ф !)., то ей соответствует стоп- машина В,, -6~, Таким образом, каждый знак 6, соответствует определяющей паре (съ, а, ) исходной машины Т и неявно содержит в себе информацию о номере состояния, в котором она находится. Таким образом, сгенерирована матрица инциденций Вео отражающая наличие связей всех состояний (точкоълест) в диаграмме. Теперь можно построить диаграмму машины Т: Здесь введена сплошная (от 1 до са) нумерация лля пар (г,у) таких, что пара (д;, а, ) определяет некоторую команду машины Т, не являющуюся терминальной. Аналогично была, введена сплошная (от 1 до ьп) нумерапия для пар (с, у)., лля которых пара (ц;, а ) определяет терминальную команду мапсины Т. Сам порядок, в котором перенумсрованы пары, не важен.

Исходя из построенной диаграммы, можно заметить, что машина Т' является структурной, т. к. структурныъси являя>тся все машины Вс . Осталось показать, что маслина Т' моделирует машину Т. Конфигурации [Лай ... асъ ... ак,Л) сй машины Т поставим в соответствие конфигурацию [Лай... бать ...