Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 47
Текст из файла (страница 47)
в д, в, в вз в ... в вь где ун ..., ун гн ..., г, — все простые числа такие, что у~ ~уз~...< дь з~ <аз 4... 4зь то 1 ! и г, д„для всех й, 1<у<1. Напомним, что простые числа — это влемепты из Х, которые делятся только иа 1 и на самих себя. Полное докааательство этой теоремы песложпо, ио его вапись существенно отвлекла бы пас от основной задачи. Поэтому вместо доказательства мы предлагаем рассмотреть конструкцию алгоритма (процедуры/программы) для выделения упорядочеппых простых множителей дн ..., д, для любого данного и, Таким образом, избегая деталей ввода и вывода, мы мовгем испольвовать схему, представленную па рис. 9.5. Предположим теперь, что некоторая программа читает данные, которые состоят пз последовательности символов алфавита А (х, у, г).
Произвольно выбирая порядок <р для элементов нз А, можно получить ч(1) = х, ~р(2) = у, ~р(3) = з. Коли вводимая последовательность ъ имеет длину и и выражается как а~аз...а., где а,ыл, 310 тогда существует последовательпость »р '( )»р '(»х )...»р '(»х.) над (1, 2, 3). Вань первые л простых чисел Р», ..., Р„мы можем составить число т.г « '(«») е»(~,) «»(ва) Р» Р» 4" ° 'Р»» » 1 нааовем его Ф(а). Пусть по согла»пению Ф(Л) 1. Чтобы проиллюстрировать испольэовакие этой общей формулы, эакодвруем строку «хуххэ посредством 1, 2, 3 Рве.
й5 следующим обравом: 2»3«5»7« .30870. Испольауя теорему о единствепкости рвэлок»епкя на простые множители и тат факт, что Ф"' является бкекцией, имеем, что «хугз» является едивствекпой строкой иад А, которая дает это эпачопие. Следовательно, применяя Ф, мы можем 311 «обратить» вычисления, чтобы восстановить строку «хрхх», 11ри помощи этой процедуры все строки пад А мо«кпо закодировать таким образом, чтобы они имели рааные значения в множестве К. Это в силу упорядоченности, индуцируемой Х (поскольку РшХ), влечет упорядоченность строк из Ао.
Например, «хр»)«ухю Необходимо отметить два фактора, связанных с этим методом, Во-первых, поскольку А конечно, в г( существуют значения, которые не являются кодами какой-либо строки в Аа (например, не существует и «э А* такого, что Ф(а) 2», так как иначе аыА: <р-'(5)=а, а такого а не существует). Во-вторых, поскольку элементы Ао являются неограниченными, то таковыми являются и коды. (Для любого и ы Х возьмем простое р ) п и рассмотрим строку «» с«! .
с«а с«« такую, что !и! Р« л«; тогда отсюда следует, что о-»(ай о-«(аа) Ф(а) Д р« ' ~ р,„" ~ р,'„ра>п.) 1 1 Используя методику, описанную в 3 3 гл. 3, преобраауем кодирование Ф так, чтобы получить новое кодирование, которое сохраняет порядок, полученный Ф, но использует все У. Это один из тех случаев, когда трудно дать арифметическую формулу для вычисления измененных кодов, однако все еще достаточно легко описать спо соб их получения. Очевидно, что новое кодирование Ч' с областью значений У задается формулой «» !(аи: Ф(1)(Ф(с«))!.
В частном случае для рассмотренного в примере множества А и его упорядочения ~р первые десять значений Ф и Ч» приведены в табл. 9Л. Таблица 8Л й з В хх $ Вх «В «и тхх ЭЗ Строка и Ф(а) Ч'(а) 2 4 0 1 2 8 8 12 18 8 4 3 8 24 30 38 8 Е Чтобы получить вти,коды и выполнить процедуры кодирования, требуется машина, способная понимать и совдевать символы вне алфавита В ° (О, 1, 2, „8, 9), на котором определены злемеиты множества К Для этого 312 Г о 1 Р Г е 'л Ч' в' ' в ! ! ! т Н!В(! ! / / / ! / / / '. (д!/ Р У г.---- — ! Р а — ' — / ~!и~ат...в — ~ 6 ! ! ! ! ! ! ! ! / Ф Ф / / / / юе .~ ! р .йв диаграммы па рис.
9.6 восстанавливают сущность пропущенпых агапов. 6(й необходимо только устройство, позволяющее имитировать действие ф (и ф-!), некоторым простым способом воздействуя на таблицу ввода-вывода; остаток процедуры кодирования, включающий Ф и Ч", можно потом учесть прп помощи машины с неограниченной памятью. Следовательно, любой ввод в данную компьютерную систему может рассматриваться как конечная строка (взятая из потенциально бесконечного миожества строк над некоторым конечным алфавитом), и если применить описанный выше процесс к соответствующему алфавиту А, то зту строку можно преобразовать в единственный злемент )/. Обратная процедура, примеиенная к полученному значению из )/, дает зпачеиие над другим алфавитом В.
Следовательно, программа Р: А* - В* похожа иа соответствующую программу Р': !/- )/, где Р: сс Ф 1(Р'(Ф(сс))), Р'! /! Ф(Р(Ф ~(л))). Величина используемых значений даже в простых ситуациях делает примеры непригодными, одвако связаииые Переходы, включающие детальную спецификацию Р', являются сложными и не обязательио соответствуют Р «очевкдкым» образом.
Однако если Р вычислимо, то и Р' вычислимо. Как отмечалось выше, мы можем также применять такие «ке кодирующие процедуры к программам, и, следовательно, расширив Ч' таким образом, чтобы можно было игнорировать семаптически певерпые программы так же, как и программы, включающие синтаксические ограничения, можно перечислить все программы для данной системы, использующей числа из у. Мы предполагаем, что для того, чтобы программа превосходила любое заданное в У чвсло, к кей можно добавить пеограничеппое множество кодов, которые содер«««ат произвольно много нулевых утверждений, таких, как Л, — Ль Однако в большинстве языков программирования существует много избыточности в сиптаксисе; поэтому в лучшем случае мы будем обращать внимапие только на лексические знаки.
Прежде чем пытаться сделать замечания общего характера, рассмотрим, что можно сделать с простым языком, который использовался рапее в машине с неограиичеиной памятью. Существует четыре типа комаяд: х: Л; - Л<+ 1 йеп йо Со у »ц Л; Л<-1 йеп йо Со у ах 11 Л, = О йеп йо Со у е1зе йо Со г х«з«ор (Без потери общности мы можем предполагать, что всо программы начинаются с команды, помеченной индексом 1.) Бсе, что мы дол«кпы знать из команды х,— зто, какой тип операции должеп выполняться, па каком регистре и какая команда выколняется следующей.
Для того чтобы можпо было использовать ту же саму«о схему для всех команд, введем формат (тип, регистр, правильный выход, неправильный выход). Обозначая команды «останов» («»Сор»), «болыпе», «меньше» и «равко кулю» через О, 1, 2 и 3 соответствевво, получаем Ф-уровпевое кодирование типичных утверждений, как показано виже: Ф(В, — Л,+1 йеп йо Со у) 2'3'5"7" Ф(Л< — Л« — 1 йеп йо Со у) 2»3'5"7" Ф(11 Л, = О йеп яо Со у е(зе йо Со г)- 2 3'5"7' Ф (всов) 2'3'5'7' 1. 314 Поэтому команда Ф содержит всю информацию, необходимую для ее выполнения илн, если необходимо, для перехода к следующему шагу выполпеяия программы.
Поскольку все строки в А* конечны, а блок-схема программы для машины с бесконечной памятью сверху пе ограничена, то каждая отдельная программа имеет и утверждений, лжи. Тогда в«ажно распространить Ф на программы следующим образом: в фр«] Ф (ргой) Ц "' «=.1 где «ргои» состоит из и помеченных утверждений, из которых «-м является з,. Из Ф(ргой) можно получить Ф(з«) выделением компоненты р„и, следовательно, разлагал зто аначение на простые сомпол«ители, мы можем узнать детали утверждения, помеченного номером «. Используя подходящую «урезающую» функцию Ч", мы получаем кодирование, которое является биекцией между У, множеством всех программ для машины с бесконечной памятью н )т.
$.3. Проблема астапова. Теперь мы можем доказать. что конструкции некоторых общих программ невозможны: не только потому, что мы не находим решения, но и потому, что решение может не существовать, Формальные доказательства ограничим рассмотрением двух основных случаев.
Первое из доказательств получим, исходя нз начальных пркпципов, а затем покажем, как второе выводится иа первого, иллюстрируя, таким образом, общее использование техники сведения одних задач к другим. После етого сформулируем перечень проблем, относительно которых будет показано, что они неразрешимы подобным образом. Строго говоря, все утвер>кдения, приведенные ниже, относятся к программам па машине с бесконечной памятью со специальным кодированием функций Ч'«и Ч'».
Однако, задав произвольную «универсальную» .машину и подходящий яаык программирования, мы в состоянии построить адекватные кодирующне функции, и, следовательно, полученные результаты применимы н в общем случае. Первой аадачей, относительно которой мы докажем ее нераврешимость, является задача гамоприменимости. Теорема. Для машины с бесконечной памятью не суцествует программы, которая дяя «юбой заданной про- 315 враммы А при ее кодировании а Ч"1(А) будет останавливаться с выходным значением О, если А(а) останавливается (т.
е, программа А останавливается, если входное значение равно а), и с выходным значением 1, если А (а) не останавливается. Докавательство. Будем строить доказательство от противного. Предположим, что такая программа существует; назовем ее В. Итак, В(а) останавливается с результатом, равным О, если а приводит программу А к останову, н с результатом, равным 1, если а не приводит к останоеу А. Изменим программу В следующим образом. Заменим команду остаиова условной петлей, так что, если выходной регистр имеет эначеппе О, тгы обходим эту команду; в противном случае — останов. Назовем эту программу С (рвс.
9.7). Имеем следующее: С(х) останавливается (и "4 г=~ имеет то же самое выходное значение, что н В(х)) тогда и только тогда, когда выходное значение равно 1. зтэР Рассматривая С прн входном значении с — Ч'(С), получаем противоречие: так я 7 как С(с) останавливается тогда п только тогда, когда С(с)=В(с) 1, то В(с) 1 тогда и только тогда, когда С(с) не останавливается. Отсюда следует, что С ие может существоэатгч а поэтому и В не существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
