Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 48
Текст из файла (страница 48)
У Предыдущее доказательство по стилю подобно тому, которое испольэоэалось, чтобы опровергнуть существование множества Рассела в примере !.1 гл, 1. Еажется, что оно но~ит тривиальный характер, одяако, подобно многим другим кратким математическим рассуждениям, является достаточно тонким. Следует на это обратить внимание перед тем, как испольэовать этот факт при доказательстве более общего результата — неразрешимости проблемы останова. Теорема. Для машины с бесконечной памятью не существует программы, которая по произвольным входным данным, представляющим программу и ее данные, будет определять, останавливается программа на этих данных ияи нет.
Доказательство. Покажем, что если бы такая программа существовала, то мы могли бы путем выбора правильных входных данных решить проблему самоприч с16 меиимости. Поскольку последнее невозможно, то отсюда будет следовать, что решение проблемы осталова также иевозможио. Очевидно, что программа требует ввода двух сортов данных: а( Ч'1(А)) — кода программы А и х( Ч"г(Х)), где Х вЂ” входные данные для А. Это может быть закодировано обычным путем — с использованием двух различиых простых чисел р и о. Пусть входные данные будут р'д*, и предположим, что существует программа для решения кашей задачи; каэовем ее В.
Тогда В(р'о*) останавливается с результатом $, если А(Х) останавливается, и останавливается с результатом О, если А(Х) не останавливается. В этом случае из В можно создать новую программу С, добавляя к началу В последовательность команд, которые превращают содержимое (-го входвого элемента в (ро)'. Тогда ~(, если А(а) останавливается, (О, если А(а) не останавливается. Следовательно, С решает проблему самоприменимости, о которой мы внаем, что опа неразрешима. Следовательно, С ие существует, а поэтому не существует и В.
У Проблема останова является классическим результатом о неразрешимости в теории компьютеров. Приведенное здесь доказательство использует общую технику сведения одной задачи к другой. Далее показывается, что первая задача неразрешима, поскольку если бы это было ие так, то была оы разрешима и другая задача, о которой известно, что оиа неразрешима. Используя этот принцип (и соответствующие конструкции, детали которых здесь опускаются), можво пока- вать, что многие другие проблемы также неразрешимы.
В частности, неразрешимы следующие проблемы: а) остаиавливается или иег произвольная программа, если входное значение равно 0; б) останавливается или нет произвольная программа при любых входных данных; в) выполнеио ли равенство Е(С) И для произволы иой контекстио-зависимой грамматики С; г) выполиеио ли равенство Ь(С~) й Е (Сэ) Я1, где С1 и Сз — произвольные коатекстно-сзободвые грамматики; д) выполнено ли равенство Б(С) Т*, где С (М, Т, Р, 8)- произвольиая контекстно-свободная грамматика; З1г е) выполнено ли равенство Ь(6>) Б(бг), где ы> а бз — произвольные контекстно-свободные грамматики; ж) является лп произвольная контекстно-свободная грамматика неоднозначной. 1.4.
«Расширенная» машина. Насколько реалистичной нвляется машина с бесконечной памятью в качестве мо- дели компьютера? Память такой мап>ины, очевидно, пре- восходит памлть любой существующей машины, которая подвергается ограничениям как на число регистров, так и на значения, которые могут содержаться в каждом ре- гистре.
Однако эта идеализация в пределах машины с неограниченной памятью расширяет, а пе ограничивает воаможности машины. Существуют ли аспекты в компью- терных системах, которые не могут быть смоделированы пэ машине с неограниченной памятью? Ыы утверждаем, что нет. Хотя формально мы не мо- жем доказать это высказывание, остановимся па основных моментах такой «расширенной» машины, которая может моделировать все нуясные свойства, хотя в качестве аб- страктной модели она применяется редко. Нас будут интересовать следующие свойства: а) болыпой набор операций; б) более широкий набор внешних типов данных; в) массивы; г) стеки; д) более сильные команды управления; е) общий механизм управления; ж) рекурсия. В пп.
1,1 и 1.2 мы показалп, как в случае а) можно добавить арифметические операции к множеству команд, а в случае б), добавляя простые периферийные устрой- ства (длн того чтобы иметь воаможкость работать с спм- волами, которых пег э машине с неограниченной па- мятью), можно расширить диапазон представлений входных и выходных данных над произвольным алфа- витом. Остановимся па работе с массивами. Предположим, что нам необходим массив с десятью компонентами А (1], ... ..., А (10] и что содержимое этих регистров суть ап ..., а~э. С помощью методики, которая уже использовалась, мы можем сохранить эти эначенш>, вводя величину >э а = У р>, >-1 которую затем можно запомнить в одном регистре. Ыы 318 уже описывали пропедуру выделения каждого а, из а.
Этот метод пе зависит от границы массива и поэтому переносится на случай работы со стеками. В стеках можно хранить результаты промежуточных вычислений, не требуя существенно больше регистров. С помощью подходящего механизма управления (см. ниже) мы моя«ем также поместить в стек адреса возврата пз подпрограмм. Любая программа на машине с неограниченной памятью конечна, и строки программы могут быть пронумерованы (помечеяы) числами от 1 до л, и ш Х. В контексте блок-схемы программы мы можем сконструировать в случае е) «вычисление до«о», используя табличную технику, дан- Ф„=г 2 ную выше, для того, чтобы получить «бе1о(В,)», » как указано на рис. 9.8. Используя схему а;-Х 2 прямого кодирования для программ Ф (а не Ч'), мы можем закодкровать всю программу одним значением, которое запоминается в ре- ./ л.' гистре.
Разложение на Л»«л простые множители затем может использоваться для выделения кода «следующего утверждения». Это моде- рне, 9.8 лирует свойство ж), а вместе с использованием стеков дает возможность рекурсии з). Следовательно, используя машину с неограниченной памятью, моя«но произвести «расшпренне» путем добавления этих свойств. Однако в действительности такие расширения носят лишь внешний характер, а результирующая система может быть смоделировапа с использованием другой машины с неограниченной памятью, у которой блок-схема программы состоит нз простых команд увеличения, уменьшения и «равенства нулю». Упражнение 91. 1.
Построить на машине с неограниченной памятью блок-схему программы, осуществляющей проверку «й, л»». 319 2, Спроектировать машину с неограниченной памятью, которая, если дава программа, аакодироеанная в 1«», будет выполнять ату программу. (За основу ваять кодирующую схему нз п. 1.2.) $2, Конечные автоматы Уже достаточно много сказано об универсальных машинах (их свойствах и ограничениях на эти свойства), которые могут вычислять есе, что вычисляется, и, следовательно, проводя рассуждения в обратном порядке, получим, что любая вычислительная проблема, которая неразрешима в такой общей системе, будет неразрешима и в любой другой системе. Однако возникает вопрос: как это связано с реальнымп компьютера»»н3 Основная проблема — это конечность памяти реальной машины (правда, и ее можно несколько сгладить, используя машину с неограниченной памятью, оппсанную в и.
11). Машина с неограниченной памятью состоя«а из неограниченного числа регистров, каждый пз которых имел возможность содержать любое число нз множества Р. Хотя, как это следует из построений и. 1,4, мы можем обменять «короткую и широкую» память (имеющую несколько регистров, каждый с большой емкостью) на «длинную и тонкую» память (в которой емкость каждого регистра уменьшена, аато число регистров увеличено), существенное ограниченпе состоит в конечности числа различных конфигураций или состояния, которые может принимать память.
Такое ограничение вызвано физическими ограничениями. Это понятие формирует основу вашей математической модели конечных машин. 2.1. Детерминированные машины. В соответствии с опытом электронного машиностроения (низким уровнем аппаратуры прп построении элементов типа «не и» и т. и., микропроцессорных систем или универсальных цифровых машин) наша первая модоль воплощает в себе понятие детерминизма, т.
е. если некоторая ситуация достигается более одного раза, то в кал«дом случае устройство ведет себя одинаковым образом. Качнем с формального описания. Определение. Понсчныч (детернннированньм) автоматом М называется алгебраическая структура М (ч,2,1,2»,Р,р), 320 где <е — пепустое множество состояний; Х вЂ” конечный входной алфавит; 1 — отображеппе б<ХХ <,», пазыоаомое переходом (пли функцией переходов); до ы <Š— «ачальное состояние; р'. (», р' — мвожество заключительных состояний (илв прш<има»о<цих состояний); р — фувкцпя <<< Х Х - Х, нааываемая функцией печати (пли функцией выходов) . (В векоторых случаях полезно модифицировать фувкцию выходов таким обравом, чтобы оиа имела впд р: Ч Х Х Х - Х', где Х' — некоторый другой алфавит.) Идея состоит в том, что мы начинаем иа состояния до, и если д,<в1(до, в), то под действием входного символа в автомат переходит в состояние д.
Аналогично, если (уо, е) <и В„, то, когда автомат перейдет в состояние (цо, в), па выходе появится р(ао, в). Продолжая таким образом и читая каждый раз очередной входной символ, будем переходить от одного состояния к следующему, кока плп ие прочитаем символ, которого иет в Х, или входные данные будут исчерпаны — в этих случаях обработка прекращается. Входная последовательвость называется представимой (автоматом М), если состояние, в которое перешел автомат М, припадленшт Р. Для наглядности рассмотрим пример. Одпако про>иле опишем представление М в виде диаграммы. Во-первых, мы представим влементы () вершивамп орпеитировавиого графа, которые пзобража<отся маленькими кругами; имя состояния указывается внутри круга.
Элемевты вз р пме<от дополкительиые круги, иачерчепвые вокруг малепькпх кругов. Если ((дь в,), д»)ш 1, то проведем орпевтировапвое ребро от д, к д„и наметим его символом вь Далев, если ((дь в,), в,)ш р, то пометам ребро через в,: вь Н одному и тому я<е ребру может быть добавлено весколько меток. Наконец, определим до стрелкой, входящей в до. П ри мер 2.1. Рассмотрим машину, изображенную иа рпс. 9.9.
Предполов<им, что мы читаем строку «аЬЬаа». Ребра, обозиачающие фувкции перехода, заставляют машину проходить через состояния до, у<, Чо, Чь яо и Ф в указапвом порядке. Легко видеть, что, вачипая с до, под действием 1 получаем (йм а) у„(ум Ь) цо, (йм Ь) д„ (у„ а) - до (уо а) - д,. 21 д. ктк, г. вове 321 Однако д~ пе является заклгочительпым состолнием, и поэтому этот вход ие подходят. Прозерва диаграммы показывает, что строками, представимыми этой машиной, являются только те строки над алфавитом (а, Ы, з которых я Рис. 9.9 имеется четное число символов а и четное число символов Ь. У этой машины пет явного выхода; требуемая информация может быть извлечена из результиругощего состояния только после астапова машины.
Х Следующие дэа примера отпосятся к арифметическому »оборудованию» и фактически порождают непосредственный входной результат. Пример 2.2. Машина, изобрахгенная иа рис. 9.10 для пары строк кад (О, 11, вычисляет и выводит их сумму. Входные данные начинаются с битов с наименьшими (о,т):1 (г,о(: г (((,(э:О Ш,г(:о (т,о(:о (00:г Рис. 9.10 звачепиями, и пары читаются справа налево. По данным двум л-разрядным числам эта машина вычисляет их п-разрядную сумму. Однако она не распознает условий переполнения и ве работает с отрицательными числами. »' Проверяя свойства функции выхода (функция выхода имеет вид ~ Х (О, 11» - (О, 11), полезло всяомпить факты, 322 каса>ощнеся двоичной ариф»>етики и описанные в т 3 гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
