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

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

на обложку

Пенроуз Роджер

Шрифт:

x . [ fx ],

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

( х . [ fx ]) a = fа .

Другими словами, х . [ fх ] —

это просто функция f , т. е.

х . [ fх ] = f .

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

х . [ sin х ] = sin .

(Не придавайте большого значения тому, что в качестве «функции» х может фигурировать величина угла. Мы скоро увидим, каким образом числа можно иногда рассматривать как функции, а величина угла — это просто число.) До сих пор все на самом делетривиально. Однако представим себе, что обозначение «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 .)

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