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