lekcii5 (Лекции), страница 12

Будем говорить, что конфигурация С' следует за, конфигурацией С, если найдется о конфигураций Сш С),..., С„. 1 (н = 1,2,... ), .таких, что С = С).,. С„.) — — С', и С,', =~ С', 1, г = 0,1...., н — 2. Если конфигурация С' следует за конфигурацией С, будем писать С ~ С'. Отношение следования тож1 переносится на ситуации 5' =*~ У. Здесь звездочка традиционно обозначает рефлексивно-транзитивное замыкание отношения следования, включающее с:)учаи непосредственного следования (один такт) и пустого следования, возможного только при отказе МТ на неприменимых исходных кш)фигурациях, когда пи одного такта пе было выполнено. Ситуацию (конфигурацию), соответствующую начальному состоянию МТ, будем называть начальной ситуацией (конфигурацией). Пример 2.2.4. Опишем машину Тьюринга К, которая копирует на ленте слово над однобуквенным алфавитом А = (!), т. е...

исходя из ситуации бс — — [>вЛьа)(Л)Л), где са некоторое (не интересующее нас) сообщение, которое может быть записано на ленте до копируемого слова ш, и = !...! (и палочек), заканчивает работу в ситуации О, = 1д)ЛН)ЛН)(Л)Л) (при этом слово п, оказывается скопированным на ленте). Пусть для определенности п = б), т. е., ьа = !/!!/, тогда работу машины К можно описать с ПОм01цьк) следук)Н1сй ПОсл).'дОВат1'льнОсти ситуаций: Программа может быть записана в виде слелукнцей таблицы; Состояние Буква начало работы поиск начала исходного слова поиск начала исходного поиск начала исходного слова начало исходного слова найдено слова копированис очередной буквы начало исходного слова найдсно пометка копируемой бук- вы копирование сочередной буквы слово скопировано перенос буквы в копию ис- ходного слова пометка копируемой бук- вы перенос бу квы в колино ис- ходного слова, г поиск конца исходного слова поиск конца исходного слова г поиск конца исходного конец исходного слова найден слова поиск последней скопиро- ванной буквы конец исходного слова найден г поиск последней скопированной буквы поиск последней скопиро- ванной буквы последняя скопированная буква найдена очередная буква скопиро- вана последняя скопированная буква найдена очередная буква скопиро- вана поиск начала копии слова начало копии слова найде- поиск начала копии слова поиск начала копии слова но начало копии слова, найде- поиск пометки в исходном слове пометка найдена но поиск псгметки в исходном поиск пометки в исходном слове слове пометка.

найдена копирование следующей буквы копирование следующей буквы г копирование очередной буквы г установка головки Л конец работы слово скопировано установка головки г установка головки конец работы в конец работы конс'ц работы 4б [;лц~ц[л)л > [=,ллцц(л)л > [;,Л[~)ЦЦЛ[Л > [=.,Л~л~ цл[[л) л > [;ЛЦ([) ЦЛЦЛ > =~ [~о(Л)ЦЦ[ЛЛ > => [=оЛЛ[Ц[Л(Л)Л > => [~оЛ)(!)Ц[Л[Л > — ~ [иоЛ~Л!~[Л[[[)Л > => [соЛ~ИЛ)[!ЛЦЛ > ~ [ оЛ([)[Ц[ЛЛ > =~ [- ЛЛЦЦ(Л)[Л > =~ [- ЛИЛ)Ц[Л[Л > 4 [:,л~<л)ц[лцл > =* [=.,ЛЦ[ЦЛЦ[Ц[Л)Л > =~ [:оЛ(Л)~~ЦЛЛ > А [ Л(Л)ЦЦЛ~Л > ь [..Л~Л[Ц[Л)~Л> =~ =~ [иоЛН~)~ЦЛЦЛ > => Конечно, состояния можно было бы перенумсроватгь и тогда программа имела бы более компак!'ный, но менее поня'!ный Вид: Из примера (2.2.'!) видно, что даже простые действия выполняются на машинах Тьюринга достаточно сложными программами.

Кроме того, запись программ МТ в виде таблиц плохо обозрима и потому неудобна для понимания. Поэтому мы перейдем к другой фо1эме записи. Лекция 7 2.2.3 Диаграммы Тьюринга Диаграммы Тьюринга представляют одни МТ через другие, более простые МТ иным, визуально-топологическим способом, причем, как будет показано далее, этот способ не менее строг и гюлон, нежели "обычные" МТ. Так, машина, копирующая на лепте залисанное на ней слово, рассмотренная в примере (2.2.4), может быть представлена !срез МТ, которые ищут начало слова на ленте, конец слова на ленте, копируют одну из букв слова и т. д.

(ик!сна состояний под!!б!1л!н!~! в этом примере так, чтобы легко бь!ло бы выдели!ь более простые М'1'). Эти более простые МТ в свох! очередь могут бьггь представлены через еще более простые МТ (это тоже нетрудно проиллкэстрировать на примере (2.2А)) и т. д. Такой нисходящий процесс представления МТ через более простые МТ должен обязательно оборваться, так как рано или поздно мы сведем описание каждой из расс матривасмых МТ к элементарным действиям, введенным при определении МТ. При этом рассматриваемая МТ будет описана через элементарные МТ, т. е. такие, .которые уже нельзя описать через более простые МТ, так как каждая из них выполняет всего одно элементарное действие и останавливается. Элементарные МТ над алфавитом А„= (я!, аа, ..., ар) определяются следующими программами.

1. Элементарная МТ 1 (сдвиг головки на одну ячейку влево) (~в, Л,г, ~!) ( 1„ Л„, ~!) Йо;и! 1 !1!) (Ч! и! э, Ч!) Если применить ЫТ 1 к крайней левой ячейке ленты, то результат будет таким, как если бы было применено элементарное действие 1: действие Ы'1' не определено ввиду перехода через край ленты. 2. Элементарная МТ г (сдвиг головки па одну ячейку вправо) ИО; Л, г Ч1 ) (Ф, Л, 3; Ф ) (да, ам г, ш ) (д~, ам з, д~) (да, а„, г, ц~) (сХ~, а,„, а, гХ~) 3. Элементарные МТ Л, ад,..., ар (запись соответствующего знака на ленту). Ыы приведем программу машины а; (г', = О, 1,..., р; ав = Л): (цд, .Л,под~) (сй, Л, э,п~) ((Хо а~, .аь Х~) (дп ад,. Я, .гХд) (Дшпя~по~Х~)(~й" пр~гпЯ1) Комбинируя элементарные МТ, можно получать более сложные МТ.

11апример, применяя последовательно элементарную МТ 1 (или т) до тех пор, пока в рабочей ячейке не встретится знак Л, получим МТ, сдвигающую головку до левого (правого) конца слова, т. е., выполняющую действие (гэЛгп(Л)Л >=;. (га(Л)шЛ) (соответственно (гс(Л)шЛ) => (=сЛгп(Л)Л)). Построенные ЫТ мы будем обозначать буквами Ь (соответственно В). При конструировании новых ЫТ можно наряду с элементарными МТ использовать и машитты Ьи1т,: Диаг~>амма Тьк>1>инга, будучи ориентированным на 'и ловека вариантом алгоритми ~еской модели Тьюринга, рисуется на чистом листе бумаги слева-направо и сверху вниз. При использовании систем-диаграммеров, этот принцип сохраняется, потому что читать диаграмму (в несемитских и неиероглифических письменностях) принято также слева- направо и сверху-вниз. Состояния будем обозначать на диаграммах точками (е).

Позиционнотопологическая различимость мест для точек (точкомест) заменяет в диаграммах уникальные имена состояний. Каждому символу МТ соответствует два состояния -- начальное и заключительное. Поэтому каждый символ МТ должен быть изображен на диаграмме между двумя точками (например, В или Х и т. д.). Если после действия, определяемого машиной ЛХ~ должно быть выполнено действие, определяемое машиной ЛХ~, то правая точка (заключительное состояние) машины ЛХ~ соединяется стрелкой с левой точкой (начальным состоянием) машины ЛХ~, причем над стрелкой надписываются те знаки рабочего алфавита А„, которые вместе с заключительным состоянием машины ЛХ, определяют переход к действию, которое задается машиной ЛХэ.

аи ~ ..; п~д Л, Ю, Зимечангяе. В силу относительной адресации М'Г они чрезвычайно чувствительны к начальной ситуации на ленте и при неточном позиционировании будут работать неправильно или пс будут работать вообгцс. Но сеть исклсочения. Машины В и Х проевжа|от не только полное слово от границы до границы, но также и остаток слова и пустое слово. Зииечание. 11ашс определение диаграммы путем се нисходящей декомпозиции на более простые машины нс коснулось случая, когда среди таких машин снова появилась бы сама декомпозируемая машина, точнее, ее символ.

Хотя рекурсия принципиально не свойственна низкоуровневным операционным алгоритмическим моделям, диаграммы, будучи процедурным программированием. вполне могут быть рекурсивными. Более того, функциональные алгоритмические модели (Л-исчисление, НАМ) существенно рекурсивны. Однако рекурсивное определение диаграммы Тьюринга нс может быть статически расписано до элементарных машин и должно быть возложено на среду выполнения диаграмм, которая динамически конструирует необходимый диаграммный код в процессе интерпретации. Если она рекурсивна, то такие диаграммы Тьюринга допустимы. Например> в натурализованном алгоритме десятичного сложения синхронно работающие машины декремента второго операнда и инкремента первого, решающие задачу, могут быть описаны рекурсивно: в случае возникновения займа (переноса), необходимо применить ту же самую машину декремента (инкремента) к следующему разряду.

Именно так реализовано десятичное сложение в диаграммере Д. В. Дзюбы Л)Т2. 2.2.4 Понятие моделирования Определение 2.2.5. Рассмотрим две МТ Т = (А, О, Р, да) и '.Г = (А'., Я', Р', ф. Будем говорить, что машина Т' моделирует машину Т, и обозначать зто Т' Т, если выполняются следующие условия: 1. Указан спосоо кодирования знаков (букв) алфавита А знаками (буквами или словами) алфавита А' С: А — ~ А', 2. Каждому состоянию д Е Я машины Т поставлено в соответствие некоторое состояние ц' Е с1' машины Т', т. е.

определено отображение Я вЂ” ~ Я~'. Условия (1) и 12) возволяюзп для каззсдой конфигурации С машины Т составить конфигурацию С' машины '1', являюи1узося образом конфигурации С, заменяя каззсдую букву на ленте машиньз Т се кодом, а состояние ц -- соппоянисм д', 3. Если Г'о начальная конфигурация машины 'Е', то се образ Сс — начальная конфигурация машины Т', 4. Если машина, Т из начальной конфигурации Сс после конечного числа тактов (переходов от одной конфигурации к другой) останавливается в конфигурации Сь, то маьпина Т' из начальной конфигурации С", являющейся образом Сш после конечного числа тактов также останавливается в конфигурации С~., являклцсйся образом Сь, 5.