рекурсивные функции

Еще в 30-х годах нашего столетия математическая логика и возникавшая тогда теория алгоритмов казались наиболее абстрактными и наиболее далекими от практических приложений областями математики. В настояш;ее время положение коренным образом изменилось. Ныне общепризнанно, что обе названные области образуют теоретический фундамент для создания и применений быстродействующих вычислительных и управляющих систем. Резко возрос удельный вес математической логики и теории алгоритмов и в самой математике. Более того, в значительной степени через теорию алгоритмов и математическую логику происходит ныне проникновение математических методов в биологию, лингвистику, экономику вплоть до философии естествознания. Все это привело к тому, что математическую логику и теорию алгоритмов начали включать в учебные планы наших университетов и пединститутов в качестве дисциплин, обязательных для изучения студентами-математиками всех специальностей.

Настоящая книга возникла в результате обработки конспектов лекций по математической логике, теории алгоритмов и их приложений, читавшихся автором в 1956-

1959 гг. в Ивановском педагогическим институте и с

1960 г. в Новоспбнрском университете. В ней излагается лишь общая теория алгоритмов и рекурсивных функций.

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

Более серьезнылг недостатком предлагаемой книги может оказаться отсутствие в ней сведений о реальных вычислительных машинах. Однако в настоящее время теория програмьшрования и принципы устройства реальных вычислительных машин читаются во всех университетах в

. ПРЕДИСЛОВИЕ 7

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

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

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

Первая половина книги в несколько ином виде была издана студентами Новосибирского университета в 1960 г. ротапринтным способом. Остальные главы читались в рукописи сотрудниками и студентами кафедры алгебры и математической логики НГУ. Всем им автор признателен за советы и замечания.

А. И, Мальцев

ПРЕДИСЛОВИЕ РЕДАКТОРА КО ВТОРОМУ ИЗДАНИЮ

Первое издание книги вышло в 1965 г. В течение двух десятилетий книга была и оставалась одним из самых превосходных пособий по теории алгоритмов. Широкий охват материала, доступное изложение, выход на самую современную проблематику - вот неоценимые достоинства книги.

В текст второго издания книги внесены лишь самые несущественные изменения. Исправлены некоторые неточности. Изменено доказательство утвернодения Ж) в п. 5.4. В п. 8.4 приведено другое, более короткое и прозрачное, доказательство теоремы о существовании максимальных мнонеств.

А. И. Мальцев всегда живо интересовался диофантовой проблематикой и кончил свою книгу одной из труднейших теорем (того времени) в этой области. В частности, его интересовала и десятая проблема Гильберта. В 1970 г. Ю. В. Матнясевич получил свой знаменитый результат: всякое рекурсивно перечислимое мно?кество диофантово. Этот результат позволил получить ответы на многие вопросы, но породил и много новых. В частности, оказалось, что десятая проблема Гильберта алгоритмически неразрешима. Освещение всех вопросов, относяпщхся к этой проблематике, по-видпмому, требует отдельной книги.

Именно этими обстоятельствами вызвана необходимость добавить ко второму изданию книги краткое приложение, содержащее минимум фактов, нужных для доказательства теоремы о дпофантовости.

Д. А. Захаров

Уже на самых ранних ступенях развития математики (Древний Египет, Вавилон, Древняя Греция) в ней стали возникать различные вычислительные процессы чисто механического характера; с их помощью искомые величины ряда задач выт1ислялись последовательно из данных исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов или - в другом написании - алгорифмов. Вплоть до 30-х годов нашего столетия это понятие алгоритма в основе своей не менялось, хотя приобретало вс-большую и большую отчетливость. Тем не менее, оно осе тавалось интуитивным понятием, имевшим скорее методологическое, а не математическое значение. Сущность его легко уясняется из следующих примеров.

В десятичной системе счисления натуральные числа изображаются конечными последовательностями цифр О, 1, . . ., 9. Спрашивается, как найти десятичную запись числа, равного сумме, разности, произведению, частному двух чисел, заданных своими десятичными записями. Известные всем из начальной школы процессы, с помощью которых решаются эти задачи, и являются алгоритмами сложения, вычитания, умножения и деления целых чисел 1! десятичной системе счисления. Аналогичные алгоритмы известны п для произвольных /р-пчных систем счисления.

Таким же ярким примером алгоритма может служить п процесс нахождения наибольшего общего делителя Двух положительных натуральных чисел а, а. Состоит он, как известно, в след5пощем:

1) делим на а, находим остаток а п смотртг, равен он О или нет. Если равен, то процесс обрывается и ва - пскохшй наибольший общий делитель. Если же О, то

2) делим а, на а п находилг остаток а. Если = О, то процесс обрывается и Яд - искоишй наибольший общий делитель. Если а > О, то

3) делим Яз на и т. д.

Так как . . . > О, то указанный процесс оборвется самое большее через а, шагов и мы при его обрыве найдем требуемый наибольший обилий делитель чисел fflj и Яд-Аналогичные процессы применяются для нахождения наибольшей обш;ей меры двух отрезков, наибольшего обш;его делителя двух многочленов и т. п. Все эти процессы известны сейчас под названием алгоритмов Евклида.

Из других алгоритмов укажем еш;е алгоритмы разложения натурального числа на простые множители, извлечения квадратного корня из натурального числа, решения системы линейных уравнений методом последовательного исключения неизвестных и т. д.

Отметим теперь несколько обш;их черт алгоритмов, ясно вырисовываюш;ихся из предыдуш;их примеров и часто признаюш;ихся (Колмогоров и Успенский [1], Марков [2]) характерными для понятия алгоритма.

а) Алгоритм - это процесс -последовательного построения величин, идуш;ий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следуюш;ий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыД5Ш1;ий момент времени {дискретность алгоритма).

б) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествуюш;ие моменты времени [детерминированность алгоритма).

в) Закон получения последуюш;ей системы величин из предшествующей должен быть простым и локальным {элешнтарностъ шагов алгоритма).

г) Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма [направленность алгоритма).

д) Начальная система величин может выбираться из некоторого потенциально бесконечного множества [массовость алгоритма).

Понятие алгоритма, в какой-то мере определяемое требованиям а) - д), конечно, не строгое: в формулировках этих требований встречаются слова «способ», «величина», «простой», «локальный», точный смысл кото-

рых не установлен. В дальнейшем это нестрогое понятие алгоритма будет называться непосредственным или интуитивным понятием алгоритма.

Интуитивное понятие алгоритма хотя и нестрогое, но настолько ясное, что практически не было серьезных случаев, когда математики разошлись бы в мнениях относительно того, является ли алгоритмом тот или иной конкретно заданный процесс. Этим легко объясняется своеобразное положение, сложившееся в математике с алгоритмическими проблемами к началу XX в. В этих проблемах требуется найти алгоритм для решения некоторой совокупности родственных задач, в условия которых входит конечная система параметров, могущих принимать обычно произвольные целочисленные значения. Например, требуется найти алгоритм, позволяющий для каждой четверки целых чисел а, Ь, с, d узнать, существуют ли целые числа х, у, удовлетворяющие уравнению

ах + Ъху -\- су = d.

Был найден процесс, при помощи которого, исходя из заданных чисел, через конечное число «шагов» можно было получить ответ «да» или «нет» на. указанный вопрос. Многие другие алгоритмические проблемы также были решены путем указания конкретных разрешающих процессов. Положение существенно изменилось в XX в., выдвинувшем на первый план такие алгоритмические проблемы, существование положительного решения которых было сомнительным. Действительно, одно дело - доказать существование алгоритма, другое - доказать отсутствие алгоритма. Первое можно сделать путем фактического описания процесса, решающего задачу; в этом слзчае достаточно и интуитивного понятия алгоритма, чтобыТудостовериться в том, что описанный процесс есть алгоритм. Доказать нес5Ш1;ествование алгоритма таким путем невозможно. Для этого надо точно знать, что такое алгоритм. В двадцатых годах нашего века задача точного определения понятия алгоритма стала одной из центральных дштематических проблем. Решение ее было получено в середине тридцатых годов в работах Гильберта, Гёделя, Чёрча, Клпни, Поста и Тьюринга в двух формах. Первое решение было основано на понятии рекурсивной функции, второе - на описании точно очерченного класса процессов.

Выше уже говорилось, что для алгоритлшческих проблем типичным является положение, когда требуется найти