Невозможность алгоритмического решения задачи замощения ячейками Пенроуза

         Я, разумеется, не собираюсь  приводить подробности доказательства Лагранжа, вместо этого рассмотрим одну не в пример более простую задачу:

         (C)       Найти нечетное число, являющееся суммой двух четных чисел.

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

         0,2,4,6,8,10,12,14,16,...,

         всегда получаются четные же числа; иными словами, никакая  пара четных чисел не может дать в сумме нечетное число, т. е. число  вида

         1,3,5,7,9, 11, 13, 15,17,....

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

         (D)       Найти четное число, большее 2, не являющееся суммой двух простых чисел.

         Вспомним, что простым  называется натуральное число (отличное от 0 и 1), которое делится без остатка  лишь само на себя и на единицу; иными словами, простые числа составляют следующий ряд:

         2, 3, 5, 7, 11, 13, 17, 19, 23, ....

         Существует довольно высокая вероятность того, что  отыскание решения задачи (D) также потребует незавершающейся вычислительной процедуры, однако полной уверенности пока нет. Для получения такой уверенности необходимо прежде доказать истинность знаменитой «гипотезы Гольдбаха», выдвинутой Гольдбахом в письме к Эйлеру еще в 1742 году и до сих пор недоказанной.

         Так каким же образом можно применить такой класс задач, как задачи о замощении, к созданию "игрушечной" вселенной, которая, будучи детерминированной, является, тем не менее, невычислимой? Допустим, что в нашей модели вселенной течет дискретное время, параметризованное натуральными (т.е. целыми неотрицательными) числами. Предположим, что в некий момент времени p состояние вселенной точно определяется одной задачей из рассматриваемого класса, скажем, набором полиомино. Необходимо установить два вполне определенных правила относительно того, какой из наборов полиомино будет представлять состояние вселенной в момент времени при заданном наборе полиомино для состояния вселенной в момент времени n, причем первое из этих правил применяется в том случае, если полиомино покрывают всю плоскость без зазоров и наложений, а второе если это не так. То, как именно будут выглядеть подобные правила, не имеет в данном случае особого значения. Можно составить список всех возможных наборов полиомино таким образом, чтобы наборы, содержащие в общей сложности четное число квадратов, имели бы четные индексы, а наборы с нечетным количеством квадратов нечетные индексы (Составление такого списка не представляет особой сложности; нужно лишь подобрать соответствующую вычислительную процедуру.) Итак, "динамическая эволюция" нашей игрушечной вселенной задается теперь следующим условием:

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

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

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

          Для чего вообще нужны непериодические мозаики, спросите вы? Неужели только для  игр и головоломок? Нет. В 1984 году сотрудники НИСТ США сделали сенсационное открытие, обнаружив непериодическую структуру на электронограмме быстро охлажденного сплава марганца и алюминия. Расположение рефлексов – светлых пятен – на снимке обладало осью симметрии 5-го порядка, что с математической точки зрения убедительно свидетельствовало о существовании непериодического пространственного расположения атомов, аналогичного мозаике Пенроуза.

         Это открытие было чрезвычайно  сильным ударом по фундаментальным  догмам кристаллографии, где долгое время господствовало утверждение, что кристаллы могут обладать лишь осями симметрии 2-го, 3-го, 4-го и 6-го порядка, но никак не 5-го. Согласно другой догме, твердое вещество могло существовать только в двух формах: либо с регулярной периодической решеткой атомов в кристалле, либо в хаотическом беспорядке атомов аморфных тел, как в стекле, к примеру. Открытие кристаллов с непериодической «квазисимметричной» структурой означает, что между аморфными телами и периодическими кристаллами имеется не четкое разграничение, как казалось долгое время, а плавный переход.

         Но означает это  и нечто значительно большее. В частности, для понимания природы  человеческого сознания, способного предсказывать вещи, противоречащие повседневному опыту и не вычисляемые  с помощью компьютера. 

     Новые открытия

          Двое ученых из Университета Дьюка (США) предложили свой вариант непериодичной мозаики, полностью покрывающей плоскость, в котором используются плитки одной формы  — правильного шестиугольника (см. рисунок). При укладке таких плиток черные линии не должны прерываться, а флажки в вершинах шестиугольников, которые находятся на расстоянии, равном длине одной стороны плитки (на рисунке отмечены стрелками), должны смотреть в одну сторону. Ученые использовали, строго говоря, две различные раскраски: вторая получается при отражении первой относительно вертикальной линии. Без второго варианта раскраски, впрочем, можно обойтись, если плитку сделать трехмерной. Замощение плоскости такими плитками показано на одном из расположенных ниже рисунков; для удобства представления те флажки на шестиугольниках, которые смотрят влево, заменены здесь фиолетовыми линиями, а флажки другого типа — красными линиями.

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

          Примеры непериодических  замощений