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

аг„Л) машины Т', где состояние д* может быть любым. Тогда начальной конфигурацией машины Т' будет [Лай... б„,„„з, ч ... ар„Л),. Я соответствующая начальной конфигурации машины Т (здесь ц начальное состсьчнис Т'). Рассмотрим выполнение нетсрминальной команды (сб, а . в, сб)., где и Е АЫ(Л)0(/, т, «), а 7 т- 1. Если в Е А О (Л), то ма|пина Т' просто заменяет в своей рабочей ячейке знак 6; ~ на, 6~ в. Если и Е (1, г), то машина маипина Т' сначала считает из ячейки букву 6;, восстановит в ней букву а, сдвигается в направлении в и в новой рабочей ячейке записывает букву 6~ с, если до этого в ней была записана буква а г.

Е:ели и = л, то машина '1" заменяет в рабочей ячейке букву 6, на 6~ . Наконец, если команда, (д, а, г, д~) является терминальной (1 = г, и = а), то машина Т' сразу же выходит из цикла и завершает работу. Таким образом, теорема Нойма-Якопипи-Миллса доказана. Зимечание. Данное доказательство неконструктивно, но весьма миниатюрно и изящно как будто бы его делал не программист, а математик. Харлан Миллс, популяризируя результаты Бойма и Якопини для программистов-практиков из 1ВМ, дал конструктивное доказательство теоремы на базе блок-схем программ. Из теоремы Бойма-Якопини-Миллса вытекает важное Следствие. Всякая диаграмма может быть преобразована к виду, не использующему произвольные передачи управления -- стрелки, соединяющие элементы диаграммы неструктурированными способами.

В практике программирования это означает, всякая программа может быть преобразована в эквивалентную, не содержащую ни меток, ни операторов безусловного перехода ноСо. Программирование без по1о вместе с нисходящей разработкой было одним из элементов технологии структурного программирования— одной из первых технологий (после процедурного и модульного программирования).

Пример 2.7.4. Рассмотрим пример структурированного преобразования диаграммы Тьюринга. Машина Тьюринга, просматривающая слово гв б Я* и печатающая в качестве результата своей работы букву с1, если слово и: содержит четное число палочек, и букву Н, если а, содержит нечетное число палочек, описывается следующей неструктурированной диаграммой: ° 1 ° Г -------е Г -- -- ----в Г е Н а Г е Г ° х ° Г ° Эта диаграмма может быть заменена следующей схемой: е1 ° Г~ Г 'ке Г ° ~ ° ~ е' 1 у~ Г ' — — ~ *'л х ° Г =' В рассмотренном примере удалось структурировать диаграмму МТ, не вводя вспомогательных букв в ее рабочий алфавит (роль такой буквы удалось возложить на Н).

В середине ХХ века многими отечественными исследователями были предложены свои исчисления схем программ ~39~. Лекция 13 2.7.4 Доказательство теоремы о нормированной вычислимости Для доказательства теоремы 2.5Л по МТ 7'», вычисляклцей функцик> !', необходимо построить МТ Т~~, которая нормирова.нно вычисляет ту жс функцию 1. Для построения МТ 7~ используем прием конструирования МТ»сверху вниз». Сначала построим МТ 7~~, которая нормированно вычисляет функцию !", но рабочий алфавит которой содержит на один знак больше, чем рабочий алфавит МТ 7'~. Этот дополнительный знак обозна ~им через э'-. Машина Тм вычисляет ту же функцию 1, что и машина Т1, но отличается от машины 7'г следукицими свойствами: 1.

машина Т~~ не портит аргументов функции 7', а для машины Т~ это требование не обязательно; 2. магпина Т~~ останавливается только в том случае, когда слово, полученное в результатс ее работы, принадлежит множеству значений функции !" (и, следовательно,является значением этой функции); в этом случае машина '1~ останавливается ':Ж непосредственно после слова, являющегося значением функции 7: во всех остальных случаях машина Т~ никогда не останавливается.

Основная трудность, возникающая при построении машины Т', состоит в том, что и в процессе своей работы машина Т~ может изменить содержимое, вообще говоря, любой ячейки лепты, так что на ленте оказывается невозможным найти «безопасное» место для сохранения аргументов функции 7'. Эту трудность можно преодолеть следующим образом. Выберем произвольную ячейку ленты и пометим ее, записав в нее знак ф.

Все ячейки ленты, расположенные правее ячейки, помеченной л, занумеруем слева направо последовательными натуральными числами, начиная с 1. Ячейки ленты, расположенные левее помеченной ячейки, занумерусм справа налево последовательными отрицательными числами, начиная с — 1 1см. схему). -5-4-3.2-1 1 2 3 4 -5-4-3-2-1 1 2 3 4 «Раздвинем» ячейки правой части ленты, перенеся каждый знак, записанный в ячейку с номером 1, в ячейку с номером 2ю' — 1 (при этом, .как видно из схемы, знак, записанный в ячейке с номером 1, останется в этой ячейке, знак, записанный в ячейке с номером 2, будет перенесен в ячейку с номером 3 и т.

д.). !евую часть ленты отобразим на правую, перенеся буквы, записанные на левой части ленты, в образовавшиеся «зазоры» между знаками правой части, т. е. символ, записанный в ячейке — у, перенесем в ячейку с номером 27' (см. схему). Заменим машину Т~ мининой Т,', которая моделирует машину Т~ на 97 ° ' - а а каждое вхождение символа 1 диаграммой а „2 Машина Т~ моделирует машину. Тт и обладает тем свойством, что ее головка никогда не заходит левее ячейки, помеченной знаком з». Это дает пам возможность использовать для сохранения аргументов функции > часть ленты, расположенную левее ячейки со знаком ф:.

Итак, схему машишя Т можно представить в виде: ' Я Л»е Тсж тир ". ° ! и и !'!з+1 ТРЗд ~1 '' Х Г ° Л Г ° л. Машина Т>»' начинает работать в ситуации [Ли»ЛигЛ... Л>и„(Л)Л >,. где и>>, гог,..., и'„аргументы функции 7'. 11осле рабюты гфгфгХт „" > получается ситуация [Ли>>Ли>гЛ... Л>и ЛАЯЛ>о>Л>ог... Ли„(Л)Л > Машина Трзд раздвигает запись на правой части ленты, представив ее в виде [Ли >Ли>гЛ...

Ли>„ЛффЛа>аг... а», Ли>>Ли>г... Ли>„(Л) Л >=~* [Ли>>Л»>гЛ... Ли>„ЛффЛа>Лаг... Ла>,ЛЛЛ... (Л)Л > Далее начинает работать машина Т', которая либо никогда не останавливается, либо останавливается в ситуации [Ли»Ли>гЛ... Ли>„ЛфЯИ>(о)а, '> Если о, ф Л, то зто значит, что Т' не вычислила, значения функции Г"; если а = Л, то включается машина 7ож, которая «сжимает» слово,. являющееся результатом работы машины 'Г', располагая его оуквы в ячейках, идущих подряд., а нс через одну, после чего ма>пина Тйр убеждается, что слово, полученное в результате работы Т~, содержит лишь знаки еыходного алфавита машины Т>, Далее проверяется запись, произведенная машиной новой г>ег>>т>.

Для второ в диа> рамь>е мап>инь> 7 > заменим каждое вхождение символа и диаграммой: Тпг., если машина Тпг записала знак И (истина), то он стирается, после чего включается машина Ю, формирующая заключительную ситуацию Ри31Лш2Л... ЛИ~„Ц(ь низ,...,и~„)(Л)Л ) Если машина Тпр записала знак Л (ложь), то включается машина Т, которая никогда не останавливается. Для завершения конструирования машины Т~~ осталось разработать схемы машин Тгзд, Тс,ж, Т|тг, Т и Х.

При конструировании этих машин мы будем предполагать, что рабочий алфавит машины Ту содержит буквы ам а~,..., аь Машина Трзд описывается следующей схемой: +е Р е ) ° Г Л ~Ф ----н~. ( ° Г,~,Я ° ) ° 3 При составлении схемы машины Трзд использованы символы машин Т,~, Вз и Р„. Машина Ь,~ сдвигает головку влево до тех пор, пока не встретится ячейка со зна,ком ф; ее схема имеет вид 1 Ф Машина Е?з сдвигает головку вправо до тех пор, пока не встретятся три подряд идущие ячейки со знаком Л; схема этой МТ имеет вид 2 йу Машина Л~ сдвигает головку вправо до тех пор, пока не встретятся две подряд идущие пустые ячейки; она описывается схемой .