Тени разума. В поисках науки о сознании

Еще одним примером класса вполне структурированных математических задач, не имеющих алгоритмического решения, является задача о замощении. Она формулируется следующим образом: дан набор многоугольников, требуется определить, покрывают ли они плоскость; иными словами, возможно ли покрыть всю евклидову плоскость только этими многоугольниками без зазоров и наложений? В 1966 году американский математик Роберт Бергер показал (причем эффективно), что эта задача вычислительными средствами неразрешима. В основу его доводов легло обобщение одной из работ американского математика китайского происхождения Хао Вана, опубликованной в 1961 году (см. [ 176]). Надо сказать, что в моей формулировке задача оказывается несколько более громоздкой, чем хотелось бы, так как многоугольные плитки описываются в общем случае с помощью вещественных чисел (чисел, выражаемых в виде бесконечных десятичных дробей), тогда как обычные алгоритмы способны оперировать только целыми числами. От этого неудобства можно избавиться, если в качестве рассматриваемых многоугольников выбрать плитки, состоящие из нескольких квадратов, примыкающих один к другому сторонами. Такие плитки называются полиомино(см. [ 161]; [ 136], глава 13; [ 222]). На рис. 1.2показаны некоторые плитки полиомино и примеры замощений ими плоскости. (Другие примеры замощений плоскости наборами плиток см. в НРК, с. 133-137, рис. 4.6-4.12.) Любопытно, что вычислительная неразрешимость задачи о замощении связана с существованием наборов полиомино, называемых апериодическими; такие наборы покрывают плоскость исключительно апериодически(т.е. так, что никакой участок законченного узора нигде не повторяется, независимо от площади покрытой плиткой плоскости). На рис. 1.3представлен апериодический набор из трех полиомино (полученный из набора, обнаруженного Робертом Амманом в 1977 году; см. [ 176], рис. 10.4.11-10.4.13 на с. 555-556).

Математические доказательства неразрешимости с помощью вычислительных методов десятой проблемы Гильберта и задачи о замощении весьма сложны, и я, разумеется, не стану и пытаться приводить их здесь ^{13}. Центральное место в каждом из этих доказательств отводится, в сущности, тому, чтобы показать, каким образом можно запрограммировать машину Тьюринга на решение задачи о диофантовых уравнениях или задачи о замощении. В результате все сводится к вопросу, который Тьюринг рассматривал еще в своем первоначальном исследовании: к вычислительной неразрешимости проблемы остановки— проблемы определения ситуаций, в которых работа машины Тьюринга не может завершиться. В §2.3мы приведем несколько примеров явных вычислительных процедур, которые принципиально не могутзавершиться, а в §2.5будет представлено достаточно простое доказательство — основанное, по большей части, на оригинальном доказательстве Тьюринга, — которое, помимо прочего, показывает, что проблема остановки действительно неразрешима вычислительными методами. (Что же касается следствий из того самого «прочего», ради которого, собственно, и затевалось упомянутое доказательство, то на них, в сущности, построены рассуждения всей первой части книги.)

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

Рис. 1.З. Набор из трех полиомино, покрывающий плоскость апериодически (получен из набора Роберта Аммана).