1.9. Невычислительные процессы

63

Зазор

Зазор

Рис. 1.2. Плитки полиомино и замощения ими бесконечной евклидовой плоскости (допускается использование зеркально отраженных плиток). Если брать полиомино из набора (с) по отдельности, то ни одно из них не покроет всю плоскость.

64

Глава I

Рис. 1.3. Набор из трех полиомино, покрывающий

плоскость апериодически (получен из набора Роберта

Аммана).

1.9. Невычислительные процессы 65

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

квадратов - нечетные индексы (Составление

такого списка не представляет особой сложности; нужно лишь подобрать соответствующую вычислительную процедуру.) Итак, "динамическая эволюция" нашей игрушечной вселенной задается теперь следующим условием:

Из состояния в момент времени t вселенная переходит в момент времени t + I в состояние , если набор полиомино покрывает плоскость, и в состояние , если набор не покрывает плоскость.

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

Безусловно, такую схему нельзя воспринимать хоть сколько-нибудь всерьез - она ни в коем случае не моделирует реальную вселенную, в которой все мы живем. Эта схема приводится здесь (как, собственно, и в НРК, с. 170) для иллюстрации того часто недооцениваемого факта, что между детерминизмом и вычислимостью существует вполне определенная разница. Некоторые полностью детерминированные модели вселенной с четкими законами эволюции невозможно реализовать вычислительными средствами. Вообще говоря, как мы убедимся в § 7.9, только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки эре-

66

Глава I

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

ния . Что же касается тех феноменов, которые отвечают-таки этим самым реальным требованиям, и некоторых связанных с упомянутыми феноменами поразительных физических возможностях, то о них мы поговорим в § 7.10.