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

Если из начальной конфигурации Сс машина Т пробегает (конечную или бесконечную) последовательность конфигураций Сш Сд,..., Сы..., то каждая последовательность конфигураций, пробегаемая машиной Т' из начальной конфигурации Со (образа конфигурации Сс), содержит в ка, зесгве подпоследовательности последовательность конфигураций Сс, С~,..., С~...., где 1'с (ю, '= О, 1,..., 15...) - образы конфигураций С, машины Т. 50 Из определения 2.'2.5 <следует, что если машина Т' моделирует машину Т, то она описывает тот жс самый алгоритм, что и Т, но, возможно, проходит при выли>лнении алгоритма большее число промежуточных конфигураций.

Таким образом, понятие моделирования вводит бинарное отношение алгоритмического равенства между машинами Тьюринга. Другие операции отношения над алгоритмами будут вв<'дены поздне<-', по ъп ре изложения Тьн>ринговской теории алгоритмов. Следует заметить, что равенство алгоритмов даже в таком простом случае машин Тьюринга требует более сложного определения, чем равенство строк или чисел. 2.2.5 Эквивалентность диаграмм и программ МТ Теорема 2.2.6. Каждой программе Р, задающей МТ 7 = (А, Я, Р, г!о), можно зффективньс.лл образом соссоепс<св<сть диаграмму !7, образованнук> символами элементарных МТ, так, чтобы МТ, .определяемая этой диаграммой, моделировала бьс машину Т.

г>Наьс нужно указать способ (алгоритхс) эффективного построения лиаграммы по программе Р, а потом убедиться, что для исходной МТ и МТ, определяемой диаграммой 77, выполняются все пять условий определения 2.2.5. 2.2.6.1. Рфоспсроение диограммьс О. Каждой строке (<1, а, и, с!') Е Р поставим в соответствие на диаграмме символы о . Для и = з нич<>го ставить не надо, ведь пустые д<йствия на диаграмме не отображаются. В этом случае окончанием работы машины, определяемой диаграммой, будет правая точка предыдущего элемента диаграммы.

Зо.клечание. Если бы наши программы были бы в пятерках, непосредственной трансляции команды в элемент диаграммы здесь бы не получилось. Вот еще одна причина использования четверок! Поставим еше одну точку ( ° ), соответствующую начальному состоянию диаграммы, и соединим ее стрелкалси — с левыми точками всех символов и, соответствующих строкам вида (<7ш аз, и,<!) б Р. Для каждой пары строк (<1, о», и, <!') б Р и (с!', а . <', с!л) б Р соединим стрелкой — правую точку символа и, соответствующего строке (с1, аь, г<, <!') Е Р, с левой точкой символа о', соответствующего строке (<!', и, о', <!ь) Е Р и надпишем над стрелкой букву а, . В полученной таким ооразом диаграмме произведем необходимые упрощения, описагшые в конце и.

2.2.3. Диаграмма 77 построена. 2.2.6.2. Доказательство того, ч>по ма<щи>со, Тп, опредаллелсал дипгралсмой 77, моделируе>п ма«лс><1! Т. Для этого достаточно показать, что выполнены условия (1) — (5) определения 2.2.5. Условие (1) выполняется потому, что алфавиты машин Т и 7р совгсадают. Состояниям машины Тп соответствуют точки на диаграмме 1Э. По сюстроению диаграммы каждому состоянию <7 машины '! соответствует одна или две точки на диаграмме О.

В последнем случае сопоставим состоянию о правую точку соответствукнцего символа на диаграмме. Таким образом, условие (2) выполнено. Условия (3) — (5) выполнены, так как диаграмма !7 определяет ту же последовательность элементарных действий, что и программа Р, за исключением того., что у маслины То могут оказаться лишние «пустые» действия, соответствующие переходам от левых точек символов и к правым. П За слечание. 1!роцедура построения диаграммы МТ по ес программе (последовательности четверок) является алгоритмом и, следовательно, может быть автоматизирована. В соответствии с этим алгоритмом может быть постро<'н транслятор программ Тьюринга в диаграммы, причем основная сложность такой трансляции заклк>чается в ген<рации 51 диаграммы, представление в ЭВМ которой одновременно должно бьггь удобным и вся визуализации, и для обработки, и, конечно же, для выполнения.

В современных системах автоматизации программирования с'САВЕ) диаграъсълы являются одним из самых распространенных способов представления алгоритмов, автоматически преобразуемых в программы (иногда наоборот!). Как было сказано выше, иъъенно диаграммный способ построения является наиболее удобным для нисходящей разработки алгоритма. Пример 2.2.7. Рассмотрим диаграмму, полученную в результате применения теоремы к программе 2,Н После преобразований эта, диаграмма примет вид; Теорема 2.2.8. Каждой диаграмме Тьюринга 0 может быть оффектасгнъъм, образам соиоспшсълена программа Р так, что МТ, описываемая этой программой, моделирует МТ, описываему1о диаграммой О. Г Доказательство снова состоит из двух этапов.

2.2.8.1. Построение программъс Р. Заюеники на диаграмме 1Э все символы незлементарных МТ их диаграммами, продолжая такую замену до тех пор, пока на диаграмме не останутся только обозначения элементарных МТ. В полученной диаграмме перенумеруем одинаковые символы элементарных МТ, .снабдив их числовыми индексами. Перенумеруем также все точки, соответствующие въссооднъсм состояниям. Каждому символу элеъъентарной МТ сопоставим программу этой машины из п. 2.2.3, пометив каждое состояние этой программы дополнительными индексами у и н, где в совпадает с названием соответствующей элементарной МТ, а 7 номер, присвоенный этой элементарной МТ. Например, элементарной машине г ()-е вхождение элементарной МТ г в диаграмме) будет сопоставлена программа, (Чо от г, % ) (% ссг~ э) % ) Точке с индсксом ~ сопоставим программу вида (д,, Л, а,%) (д„ам э, д,) (Ц, аъеэ,%) Соединим все программы, сопоставленные символаъь элементарных МТ и точкам, в одну и произведем в полученной программе следующие изменения: еесли на, диаграмме символы элементарных МТ и; и нъ соединены стрелкой — ~, то стРокУ (У,'~, а, к, о о) заменим на (%'~, а, а, осъ '), т.

е. останов машины и заменим на перезапись буквы рабочей ячейки с последующим гсереходом прямо в начальное состоЯпие машины въ, минУЯ конечное состоЯние машины гб ° если на диаграмме меж„чу символами элсмонтарных МТ н и пъ стоит точка, то про- 52 Ведем Вьпшуказанн1ю замену для Всех сгрок Вида. (ф, и.. В, и,), гем Самым и!>сдотВ~ьащается ОстанОВка машины на прОмсжутОчных э'Ганах, изОбра.жаемых тОчками «пустыми» машинами: ° введем новое начальное состояние дс для генерируемой программы (оно соответствует крайней левой точке диаграммы) и добавим к программе пустые командные строки ЙВ Л~ Л; Ча) (Ф): Ви по Чс) ($ = ! 2, ° ° р р), где п~ симВОлы элеьюнтарных М !, непосредственно следунлцих за, крайней левой точкой диаграммы.

Эти строки являются модифицированной программой элементарной машины « ° ', в которой остановка заменена перезаписью буквы в рабочей ячейке, .т. е. реализуют холостой ход конструируемой программы: ° перенумеруем все состояния программы, за исклк>чением нового дс произвольным образом, введя сплошную нумерацию состояний (например, в лексикографическом возрастании индексов: !1,'~ — » дь. Постройте сами такое отображение индексов по схеме (1, г, в, Л, а;) х Г!2 — » !"!). На этом построение программы Р завершается.

2.2.8.2. Проверка уславпй (1) (5) определения 2.2.5 Условие 11) выполняется, так как рабочие алфавиты рассматриваемых МТ совпадают. Условие (2) выполняется по построенин) программы Р. Условия (3)--(5) выполняются потому, что обе МТ выполняют над сообщением, записанным на, ленте !Но построению программы Р) одни и те же элементарные действия в одной и той же последовательности !дополнительные элементарные действия имеют вид (ц, а, и, д ), т. е. не меняют ситуации на ленте).

П В заключение теоремы можно сказать, что трансляция любой высокоуровневой визуальной диаграммы в низкоуровневый маши1шый код описана нами достаточно конструктивным алгоритмическим образом. Здесь, как и раньше, основные трудности реализации заключаются в эффективном представлении диаграмм в памяти ЭВМ. Такого рода трансляторы диаграмм в программный код имеются в САЯЕ-системах автоматизации программирования, т. н.