Новый ум короля: О компьютерах, мышлении и законах физики

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

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

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

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

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

f.[f (fx)]

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

x

(f.[f (fx)])g = g(gx).

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

f. [х. [f (fх)]],

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

fx. [f (fx)].

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

2 =  fx.[f (fx)],

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

3 = fx. [f (f (fx))],

4 = fх. [f (f (f (fx)))], и т. д.,

а также

1 = fх. [fх] и 0 = fx.

[x].

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

(3f)y = f (f (f (y)))-

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

S = abc. [b ((аb)с)].

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

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

аbс. [(аb)(bс)]приводит к тому же результату, что и S.)

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

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

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

А = fgxy. [((fx)(gx))y],

М = fgx. [f (gx)],

P = fg. [fg]

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

(Am) n = m + n,

(Mm) n = m x n

,

(Pm) n = n ^m,

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

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

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

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