Лямбда-исчисление Черча

Понятие вычислимости — очень важ­ная и красивая математическая идея. При­мечателен также и ее малый возраст в срав­нении с другими столь же фундаменталь­ными математическим проблемами: она бы­ла впервые выдвинута только в 1930-х го­дах. Эта проблема имеет отношение ко всем областям математики (хотя, справедливости ради, отметим, что большинство математи­ков пока не часто обращаются к вопро­сам вычислимости). Сила этой идеи связа­на отчасти с существованием четко опре­деленных и все же неразрешимых матема­тических операций (как, например, про­блема остановки машины Тьюринга и не­которые другие, которые мы рассмотрим в главе 4). Если бы не было таких невы­числимых объектов, то теория алгоритми­ческой разрешимости не представляла бы особого интереса для математики. В кон­це концов, математики любят головоломки.

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

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

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

В рамках этой схемы рассматривается «универсальное множество» различных объ-

ектов, обозначаемых, скажем, символами

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

мы подразумеваем, что функция b, действуя на функцию c, дает в результате другую функцию a. В рамках этой схемы нетрудно сформулировать понятие функции двух или более переменных. Если мы хотим пред­ставить, как функцию двух переменных, скажем р и q, то мы можем просто написать

(что есть результат действия функции fp на функцию q). Для функции трех перемен­ных можно использовать выражение

и так далее.

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

мы подразумеваем функцию, которая при действии на, например, a имеет значение fa, т.е

Другими словами, - это просто функция f, т.е.

Сказанное выше требует определенного осмысления. Это одна из тех математичес­ких тонкостей, которые на первый взгляд кажутся настолько педантичными и триви­альными, что их смысл часто совершенно ускользает от понимания. Рассмотрим при­мер из знакомой всем школьной математи­ки. Примем за f тригонометрическую функ­цию — синус угла. Тогда абстрактная функ­ция «sin» будет определяться выражением

(Не придавайте большого значения тому, что в качестве «функции» х может фигу­рировать величина угла. Мы скоро увидим, каким образом числа можно иногда рассма­тривать как функции, а величина угла -это просто число.) До сих пор все на самом деле тривиально. Однако представим себе, что обозначение «sin» не было изобретено, но нам известно о существовании предста­вления sin x в форме степенного ряда:

Тогда мы могли бы ввести определение

Можно было поступить еще проще и опре­делить, например, операцию «одна шестая куба», для которой не существует стандарт­ного «функционального» обозначения:

Тогда, например,

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

Это функция, которая, действуя на другую функцию, скажем g, дает дважды итериро­ванную g, действующую на х

Мы могли бы сначала «абстрагироваться» от ж и рассмотреть выражение

которое можно сократить до

Это и есть операция, применение которой к gдает функцию «вторая итерацияg». По сути, это та самая функция, которую Черч обозначил номером 2:

так что (2g)y = g(gy)- Аналогичным обра­зом он определил:

а также

Видно, что 2 Черча больше похоже на «два­жды», 3 — на «трижды» и т.д. Значит, дей­ствие 3 на функцию f, т. е. 3f равносильно операции «применить f три раза», поэто­му 3f при действии на у превращается в

Посмотрим, как в схеме Черча можно представить очень простую математическую операцию — прибавление 1 к некоторому числу. Определим операцию

Чтобы убедиться, что 5 действительно при­бавляет 1 к числу в обозначениях Черча, проверим ее действие на 3:

поскольку (Зb)с = b(b(bс)). Очевидно, эта операция с таким же успехом может быть применена к любому другому натуральному числу Черча. (В действительности, операция Xabc.[(ab)(bc)} приводит к тому же результа­ту, что и 5.)

А как насчет удвоения числа? Удвое­ние числа может быть получено с помощью операции

что легко видеть на примере ее действия на 3:

Фактически, основные арифметические опе­рации — сложение, умножение и возведение в степень — могут быть определены, соот­ветственно, следующим образом:

Читатель может самостоятельно убедиться (или же принять на веру), что

где т и n — функции Черча для двух на­туральных чисел, m + n — функция, выра­жающая их сумму, и т. д. Последняя из этих функций поражает больше всего. Посмо­трим, например, что она дает в случае m = 2, n = 3

Операции вычитания и деления опре­деляются не так легко (на самом деле нам потребуется соглашение о том, что делать с (т - n), когда ига меньше и, и с (m/n), когда т не делится на n). Решающий шаг в развитии этого метода был сделан в начале 1930-х годов, когда Клини удалось найти вы­ражение для операции вычитания в рамках схемы Черча! Затем были описаны и дру­гие операции. Наконец, в 1937 году Черч и Тьюринг независимо друг от друга пока­зали, что всякая вычислимая (или алгорит­мическая) операция — теперь уже в смысле машин Тьюринга - может быть получе­на в терминах одного из выражений Черча (и наоборот).

Это воистину замечательный факт, ко­торый подчеркивает глубоко объективный и математичный характер понятия вычи­слимости. На первый взгляд, понятие вычи­слимости по Черчу не связано с вычисли­тельными машинами. И тем не менее, оно имеет непосредственное отношение к прак­тическим аспектам вычислений. В частно­сти, мощный и гибкий язык программиро­вания LISP включает в себя как существен­ный элемент основные структуры исчисле­ния Черча.

Как я отмечал ранее, существуют и дру­гие способы определения понятия вычи­слимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной маши­ны. Тогда же благодаря работам Дж. Хер-бранда и Геделя появилось и более прак­тичное определение вычислимости (рекур-сивности). X. Б. Карри в 1929 году, и ра­нее, в 1924, М. Шенфинкель, предложили иной подход, который был отчасти исполь­зован Черчем при создании своего исчисле­ния (см. Ганди [1988]). Современные под­ходы к проблеме вычислимости (такие как машина с неограниченным регистром, опи­санная Катлендом [1980]) в деталях значи­тельно отличаются от разработанного Тью­рингом и более пригодны для практичес­кого использования. Однако понятие вы­числимости во всех этих подходах остается неизменным.

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

Примечания

1. Я использую обычную современную терми­нологию, в которой множество «натураль­ных чисел» включает и нуль.

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

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

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

5. Эта процедура имеет отношение только к методу, который позволяет интерпретиро­вать запись на ленте как натуральное число. Она не изменяет номера наших конкретных машин Тьюринга, таких как EUC и XN + 1.

6. Если Т_n определена некорректно, то U будет действовать так, как если бы число, отвеча­ющее п, обрывалось сразу по достижении последовательности из четырех или более единиц в двоичной записи п. Остаток вы­ражения будет считан уже как число т, после чего устройство начнет совершать не­кие бессмысленные вычисления! От этого свойства можно при желании избавиться, если представлять п в расширенной двоич­ной форме. Я решил не делать этого, чтобы еще больше не усложнять описание несчаст­ной универсальной машины Тьюринга!

7. Я благодарен Давиду Дойчу за то, что он на­шел десятичную форму двоичного предста­вления и, которое я привожу ниже. Я при­знателен ему также за проверку того факта, что это двоичное значение и действитель­но задает универсальную машину Тьюрин­га! Пытливый читатель, вооруженный эффек­тивным домашним компьютером, быть мо­жет захочет проверить, используя данные в тексте предписания и применяя эту по­следовательность к номерам различных про­стых машин Тьюринга, что она и в самом деле соответствует универсальной машине Тьюринга!

Некоторое уменьшение величины и может быть достигнуто за счет другого определе­ния машины Тьюринга. Например, мы мог­ли бы отказаться от использования коман­ды STOP и вместо этого применять прави­ло остановки после того, как машина по­вторно возвращается во внутреннее состо­яние 0 из какого-либо другого внутренне­го состояния. Это не дало бы нам значи­тельного выигрыша (а может, и вовсе ни­какого). Большую пользу принесло бы ис­пользование лент с иными, нежели только 0 и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчи­ва, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.

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

9. Мы могли бы, конечно, «обыграть» и этот модифицированный алгоритм, просто за счет повторного применения предыдущей процедуры. Тогда мы сможем использовать эти вновь полученные знания для дальней­шего улучшения алгоритма, который мы, в свою очередь, снова превзойдем; и так далее. Тип рассуждений, в который выли­вается этот повторяющийся процесс, будет рассмотрен нами в связи с теоремой Геделя в главе 4.