алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров . . ., х„, а искомым результатом служит также целое число у. Иначе говоря, речь идет о суп];ество-вании алгоритма для вычисления значений числовой функции у, зависящей от целочисленных значений аргументов Xi, . . Хп- Числовые функции, значения которых можно вычислять посредством некоторого (единого для данной функции) алгоритма, называются вычислимыми функциями. Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие вычислимой функции оказывается интуитивным. Тем не менее, при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство. Совокупность процессов, удовлетворяющих условиям а) - д) и, следовательно, подпадающих под интуитивное понятие алгоритма, очень обширна и мало обозрима. Напротив, совокупность вычислимых функций для самых разных пониманий процессов, удовлетворяющих условиям а) - д), оказалась одной и той же и притом легко описываемой в обычных математических терминах. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекурсивных функций.

Отправляясь от идей Гильберта, Г ё д е л ь [1] впервые описал класс всех рекурсивных функций как класс всех числовых функций, определимых в некоторой формальной системе. Исходя из совершенно других предпосылок, Чёрч в 1936 г. пришел к тому же классу числовых функций, что и Гёдель. Анализ идей, приведших к этому классу функций, позволил Черчу первым опубликовать гипотезу о том, что класс рекурсивных функций тождествен с классом всюду определенных вычислимых функций. Эта гипотеза ныне известна под именем тезиса Чёрча. Так как понятие вычислимой функции точно не определяется, то тезис Чёрча доказать нельзя.

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

ки, к л и н И [1] ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные (т. е. не обязательно определенные для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Конечно, более общая гипотеза Клини так же недоказуема, как и гипотеза Чёрча. Однако исследования, проводившиеся весьма многими математиками в течение последних тридцати лет, выявили полную целесообразность считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.

В дальнейшем мы не будем различать тезисы Чёрча и Клини и под именем тезиса Чёрча будем понимать гипотезу Чёрча в том расширенном виде, который был придан ей Клини.

Тезис Чёрча оказался достаточным, чтобы придать необходимую точность формулировкам алгоритмических проблем и в ряде случаев сделать возможным доказательство их неразрешимости. Причина этого заключается в том, что обычно в алгоритмических проблемах математики речь идет не об алгоритмах, а о вычислимости некоторых специальным образом построенных функций. В силу тезиса •Чёрча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. Поэтому обьпная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной. Именно этим путем Черчу [21 удалось первому доказать неразрешимость основной алгоритмической проблемы логики предикатов - проблемы тождественной истинности формул исчисления первой ступени.

Точное описание класса частично рекурсивных функций вместе с тезисом Чёрча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само ионятие алгоритма и уже затем при его помощи точно определить и класс вычислимых функций? Это было сделано П о с т о м [Ц и Т ь ю р и н г о м [1] независимс друг от друга и почти одновременно с изложенньвш выше работами Чёрча и Клини. Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы - это процессы, которые может совершать подходяще устро

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

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

Сравнивая обычное определение частично рекурсивных функций с определением тех над функций как функций, вычислимых на машинах Тьюринга - Поста, легко заметить следующую направленность этих определений. Обычное определение частично рекурсивных функций настолько широко, что из него почти непосредственно видна частичная рекурсивность функций, вычислимых посредством процессов, алгоритмический характер которых интуитивно ясен. Напротив, определение с помощью машин Тьюринга - Поста очень специальное. Его цель - показать, как самые сложные процессы можно моделировать на весьма простых устройствах. Поэтому, если надо показать, что алгоритмические процессы можно моделировать на еще каких-либо специальных устройствах, то машины Тьюринга - Поста обьгано берутся в качестве отправно го пункта рассуждений. В частности, этим путем Нови ков [11 решил классическую проблему тождества теории групп. Это была первая крупная алгоритмическая проблема, возникшая в математике независимо от мателгатической логики и теории алгоритмов и решенная при помопщ развитой теории алгоритмов. С другой стороны, одна из наиболее знаменитых алгоритмических проблем математики- так называемая 10-я проблема Гильберта о разрешимости

алгебраических уравнений в целых числах - пока все еще остается открытой (1963 г.), хотя алгоритмическая неразрешимость близкой задачи о существовании целочисленных решений показательных уравнений была недавно установлена группой американских математиков (см. § 16 этой книги) *).

Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Математическая логика, основания математики, алгебра, геометрия и анализ остаются и сегодня одной из основных областей приложения теории алгоритмов. Другая область ее приложений возникла в сороковых годах в связи с созданием быстродействующих электронных вычислительных и управляющих машин, которые с большой точностью моделируют машины Тьюринга - Поста. Наконец, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики, физиологии мозга и психологии, философии естествознания. Например, достаточно старые вопросы о том, является ли мозг сложной машиной, как он работает, в чем состоит различие между трудом творческим и механическим, в первом приближении теперь часто формулируют следующим образом: моншо] ли принципиально построить машину Тьюринга, перерабатывающую поступающую информацию так же, как мозг какого-нибудь животного, можно ли отождествлять труд механический с трудом согласно заданному алгоритму и т. п. Ясно, что ответ на эти и многие другие аналогичные вопросы сама теория алгоритмов дать не в состоянии, но она помогает отчетливее попять суть вопросов такого рода.

Чтобы иметь возможность увереннее решать алгоритмические задачи, возникающие в различных отделах теоретической и прикладной математики, необходимо иметь достаточно развитую самостоятельную теорию алгоритмов. В настоящее время такая независимая и богатая теория алгоритмов уже создана. Первое систематическое излож-е-иие ее было осуществлено К л и н и [3], монография которого «Введение в метаматематику» остается и поныне одним пз основных руководств в рассматриваемой области науки. Однако теория алгоритмов и рекурсивных функции изложена в этой монографии в тесном переплетении с рядом разделов математической логики с расчетом на

*)10-я проблема Гпльберта а.игорптмпческп неразрешпм см. 1атпясев11ч [1*]). См. также Приложение, с. 363.

ВВЕДЕНИЕ

Г Л[А В[Ар

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

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

О логической зависимости разделов книги

В данной книге обычным шрифтом напечатаны те раз делы, материал которых излагается, как правило, в общих курсах теории алгоритмов. Мелким шрифтом набраны разделы, содержащие результаты более специального характера. При первом чтении книги эти разделы, при желании, мон{Но опустить. Наконец, много важных результатов специального характера читатель может найти в дополнениях, примерах и задачах, помещенных в конце каждого параграфа. Результаты эти приведены без доказательств, но указаны источники, где доказательства можно найти.

При чтении этой книги не обязательно иззчать ее разделы в той последовательности, в какой они напечатаны. Более того,; лицам, интересующимся в первую очередь лишь приложениями теории алгоритмов, будет, вероятно, удобнее изучать разделы книги в следующем порядке: § 1, § 2, пи. 3.1-3.4, § 4, § И, пп. 12.1-12.4, п. 6.3, п. 12.5, § 13, пп. 7.1-7.3, пп. 8.1-8.2, § 14, § 15, § 16.

ОСНОВНЫЕ ПОНЯТИЯ

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

(\ § 1. Функции и операции

( Этот параграф имеет вспомогательное значение. Здесь

гч с целью установления терхшнологин и употребляющейся далее символики напоминаются определения ряда всем

< известных общематематических понятий.

\ 1.1. Алфавит. Слова. Исходным материалом для нас будет служить понятие ленты, разделенной на («равные») участки, называелше ячейками или клетками. Лента будет считаться конечной длины в каждый момент времени, не-ограппченно продолжаемой (надстраиваемой) в обе стороны и направленной, так что у каждой ячейки есть соседняя справа и соседняя слева.

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

Произво.льная конечная совокупность букв называется й-лфавитом. Выражение «рассмотрим алфаврЗтвддйё пз букв А, Biy означает, что будет paccsradjKpea,v\