Албанская философская и общественная мысль—алгебра логики 33 3 глава

7°. Сотри надчеркнутую палочку и все следующие за нею палочки и перейди к выполнению правила 8°.

8°. Сотри нижнюю черточку у подчеркнутой палочки; то, что получилось, и есть результат.

Применяя этот А. к комбинации ИИ, взятой в качестве началь­ного данного, получим последовательно; по правилу 1° — ill, по правилу 2° — i. || Т. по правилам З^э, 4°, 5° — | _[ | т, по прави­ла» 6°, 3^s, 4° — 11 Т |> по правилу 7°— I X, по правилу 8° — и (результат). Если же попытаться применить А. к комбинации, то получим: по правилу 1° —_1_ и, по правилу 2° — х I Г, по правилам 3\ 4°, 5°—| _|_ у, по правилу 6 — | I I, далее нужно пе­рейти к выполнению правила 3°, но правило 3° выполнимо лишь при условии, что подчеркнутая палочка не надчеркнута. Т. о., для создавшейся ситуации А. не содержит указаний, как посту­пать дальше; произошла т. н. безрезультатная остановка (остановка, не сопровождающаяся получением результата). Легко подметить, что вообще сформулиров. А. дает результат при применении его к любой комбинации из четного числа па­лочек, и результатом в этом случае является комбинация, со­стоящая из половинного числа палочек; А. не дает результата в применении к любой комбинации, состоящей из нечетного числа палочек.

Пример2. В логике и математике всякий конечный набор внаков нал. «алфавитом», входящие в него знаки — «буквами» алфавита, а конечная (в т. ч. пустая) последовательность написанных друг за другом букв к.-л. алфавита наз. „словом" в этом алфавите. Напр., арабские цифры образуют алфавит, а всякая десятичная запись целого числа является словом в эгом алфавите.

Рассмотрим алфавит (а, е) из двух букв: айв. Приме­рами слов в этом алфавите являются: в, ав, вва аааеавв и т. д. Условимся называть «допустимым» переход от слова в эгом алфавите к др. слову в этом же алфавите согласно одному из след. двух правил:

1) если слово имеет вид аР, где Р — произвольное слово, перейти к слову Рв;

2) если слово имеет вид ваР, где Р — произвольное слово, перейти к слову Рава.

Далее формулируется след. предписание: «исходя из к.-л. слова (взятого в качестве начальных данных), делай допустимые переходы до тех пор, пока не получится слово вида ааР; когда слово такого вида получится, отбрось первые две буквы, а то, что останется, и есть результат». Поскольку каждый раз выполнимо не более одного правила перехода, то сформулиров. предписание образует А., возможными на­чальными данными к-рого служат слова в алфавите (а, в). Возьмем в качестве начальных данных слово ваваа. Согласно правилу 2 получим вааава. Снова применяя правило 2, полу­чим ааваава. В силу нашего предписания надо остановиться; результатом (применения А. к слову ваваа) является ваава. Возьмем в качестве начальных данных слово ваава. По пра­вилу 2 получим аваава. По правилу 1 получим ваавав. Далее получим последовательно ававава, вававав, вававава и т. д. Можно доказать, что процесс никогда не закончится (т. е. ни­когда не возникает слово, начинающееся с двух букв а, и для каждого из получающихся слов можно будет совершить допустимый переход). Т.о., А. не дает результата при приме­нении к слову ваава. Возьмем в качестве начальных данных слово ваав. Последовательно получим ваавв, аввава, ввавав. Далее ни одно из правил 1 и 2 не выполнимо, и в то же вре­мя результат не получился. Поэтому в применении к слову аваав А. также не дает результатов.

Огнониые черты Л. По утверждению А. А. Маркова, для А. характерны следующие осн. черты: а)о п р е д е л е н и о с т ь алгоритмич. предписания, заключающаяся в его не оставляющей места произволу точности и общепонятности (в силу этой опре­деленности предписания алгоритмич. процесс является детер­минированным: каждая стадия процесса однознач-

но определяет следующую стадию); б) массовость, заклю­чающаяся в возможности для каждого А, исходить из варьи­руемых в известных пределах начальных данных; в) р е-зультативность, заключающаяся в направленности его на получение искомого результата. Детерминированность А. обеспечивает возможность сообщения его одним лицом дру­гому лицу с тем, что это другое лицо сможет выполнять А. без участия первого; это же свойство детерминированности делает возможным передачу выполнения А. машине. Массовость А. предполагает, что существует нек-рая совокупность (для каж­дого А. своя) возможных начальных данных. Как задается эта совокупность — это уже другой вопрос. Можно считать, что соответствующая какому-либо А. совокупность возмож­ных начальных данных не задается отдельно от А., а ука­зывается естеств. образом самим содержанием этого А. (так, для А. сложения столбиком соответствующая совокупность состоит из всех пар записей чисел в десятичной системе). Когда какой-то конкретный объект выбирается в качестве начальных данных А., то говорят о применении А. к этому объек­ту. Если А. дает результат при применении его к нек-рому объекту, то говорят, что он п р и м е и и м к этому объекту. Результативность А. вовсе не означает, что А. обязан быть при­меним к любому объекту из соответствующей совокупно­сти возможных начальных данных (см. примеры 1 и 2). Здесь уместно отметить, что можно построить такой А., для к-рого не существует никакого А., к-рый распознавал бы по про­извольным начальным данным первого А., применим к ним первый А. или нет.

Основные абстракции теории А.В науч. практике сложился ряд специфич. для математики и логики абстракций. Та­ковы прежде всего абстракция актуальной бесконечности, абстракция отождествления, абстракция потенциальной осуществимости. Сов. ученый А. А. Марков показал, что две последние необходимы при рассмотрении А. Алгорит­мич. процесс расчленяется на отд. шаги, каждый из к-рых предполагается настолько элементарным, что возможность его фактич. осуществления не вызывает сомнений. Вместе с тем число этих элементарных шагов, требующееся для получения результата, может быть настолько велико, что достижение результата может считаться практически неосуществимым. Однако представление о практич. осуществимости или не­осуществимости того или иного числа шагов является относи­тельным. Оно меняется с развитием вычислит, средств (в прин­ципе может меняться и представление об элементарности отд. шага). В теории А. поэтому отвлекаются от «практич. осуществимости» и считают осуществимым любое конеч­ное число шагов. Тем самым при изучении А. допускают абстракцию потенциальной осуществи­мости, состоящую в отвлечении от реальных границ на­ших возможностей. Развитие быстродействующих электрон­ных вычислит, машин быстро отодвигает эти границы все дальше и дальше. То, что было лишь потенциально осуществимым вчера, становится практически осуществи­мым сегодня. Это сближает теорию А. с практикой работы на вычислит, машинах и позволяет этим двум дисциплинам взаимно обогащать друг друга. Передача машине решения задач к.-л. серии невозможна без предварит, составления А. решения. Составление такого А. имеет, как правило, принци­пиальное значение (так, в проблеме машинного перевода ос­новным является именно составление А. перевода).

Абстракция потенциальной осуществимости необходима при рассмотрении не только алгоритмич. процессов, но и самих объектов, участвующих в этих процессах (в т. ч. «начальных данных» и «результатов»). Так, чтобы говорить о любом на­туральном числе (точнее, о записи этого числа, скажем, в десятичной системе), надо разрешить себе рассматривать за­писи столь больших чисел, что эти записи не уместились бы на земном шаре; т. о., и здесь, отвлекаясь от физич. осущест­вимости такой записи, используют абстракцию потенциальной осуществимости. Вообще к абстракции потенциальной осу­ществимости необходимо прибегнуть для того, чтобы рассуж­дать о сколь угодно длинных словах в заданном алфавите.

Объекты, построение и рассмотрение к-рых возможно в рамках абстракции потенциальной осуществимости (при про­тивопоставлении ее абстракции актуальной бесконечности), наз. конструктивными объектами. Таковы натуральные числа, представленные своими записями в к.-л. системе их обозначе­ний, слова в заданном алфавите и т. д., а также пары, тройки и вообще конечные последовательности, составленные из записей чисел, слов в алфавите и т. п.; рациональные числа (к-рые можно представить как тройки натуральных) и др. Конструктивными объектами являются и выражения т. н. исчислений, или формальных систем, что позволяет применить к последним аппарат теории А. Всякий А. (понимаемый как предписание) может (после записи этого предписания в виде комбинации каких-то символов) рассматриваться как кон­структивный объект. Напротив, объекты, рассмотрение к-рых невозможно без привлечения абстракции актуальной бесконеч­ности, не относятся к числу конструктивных объектов. Так, напр., конструктивными объектами не являются действитель­ные числа (в смысле Кангора, Дедекинда или Вейер-штрасса), геометрии, точки (поскольку анализ такой абстрак­ции, как «точка», приводит к представлению о точке как об ак­туально бесконечной системе малых тел) и т. д. Конструктив­ные объекты группируются естеств. образом в совокупности, примерами к-рых служат совокупность всех слов в данном ал­фавите и вообще любая совокупность всех объектов к.-л. «ти-

40 АЛГОРИТМ

па» из числа перечисл. выше типов конструктивных объектов. Каждая такая совокупность конструктивных объектов задается способом конструирования принадлежащих к ней объектов. Другой осн. абстракцией, используемой при рассмотре­нии конструктивных объектов и А.. является абстракция отождествления. В нек-рых случаях о двух объектах го­ворят как об одинаковых. Условия «одинаковости» ус­танавливаются каждый раз применительно к данной ситуа­ции. Так, напр., при производстве вычислений человеком на бумаге обычно бывает безразличным шрифт, к-рым пишут­ся цифры, и записи 1647 и 1647 рассматриваются как одинако­вые; однако можно представить себе ситуации, когда сущест­венно различие прямого и курсивного шрифтов (как, напр., при восприятии слов, встречающихся в данной Философской Энциклопедии). Тогда две записи будут уже рассматриваться как неодинаковые, но записи 1647 и 1647 все равно — в обыч­ных случаях — как одинаковые (хотя физически это разные объекты). Обычно принимают, что конструктивные объекты состоят из нск-рых достаточно простых «элементарных частей» (подобно тому, как слова — из букв) и два конструктивных объекта считаются одинаковыми, если они состоят из одина­ковых элементарных частей, расположенных в одинаковом по­рядке. Без понятия «одинаковости», на основе к-рого считают­ся, напр., одинаковыми цифры, написанные мелом на доске, и цифры, написанные чернилами в тетради, невозможно обу­чение. Абстракция отождествления позволяет говорить об одинаковых объектах как об одном и том же объекте. Она приводит к образованию понятия «абстрактного объекта»: именно, два одинаковых конкретных объекта считаются пред­ставителями одного и того же абстрактного объекта. Каждый А.«примененный к одинаковым объектам, приводит также к одинаковым объектам. Поэтому можно считать, что каждый А., задает процесс преобразования абстрактных конструктив­ных объектов. Это свойство А. (вместе с детерминированностью) обусловливает их повторимость или воспроизводимость: будучи выработан в форме А. над абстрактными конструктив­ными объектами, А. может быть повторно воспроизведен для любых конкретных конструктивных объектов, допустимых для данного А.

Из сказанного должно стать ясным, что начальные данные равно как окончат, результаты, возникающие при осуществ­лении к.-л. А., суть всегда конструктивные объекты (всякое «состояние» алгоритмич. процесса есть конструктивный объ­ект!). Невозможность даже потенциально осуществимых про­цессов над неконструктивными объектами связана и с отсутствием способа опознавания их как одинаковых или неодинаковых (ср. известное положение кибернетики о пре­имуществах дискретных форм хранения информации перед непрерывными).

Существуют различные т. зр. относительно методов, до­пусти х при изучении А. Одна из них, выдвигаемая предста­вителями конструктивного направления в математике и логи­ке, состоит в том, что, поскольку для образования понятия А. достаточно абстракции отождествления и потенциальной осу­ществимости, то развитие теории А. должно вестись в рамках этих абстракций. Другая т. зр. допускает при изучении А. любые методы, вообще допускаемые к логике и математике, в т. ч. и требующие абстракции актуальной бесконечности. Так, можно себе представить случай, когда для доказатель­ства того, что нек-рый А., будучи применен к нек-рому объек­ту, даст результат, потребуется использование тесно связан­ного с абстракцией актуальной бесконечности закона исключенного третьего.

Ослолные понятия теории А. К числу осн. понятий, возни­кающих на основе понятия А., относятся понятия вычислимой функции, разрешимого множества и перечислимого множества. Функция наз. вычислимой, коль скоро существует А., вычи­сляющий эту функцию в след. смысле: а) А. применим к любо­му объекту, входящему в область определения функции, и дает в качестве результата то значение функции, к-рое она принимает для этого объекта, взятого в качестве ее аргумен­та; б) А. не применим ни к какому объекту, не входящему в область определения функции. Множество, расположенное в нек-рой совокупности конструктивных объектов (т. е. мно­жество, составленное из каких-то объектов этой совокупности), наз. разрешимым (относительно объемлющей совокупности), коль скоро существует А., разрешающий это множество (относительно указ. совокупности) в след. смысле: А. при­меним к любому объекту из объемлющей совокупности и дает в качестве пезультата ответ на вопрос, принадлежит пи этот объект " рассматриваемому множеству или нет. Наконец, непустое множество (см. Пустое) наз. перечи­слимым, коль скоро существует А., перечисляющий это множество в след. смысле: а) результат применения А. к любому натуральному числу существует и принадлежит рассматриваемому множеству; б) каждый элемент рассматри­ваемого множества может быть получен как результат приме­нения А. к нек-рому натуральному числу. По определению, пустое множество также относят обычно к классу перечис­лимых. Одна и та же вычислимая функция (соответственно, разрешимое множество, перечислимое множество) может вычисляться (соответственно, разрешаться, перечисляться) посредством различных А. Из определений вытекает, что аргументы и значения вычислимой функции, элементы раз­решимого или перечислимого множества суть всегда кон­структивные объекты. Заменяя конструктивные объекты (нек-рой фиксиров. совокупности) их номерами в произвольной

алгоритмич. нумерации (т. е. такой нумерации, для к-рой существует А. получения по объекту его номера и обратно), можно, как это часто делают в теории А., ограничиться рассмотрением лишь таких вычислимых функций, аргументы и значения к-рых суть натуральные числа, и лишь таких раз­решимых и перечислимых множеств, элементы к-рых суть также натуральные числа.

Можно доказать, что всякое разрешимое множество пере­числимо. В то же время удалось построить перечислимое, но не разрешимое множество. Этот первый конкретный пример (опубликован амер. ученым А. Черчем в 1936 в статье «Одна неразрешимая проблема элементарной теории чисел») отсутствия А. (а именно, А., разрешающего построенное множество) явился источником или образцом почти всех дальнейших примеров такого рода. Оказалось, что множество разрешимо тогда, и только тогда, когда перечислимо и оно, и его дополнение (до объемлющей совокупности объектов). Т. о., существуют такие дополнения к перечислимым множе­ствам, к-рые сами неперечислимы.

Связь теории А. с логикой. Понятия разрешимого и пере­числимого множеств тесно связаны о классификацией опре­делений (мы ограничиваемся здесь лишь такими определе­ниями, каждое из к-рых определяет объекты нек-рого типа или, что то же самое, нек-рый клаес объектов). Как известно, существуют две осн. схемы определений: «через род и видовое отличие» и «по индукции».

При определении «через род и видовое отличие» задается нек-рая объемлющая совокупность объектов («род») и указы­вается признак («видовое отличие»), выделяющий среди объ­ектов указ. совокупности класс определяемых объектов. Если считать, что это определение конструктивно, т. е. что объекты конструктивны и что наличие или отсутствие видового отличия у элемента рода алгоритмически распознаваемо, то опреде­ляемое множество оказывается разрешимым (и каждое раз­решимое множество можно определить таким образом). Тем самым разрешимые множества отождествляются с множествами, конструктивно определяемыми через род и видовое отличие.

Определение «по индукции» состоит из двух частей: базис­ной части, содержащей нек-рый перечень объектов, к-рые объявляются принадлежащими к определяемому классу, и индуктивной части, гласящей, что если объекты такого-то и такого-то вида принадлежат к определяемому классу, то и объекты такого-то и такого-то вида, связанные с первыми объектами нек-рым отношением, также принадлежат к опреде­ляемому классу. (Возможны и более сложные случаи т. н. перекрестных определений, когда одновременно определяется друг через друга несколько классов объектов). Если предпо­лагать определение конструктивным, т. е. объекты кон­структивными, перечень исходных объектов, содержащийся в базисной части, конечным, а содержащиеся в индуктивной части правила перехода от уже определенных объектов к но­вым алгоритмическими (в том смысле, что наличие или отсутствие отношения, о к-ром идет речь в индуктивной части, распознается посредством какого-то А.), то мы приходим к по­нятию множества, конструктивно определяемого по индукции, или (синоним) эффективно порождаемого множества (поскольку такое определение задает эффективный порож­дающий процесс, на отд. этапах развертывания к-рого «возникают» или «порождаются» определяемые объекты). Примером конструктивного определения по индукции служит определение допустимых шахматных позиций (т. е. позиций, к-рые могут возникнуть на доске в процессе игры). Базисная часть содержит одну единств, исходную позицию. Индуктив­ная часть содержит правила ходов фигур. Множество допусти­мых позиций, т. о., эффективно порождаемо. Другим при­мером эффективно порождаемого множества служит множество всех доказуемых формул к.-л. формальной системы или ис­числения: базисная часть определения доказуемых формул содержит аксиомы, индуктивная часть — правила вывода (аксиомы объявляются доказуемыми по определению и далее говорится, что если какие бы то ни было формулы доказуемы, то и формулы, полученные из них по правилам вывода, также доказуемы). Порождающим процессом является здесь процесс доказательства всех доказуемых формул. Наконец, процесс опровержения всех опровержимых формул исчисления также является примером эффективного порождающего процесса.

Понятие эффективного порождающего процесса очень тесно связано с понятием А. Мы дали определение (прибли­зительное) эффективного порождающего процесса, опирающее­ся на понятие А. В свою очередь, понятие порождающего про­цесса позволяет определить на его основе если не само понятие А, то, во всяком случае, понятие вычислимой функции. Дей­ствительно, пусть нек-рый порождающий процесс способен «порождать» объекты, имеющие вид пар (х, у), и пусть у любых двух «порожденных» пар с совпадающими первыми членами совпадают и вторые члены. Тогда процесс след. образом опре­деляет функцию у—-fix): функция определена для объекта х„ тогда, и только тогда, когда х₀ есть первый членк.-л. порожден­ной пары: значение функций для аргумента х₀ равно в таком случае второму члену этой пары. Функция, определенная в указ. смысле эффективным порождающим процессом, оче­видно, вычислима [чтобы найти /(хо), надо развертывать про­цесс до тех пор, пока не найдем пары с х„ в качестве первого члена]. Обратно, всякую вычислимую функцию можно опре­делить посредством эффективного порождающего процесса. Алгоритмич. процессы и порождающие процессы близки друг другу с логич. точки зрения. В основании каждого из

АЛГОРИТМ 4t

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

При надлежащих уточнениях понятия эффективного по­рождающего процесса выясняется, что каждое эффективно порождаемое множество перечислимо, и обратно. Это обстоя­тельство, в сочетании с приведенными выше взаимоотноше­ниями между перечислимым и разрешимым множествами, позволяет заключить следующее. Всякий класс объектов, допускающий конструктивное определение через род и видовое отличие, допускает и конструктивное определение по индукции, но не обратно: существует класс объектов, конструктивно опре­деляемый по индукции, но не допускающий конструктивного определения через род и видовое отличие; дополнение к этому классу объектов (по объемлющей совокупности конструктив­ных объектов) не допускает эффективного индуктивного определения. Каждый конструктивный порождающий процесс можно представить в виде процесса получения доказуемых формул подходящего исчисления. Поэтому пример класса, обладающего только что описанными свойствами, можно по­строить в виде класса всех доказуемых формул нек-рого исчис­ления. Более того, оказалось, что это обстоятельство имеет место для любого достаточно содержат, исчисления (напр., для исчисления предикатов или для исчислений, формали­зующих арифметику), т. к., если исчисление достаточно со­держательно, то в нем можно выразить любой эффективный порождающий процесс. Класс всех доказуемых формул такого исчисления (являясь, конечно, перечислимым) не является разрешимым, так что не существует А., распознающего до­казуемость формул исчисления; в этом смысле говорят, что исчисление неразрешимо. Поскольку класс всех доказуемых формул исчисления не является разрешимым, то дополнит, к нему класс всех недоказуемых формул не является пере­числимым и, следовательно, не может быть получен никаким порождающим процессом; в частности, невозможно построить такое исчисление, в к-ром «опровергались» бы все недоказуемые формулы первонач. исчисления и только они; тем более, все эти недоказуемые формулы не могут быть опровергнуты сред­ствами самого первонач. исчисления, так что в первонач. ис­числении имеются т. н. неразрешимые (т. е. ни доказуемые, ни опровержимые) формулы. В этих рассуждениях можно ограничиться лишь такими формулами, к-рые при содержат, интерпретации исчисления выражают осмысленные (т. е. либо истинные, либо ложные) суждения, и обнаружить, следова­тельно, и среди таких формул неразрешимые. Отсюда вытекает, что можно предъявить формулу, выражающую истинное суждение, но не доказуемую в исчислении; в этом смысле говорят, что система неполна. Подчеркнем, что в силу общего характера проводимых рассуждений свойство неполноты присуще любому достаточно содержат, исчислению.

Понятие неразрешимости исчисления опирается на понятие А., и неудивительно что факт неразрешимости устанавливается на основе исследований в области теории А. Весьма существен­ным (и, может быть, неожиданным на первый взгляд) является то обстоятельство, что такой общелогич. факт, как неполнота исчислений (факт, выражающий принципиальную невозмож­ность полностью формализовать процесс логич. вывода и впер­вые строго доказанный австр. ученым К. Гёделем еще в 1931, до уточнения понятия «А.»), может быть получен, как мы только что видели, средствами теории А. Это обстоятель­ство уже одно показывает огромные возможности применений теории А. к вопросам логики. Эти применения не ограничи­ваются приведенным примером. Еще в 1932 сов. ученый А. Н. Колмогоров предложил истолкование созданной интуи-ционистами конструктивной логики при помощи содержат, средств, не имеющих никакого отношения к установкам ин­туиционизма; именно, каждое предложение конструктивной логики Колмогоров предложил истолковывать как проблему. Понятие проблемы требовало, однако, конкретизации, к-рая могла быть дана только на базе уже разработанной теории А. Два конкретных класса проблем, пригодных для интерпре­тации конструктивной логики, предложили, соответственно, амер. ученый С. К. Клини в 1945 и сов. ученый Ю. Т. Медведев в 1955. В 1956 сов. ученый Н. А. Шанин выдвинул новую концепцию, согласно к-рой не всякое высказывание конструк­тивной логики требует истолкования в виде проблемы.

К этому кругу идей примыкают вопросы «конструктивиза­ции», или «нахождения конструктивных аналогов», классич. математич. понятий и предложений; решение эгих вопросов также возможно лишь на основе теории А. Конструктивизация осн. понятий математич. анализа привела к разрабатываемому сейчас т. н. конструктивному математич. анализу. Намечаются пути конструктивизации и др. математич. теорий. Одним из осн. приемов, используемых при конструктивизации, является переход от изучаемых предметов к их именам, к-рые всегда являются конструктивными объектами.

Проблемы разрешения. Частным случаем массовых про­блем являются -разрешения проблемы. Проблемы разрешения к.-л. множества есть проблема построения А., разрешающего это множество. Соответств. серия единичных проблем состоит вдесь из проблем ответа на вопрос о принадлежности к множе-

ству, поставленный для каждого объекта из объемлющей со­вокупности конструктивных объектов. Обратно, всякая массо­вая проблема, соответств. серии единичных проблем ответа на вопрос, может быть рассмотрена как проблема разрешения нек-рого множества, а именно—множества тех единичных проблем, ответом на к-рые служит «да». Отсюда ясна важная роль проблем разрешения. Именно они подвергались изучению с т. зр. их разрешимости. Среди проблем разрешения выде­ляются проблемы, поставленные для классов доказуемых формул исчислений. Проблема разрешения класса всех дока­зуемых формул к.-л. исчисления наз. также проблемой раз­решения самого исчисления. (В рус. текстах проблему раз­решения наз. обычно «проблемой разрешимости»; однако «проблемой разрешимости» лучше называть проблему: «от­ветить, имеет ли решение данная проблема разрешения»).

Неразрешимые массовые проблемы. Проблема разрешения для к.-л. исчисления всегда есть проблема разрешения пере­числимого множества. Вообще все естественно возникавшие в математике проблемы разрешения оказывались проблемами разрешения перечислимых множеств. Таков упоминавшийся выше первый пример неразрешимой проблемы разрешения (и одновременно первый пример неразрешимой массовой проб­лемы вообще), опубликованный Чёрчем в 1936. Такова т. н. проблема тождества для ассоциативных систем, доказатель­ства неразрешимости к-рой опубликовали в 1947 независимо друг от друга А. А. Марков и амер. ученый Э. Л. Пост; этот результат представляет интерес как первый пример дока­зательства неразрешимости массовой проблемы, возникшей (еще в 1914) вне логики и теории А. Такова и знаменитая проб­лема тождества для грулл.поставленная еще в 1912, неразреши­мость к-рой доказана в 1952 сов. ученым П. С. Новиковым (Ленинская премия, 1957). Каждая из проблем тождества со­стоит в отыскании А., устанавливающего эквивалентность или неэквивалентность двух слов в заданном алфавите (ст того или иного определения эквивалентности зависит, имеем ли мы дело с ассоциативной системой или группой). Поэтому проблему тождества можно рассматривать как проблему разрешения множества всех пар эквивалентных друг другу" слов (относи­тельно совокупности всевозможных пар слов). При этом, по­скольку можно задать порождающий процесс получения всех пар эквивалентных друг другу слов, множество всех таких пар перечислимо.

Сводимость. Начиная с примера Чёрча 1936 и по 1944 все доказательства неразрешимости массовых проблем проводи­лись или могли быть проведены след. единообразным методом. Заведомо неразрешимая проблема, исследованная Чёрчем, сводилась к рассматриваемой массовой проблеме, так что если бы рассматриваемая массовая проблема была разрешимой, то оказалась бы разрешимой и проблема Чёрча (в этом смысле можно сказать, что доказательство неразрешимости рас­сматриваемой проблемы сводилось к доказательству неразре­шимости проблемы Чёрча). Возник вопрос, для всякой ли не­разрешимой проблемы разрешения ее неразрешимость может быть установлена таким способом. Этот вопрос, получивший название проблемы сводимости, был поставлен Постом в 1944; одновременно Пост привел несколько примеров неразре­шимых проблем разрешения, неразрешимость к-рых была ус­тановлена им методом, отличным от описанного выше (эти при­меры не решали еще проблему сводимости, поскольку оста­вался открытым вопрос, нельзя ли и для них найти такие до­казательства неразрешимости, к-рые сводились бы к дока­зательству неразрешимости проблемы Чёрча; впоследствии для нек-рых из указанных примеров такие доказательства были действительно найдены). Проблема сводимости стояла в центре исследований по теории А. вплоть до 1956, когда она была решена независимо сов. ученым А. А. Мучником и амер. ученым Р. М. Фридбергом. Был построен при­мер неразрешимой проблемы разрешения (для перечис­лимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Чёрча. Мучник показал даже больше, а именно, что не только проблема Чёрча, но и никакая другая проблема не может служить «стандартной не­разрешимой проблемой» в том смысле, что доказательство не­разрешимости любой неразрешимой проблемы разрешения для перечислимого множества могло бы быть сведено к дока­зательству неразрешимости этой стандартной проблемы.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: