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

Автор книги: Роджер Пенроуз

сообщить о нарушении

Текущая страница: 13 (всего у книги 47 страниц)

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

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

E _к.с. ω , x …, z [ f ( ω , x ,…, z ) = 0 ],

где f () – некоторая функция, построенная из обычных арифметических операций сложения, вычитания, умножения и возведения в степень, составляют рекурсивно нумеруемые множества [83]83
  Мы нумеруем множества { v , ω , x …., z ], где v представляет функцию f в согласии с некоторой лексикографической схемой. Мы (рекурсивно) проверяем на каждом этапе справедливость равенства f ( ω , x …, z ) = 0 и оставляем утверждение E _к.с. ω , х …., z [( ω , х …., z ) = 0 ] только в том случае, если это равенство выполняется.


[Закрыть](которые я обозначу через А ). Пример утверждения такого рода – хотя мы не знаем, верно ли оно – это отрицание последней теоремы Ферма [84]84
  Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. – Прим. ред.


[Закрыть]., для которой мы можем взять за f () функцию

f ( ω , х , у , z ) = ( х + 1 ) ^{ω + 3} + ( у + 1 ) ^{ω + 3} – ( z + 1 ) ^{ω + 3} .

Однако, множество А не является рекурсивным (факт, который не так легко установить, хотя он и вытекает из оригинального доказательства Геделя). Значит, мы не имеем никаких алгоритмических средств для выяснения – хотя бы в принципе – истинности или ложности последней теоремы Ферма.

Рис. 4.1.Очень схематичное представление рекурсивного множества

На рис. 4.1 я попытался схематически представить рекурсивное множество как фигуру с простой и изящной границей, так что кажется, что определить непосредственно принадлежность произвольной точки этому множеству – дело несложное. Каждая точка на рисунке соответствует некоторому натуральному числу. При этом дополнительное множество также представлено в виде просто выглядящей области на плоскости. На рис. 4.2 я постарался изобразить рекурсивно нумеруемое, но не рекурсивноемножество в виде области со сложной границей, где подразумевается, что множество с одной стороны границы, – той, что рекурсивно нумеруема – должно выглядеть проще, чем с другой.

Рис. 4.2.Очень схематичное представление рекурсивно нумеруемого множества (темная область), которое не является рекурсивным. Здесь светлая область определяется только по «остаточному принципу», когда удаляется темная часть, построенная при помощи вычислений; а установить путем прямых вычислений, принадлежит ли заданная точка белой области, нельзя

Фигуры очень схематичны и не претендуют на какую бы то ни было «геометрическую аккуратность». И конечно же, не стоит придавать большого значения тому, что эти рисунки изображены так, как если бы они были расположены на двумерной плоскости!

На рис. 4.3 я схематично обозначил, как расположены области Р , Т и А внутри множества N .

Рис. 4.3.Очень схематичное представление различных множеств утверждений. Множество Р утверждений, доказуемых в рамках системы, является, как и А , рекурсивно нумеруемым, но не рекурсивным. Множество Т истинных утверждений даже не рекурсивно нумеруемо

Является ли множество Мандельброта рекурсивным?

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

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

z  → z ² + с

сначала к z = 0 , чтобы получить с ; потом к z = с , чтобы получить с ² + с ; затем к z = с ² + с , чтобы получить с ⁴ + 2с ³ + с ² + с ; и так далее. Если эта последовательность 0 , с , с ² + с , с ⁴ + 2с ³ + с ² + с … остается ограниченной, то соответствующая точка с будет черной; в противном случае – белой. Как машина определяет, что такая последовательность остается ограниченной? В принципе, этот вопрос предполагает наличие информации о том, что происходит после бесконечногочисла ее элементов! Сама по себе эта задача вычислительными методами не решается. К счастью, существуют способы предсказать исходя уже из конечного числа членов, когда последовательность станет неограниченной. (На самом деле, если последовательность достигает окружности радиуса 1 + √2 с центром в начале координат, можно с уверенностью сказать, что она будет неограниченной.)

Таким образом, дополнениек множеству Мандельброта является, в некотором смысле, рекурсивно нумеруемым. Если комплексное число с расположено в светлой области, то существует алгоритм, подтверждающий этот факт. А как насчет самого множества Мандельброта – темного участка рисунка? Существует ли алгоритм, способный точно установить, что точка, принадлежащая предположительно темному участку, действительно ему принадлежит? Ответ на этот вопрос в настоящее время, похоже, отсутствует [85]85
  Недавно я узнал от Леоноры Блюм, что (заинтересовавшись моими комментариями в первом издании этой книги) она установила, что множество Мандельброта (и его дополнение) на самом деле являются, как я и предполагал, нерекурсивными в том смысле, который описан в десятом примечании.


[Закрыть]. Я справлялся у многих коллег и экспертов, но ни один из них не слышал о подобном алгоритме. Равно как и никто из них не сталкивался с указанием на то, что такого алгоритма не существует. По крайней мере, насколько можно об этом судить, алгоритм для темной области на сегодняшний день неизвестен. Возможно, множество, дополнительное по отношению к множеству Мандельброта, действительно является примером рекурсивно нумеруемого, но не рекурсивного множества!

Прежде чем исследовать дальше это предположение, необходимо будет обсудить некоторые моменты, которые я ранее опускал. Эти вопросы будут довольно важны для нас в дальнейших рассуждениях по поводу вычислимости в физике. Я хотел бы заметить, что, на самом деле, я был несколько неточен в предшествующем изложении. Я применял такие понятия, как «рекурсивно нумеруемый» и «рекурсивный», к множествам точек в плоскости Аргана, т. е. множествам комплексных чисел. Но эти термины могут применяться только лишь для натуральных чисел и других счетныхмножеств. Мы видели в третьей главе («Сколько же всего действительных чисел»), что действительные числа не могут быть счетным множеством, равно как, следовательно, и комплексные – ведь любое действительное число может быть рассмотрено как частный случай некоторого комплексного числа с нулевой мнимой частью (гл.3 «Комплексные числа»). В действительности существует такое же «количество» комплексных чисел, как и действительных, а именно « С». (Чтобы установить взаимнооднозначное соответствие между комплексными и действительными числами, можно, грубо говоря, просто взять действительную и мнимую части комплексного числа (записанные в десятичной форме) и перемешать через одну поразрядно цифры из мнимой части с цифрами из вещественной, образуя, тем самым, действительное число: тогда, например, 3,6781…+ i512,975… будет соответствовать действительному числу 50 132,6977851…)

Дабы избежать этой проблемы, можно было бы ограничиться только вычислимымикомплексными числами, так как мы еще в третьей главе видели, что вычислимые действительные числа – а значит, и соответствующие им комплексные – являются счетными. Однако здесь кроется одна принципиальная трудность: не существует алгоритма, с помощью которого можно было бы сравнивать два вычислимых числа, полученных алгоритмически! (Мы можем алгоритмическим образом составить их разность, но мы не в состоянии будем выяснить, равна она нулю или нет. Представьте себе два алгоритма, которые генерируют цифры 0,99999… и 1,00000…, соответственно; мы никогда не узнаем, продолжаются ли нули и девятки в них до бесконечности – так, что числа оказываются равными – или же где-то в дробной части того или другого числа могут появиться иные цифры, делая эти числа неравными.) Таким образом, мы, возможно, никогда не сможем определить, равны ли между собой такие числа. Как следствие этого – наша неспособность решить даже в таком простом случае как единичный круг в плоскости Аргана (множество точек, лежащих на расстоянии не большем единицы от начала координат – черная фигура на рис. 4.4), лежит ли комплексное число в этом круге или нет.

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

Трудность возникает не с точками, лежащими внутри или снаружи, а именно с точками на самой границе круга – то есть на самой единичной окружности. Эта окружность рассматривается по условию как часть круга. Предположим, что нам уже предоставлен в распоряжение алгоритм для получения цифр вещественной и мнимой частей некоторого комплексного числа. Если мы предполагаем, что это комплексное число лежит на единичной окружности, то мы не можем с необходимостью подтвердить этот факт. Не существует алгоритма, чтобы установить, является ли вычислимое число x ² + y ²  равным единице, что служит критерием для принадлежности комплексного числа х + iy данной единичной окружности.

Очевидно, это совсем не то, что нам нужно. Единичный круг, безусловно, долженрассматриваться как рекурсивное множество. Едва ли найдется сколь-нибудь значительное число множеств, более простых, чем единичный круг! Чтобы обойти эту проблему, одним из способов может быть игнорированиеграницы. Ведь для точек, лежащих внутри (или снаружи), безусловно существует алгоритм, устанавливающий этот факт. (Можно просто последовательно генерировать цифры числа х ² + у ² , и, в конце концов, мы найдем цифру, отличную от 9 в дробной части 0,9999… или отличную от 0 – в дробной части 1,00000…) В этом смысле единичный круг является рекурсивным. Но этот подход чрезвычайно неудобен для математики, поскольку там часто возникает необходимость ссылаться в рассуждениях на то, что происходит именнона границах. С другой стороны, вполне возможно, что такая точка зрения окажется применимой в области физики. Позднее нам еще придется вернуться к этому вопросу.

Существует другой метод, имеющий непосредственное отношение к данному вопросу, который не предполагает вообще обращения к вычислимым комплексным числам. Вместо того, чтобы пытаться пронумеровать комплексные числа внутри или снаружи рассматриваемого множества, мы просто будем вызывать алгоритм, который для любого наперед заданногокомплексного числа будет определять, принадлежит оно нашему множеству или же его дополнению. Говоря «наперед заданный», я подразумеваю, что для каждого числа, которое мы рассматриваем, нам некоторым – быть может, «волшебным» – образом известны цифры мнимой и вещественной части, одна за другой, и в таком количестве, сколько нам нужно. Я не требую, чтобы существовал алгоритм, известный или неизвестный, для нахожденияэтих цифр. Множество комплексных чисел считалось бы «рекурсивно нумеруемым», если бы существовал хотя бы единственный алгоритм такой, что для любой заданной ему вышеуказанным образом последовательности цифр он бы говорил «да» после конечного числа шагов тогда и только тогда, когда комплексное число действительно принадлежит этому множеству. Оказывается, что как и в случае подхода, предложенного выше, эта точка зрение также «игнорирует» границы. Следовательно, внутренняя и внешняя области единичного диска будут каждая по отдельности считаться рекурсивно нумеруемыми в указанном смысле, тогда как сама граница – нет.

Для меня совершенно не очевидно, что какой-либо из этих методов дает то, что нам нужно [86]86
  Блюмом, Шубом и Смэйлом [1989] была разработана новая теория вычислимости для действительных функций от действительных переменных (в отличие от общепринятых функций натуральных чисел, принимающих натуральные значения), подробности которой я узнал лишь совсем недавно. Эта теория применима и к комплексным функциям, а кроме того, может сыграть заметную роль в упомянутых мной вопросах.


[Закрыть]. Философия «игнорирования границ», будучи приложенной к множеству Мандельброта, может привести к потере большого числа тонких моментов. Одна часть этого множества состоит из «клякс» – внутренних областей, а другая – из «усиков». Наибольшие сложности при этом связаны, видимо, с «усиками», которые могут «извиваться» самым причудливым образом. Однако, «усики» не принадлежат внутренней части множества, и, тем самым, они были бы проигнорированы, используй мы любой из двух вышеприведенных подходов. Но даже при таком допущении остается неясность, можно ли считать множество Мандельброта рекурсивным в том случае, когда рассматриваются только «кляксы». Похоже, что вопрос этот связан с некоторым недоказанным предположением, касающимся самого множества, а именно: является ли оно, что называется, «локально связным»? Я не собираюсь здесь разбирать значение этого понятия или его важность для данного вопроса. Я хочу просто показать, что существует ряд трудностей, которые вызывают неразрешенные на сегодняшний день вопросы, касающиеся множества Мандельброта, чье решение – первоочередная задача для некоторых современных математических исследований.

Существуют также и другие подходы, которые могут использоваться с тем, чтобы обойти проблему несчетности комплексных чисел. Вместо того, чтобы рассматривать все вычислимые комплексные числа, можно ограничиться только подмножеством таких чисел, для любой пары которых можно вычислительным путем установить их равенство. Простым примером такого подмножества могут служить «рациональные»комплексные числа, у которых как мнимая, так и вещественная части могут быть представлены рациональными числами. Я не думаю, однако, что это дало бы многое в случае «усиков» множества Мандельброта, поскольку такая точка зрения накладывает очень значительные ограничения. Более удовлетворительным могло бы оказаться рассмотрение алгебраическихчисел – тех комплексных чисел, которые являются алгебраическими решениями уравнений с целыми коэффициентами. Например, все решения z уравнения

129z ⁷ – ЗЗz ⁵ + 725z ⁴ + 16z ³ – 2z – 3 = 0

– это алгебраические числа. Такие числа будут счетными и вычислимыми, и задача проверки двух из них на равенство будет решатся путем прямого вычисления. (Как выясняется, многие из них будут лежать на границе единичного круга и «усиков» множества Мандельброта.) И мы можем по желанию рассматривать вопрос о рекурсивности множества Мандельброта в терминах этих чисел.

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

y ≥ e ^z ,

где х + iy (= z ) – точка в плоскости Аргана.

Рис. 4.5.Множество, определенное экспоненциальным соотношением у ≥ е ^z , должно также рассматриваться как рекурсивное

Внутренняя часть множества, равно как и внутренняя часть его дополнения, будут рекурсивно нумеруемыми в соответствии с любой из вышеизложенных точек зрения, но (как следует из знаменитой теоремы Ф.Линдеманна, доказанной в 1882 году) граница, у = е ^х , содержит только одну алгебраическую точку, а именно точку z  = i . В этом случае алгебраические числа никак не могут нам помочь при исследовании алгоритмической по своей природе границы!

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

Некоторые примеры нерекурсивной математики

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

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

z ³ – y – 1= 0,

yz ²– 2x– 2 = 0,

у ²– 2xz + z + 2 = 0,

и задача состоит в том, чтобы определить, могут ли они быть решены в целых x , y , z . Оказывается, что в этом конкретном случае существует тройка целых чисел, дающая решение этой системы:

х = 13, у = 7, 2 = 2.

Но для произвольной системы диофантовых уравнений никакого алгоритма не существует [87]87
  Это дает (отрицательный) ответ на десятую проблему Гильберта, упомянутую на с. 44 (см., например, Дэвлин [1988]). Здесь количество переменных неограниченно. Однако, известно, что для выполнения свойства неалгоритмичности достаточно и девяти.


[Закрыть]. Арифметика Диофанта, несмотря на простоту входящих в нее выражений, является частью неалгоритмической математики!

(Несколько менее тривиальным является пример топологической эквивалентностимногообразий. Я упоминаю об этом только вкратце, ибо в главе 8 будут рассматриваться вопросы, имеющие к данному определенное отношение. Чтобы понять, что такое «многообразие», представьте для начала петлю, которая является многообразием в одном измерении; затем представьте замкнутую поверхность – многообразие в двух измерениях. Далее попробуйте представить некую «поверхность», имеющую три и более измерений. «Топологическая эквивалентность» двух многообразий означает, что одно из них может быть деформировано в другое путем непрерывных преобразований – без разрывов и склеек. Так, сфера и поверхность куба являются топологически эквивалентными, хотя они не эквивалентны поверхности кольца или чашки с ручкой – хотя последние топологически эквивалентны друг другу. При этом для двумерныхмногообразий существует алгоритм, позволяющий определить, эквивалентны ли произвольные два многообразия друг другу или нет – в сущности, заключающийся в подсчете «ручек», которые имеет каждая из поверхностей. Для случая трех измерений вопрос о существовании такого алгоритма на момент написания книги остается без ответа; однако для четырех и более измерений уже известно, что такого алгоритма быть не может . Возможно, четырехмерный случай имеет некое отношение к физике, поскольку согласно теории общей относительности Эйнштейна пространство и время совместно образуют четырехмерное многообразие (см. главу 5, «Специальная теория относительности Эйнштейна и Пуанкаре»). Герох и Хартли в 1986 году высказали предположение о том, что свойство неалгоритмичности может иметь отношение к «квантовой гравитации» (см. также главу 8).)

Давайте теперь рассмотрим иной тип задач, называемых задачами со словами [88]88
  Эта конкретная задача называется (если быть более точным) «задачей со словами для полугрупп». Существуют также и другие разновидности этой задачи, в которых действуют несколько отличные правила. Но нас это сейчас волновать не должно.


[Закрыть]. Допустим, у нас есть некий алфавит символов, и мы рассматриваем различные строки этих символов, трактуя их как слова . Слова могут сами по себе не иметь никакого значения, но мы должны иметь некоторый (конечный) список «равенств» между ними, которые мы сможем использовать для дальнейшего построения таких «равенств». Это делается путем подстановки слов из исходного списка в другие (как правило, более длинные) слова, которые содержат их в виде составных частей. Каждая такая часть может быть заменена на равную ей в соответствии с используемым списком. Тогда для любой данной пары слов мы должны решить задачу об их равенстве согласно этим правилам.

В качестве примера мы можем взять для нашего исходного списка, скажем, такие равенства:

EAT = АТ

АТЕ = А

LATER = LOW

PAN = PILLOW

CARP = ME.

Отсюда мы можем, например, вывести

LAP = LEAP,

используя последовательные замены из второго, первого и снова второго соотношения из нашего исходного листа:

LAP = LATEP = LEATEP = LEAP.

Проблема теперь заключается в том, чтобы выяснить, сможем ли мы для любой наперед заданной пары слов осуществить вышеописанным образом переход от одного из них к другому? Можем мы перейти от CATERPILLAR к MAN, или, скажем, от CARPET – к MEAT? Ответ в первом случае оказывается утвердительным, тогда как во втором – отрицательным. Когда ответ утвердителен, стандартный путь показать его справедливость заключается в построении цепочки равенств, где каждое из слов получается из предыдущего с учетом допустимых соотношений. Итак, имеем (обозначая буквы, назначенные к замене, жирным шрифтом, а только что измененные – курсивом):

Как мы можем утверждать, что посредством разрешенных подстановок невозможно получить MEAT из CARPET? Для демонстрации этого факта придется подумать чуть больше, однако показать это не так уж сложно, причем множеством разных способов. Простейшим представляется следующий: в каждом «равенстве» из нашего списка число букв Аплюс число букв Wплюс число букв Мс каждой стороны одинаково. Значит, общая сумма указанных букв не может меняться в процессе преобразования по допустимым нашим списком правилам. Однако, для CARPETэта сумма равна 1 , а для MEAT– 2 . Следовательно, не существует способа получить из первого слова второе при помощи вышеприведенного списка равенств.

Заметьте, что когда два слова «равны», мы можем показать это, просто приведя допустимую формальную строчку символов, построенную с помощью заданных нами правил; тогда как в случае их «неравенства» мы должны прибегать к рассуждениям об этих самых правилах. Существует четкий алгоритм, который мы можем использовать для установления «равенства» между двумя словами в том случае, когда они действительно «равны». Все, что нам требуется, это составить лексикографический перечень всех возможных последовательностей слов, и потом вычеркнуть из этого списка любую строчку, где имеется пара слов, в которой последующее нельзя получить из предыдущего при помощи какого бы то ни было правила из исходного списка. Оставшиеся последовательности дадут нам набор всех искомых «равенств» между словами. Однако, в общем случае нет такого явного алгоритма для случая, когда два слова «неравны», и нам, возможно, пришлось бы применить «интеллект» для установления этого факта. (Конечно же, мне потребовалось некоторое время, прежде чем я заметил описанный выше «трюк», при помощи которого доказал, что CARPETи MEAT«неравны». А для другого примера «трюк» мог бы понадобиться совершенно иной. Кстати, интеллект помогает – хотя и не обязательно – и в случае, когда необходимо установить существованиенекоторого «равенства».)

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

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

АН = НА

ОН = НО

АТ = ТА

ОТ = ТО

TAI = IT

HOI = IH

THAT = ITHT.

(Этот список взят из списка, предложенного Григорием Цейтиным и Даной Скотт в 1955 году (см. Гарднер [1958]).) Таким образом, эта частная задача со словами служит примером нерекурсивной математики в том смысле, что, используя такой исходный список, мы не можем алгоритмическим путем решить, «равны» два наперед заданных слова или нет.

Общая задача со словами возникает как следствие рассмотрения формализованной математической логики («формальных систем» и т. п., в соответствии с обсуждаемым ранее). Исходный список выполняет роль системы аксиом, а правила замены слов – правил вывода. Доказательство нерекурсивности задачи со словами вытекает из подобных рассуждений.

В качестве последнего примера задачи из области нерекурсивной математики давайте рассмотрим вопрос о покрытии Евклидовой плоскости многоугольниками, разнообразие форм которых ограничено, а сам вопрос при этом ставится так: можем ли мы выложить всю плоскость полностью, без разрывов и нахлестов, используя фигуры только данных нам форм? Такая укладка фигур называется замощениемплоскости. Мы знаем, что такое замощение возможно при помощи только квадратов, только равнобедренных треугольников или только правильными шестиугольниками (как изображено на рис. 10.2 гл. 10 «Плиточные» структуры и квазикристалы»), но невозможно, если использовать только правильные пятиугольники. Многими иными фигурами, такими, как два неправильныхпятиугольника на рис. 4.6, также можно выложить плоскость.

 

Рис. 4.6.Два примера периодического замощения плоскости фигурой одной формы (предложены Марджори Райе (Marjorie Rice) в 1976 году)

Замощение фигурами двух форм может стать более хитроумной задачей. Два простых примера даны на рис. 4.7.

Рис. 4.7.Два примера периодического замощения плоскости фигурами двух форм

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

Рис. 4.8.Периодическое замощение и его параллелограмм периодов

С другой стороны, существует множество типов замощений плоскости, которые не являются периодическими.

Рис. 4.9 изображает три непериодических «спиральных» замощения из таких же шиповидных «плиток», как и на рис. 4.8.

Рис. 4.9.Три непериодических «спиральных» замощения из таких же «универсальных» плиток, как и на рис. 4.8

Эта форма «плиток», известная как «универсальная» (по вполне понятным причинам!), была предложена Б. Грюнбаумом и Дж. К. Шепардом [1981, 1987] на основании форм, изученных X. Фодербергом. Обратите внимание, что универсальная форма позволяет замостить плоскость как периодически, так и непериодически. Это свойство характерно и для многих других форм единичных «плиток» и наборов «плиток». А могут ли существовать «плитки» (или конечные наборы «плиток»), которые бы покрывали плоскость тольконепериодически? Ответ на этот вопрос будет «да». На рис. 4.10 я изобразил сконструированный американским математиком Рафаэлем Робинсоном набор из фигур шести различных форм, которым можно замостить всю плоскость, но только непериодическим образом.

Рис. 4.10.Набор Рафаэля Робинсона из шести плиток, который покрывает плоскость только непериодически

Небесполезно было бы сделать историческое отступление и посмотреть, как появился это непериодический набор (см. Грюнбаум, Шепард [1987]). В 1961 году американский логик китайского происхождения Хао Ванг поставил вопрос о существовании процедуры для решения задачи замощения, или, иными словами, о нахождении алгоритма, который позволил бы выяснить возможность замощения всей плоскости с помощью конечного набора многоугольников различной формы! [89]89
  В действительности Хао Ванг занимался несколько иной проблемой – с квадратными «плитками», не вращаемыми и с совпадающими по цвету сторонами, – но эти особенности для нас здесь не важны.


[Закрыть]Ему удалось показать, что такая процедура могла бы существовать, если бы получилось доказать следующую гипотезу: любой конечный набор разных «плиток», с помощью которого можно каким-нибудь способом выполнить замощение плоскости, пригоден также и для ее периодического замощения. Мне думается, в то время интуитивно казалось, что не может существовать набор «плиток», нарушающий это условие (т. е. не может существовать «непериодический» набор плиток). Однако в 1966 году, следуя в указанном Хао Вангом направлении, Роберт Бергер смог показать, что, на самом деле, процедуры решения задачи покрытия не существует: эта задача также принадлежит области нерекурсивной математики! [90]90
  Более того, Ханф [1974] и Майерс [1974] показали, что существует отдельное множество (из большого числа «плиток»), которое покрывает плоскость только невычислимым образом.


[Закрыть]

С учетом доказанного Хао Вангом это означало, что хотя бы один непериодический набор «плиток» должен существовать; и Бергер смог построить первый такой набор. Однако, из-за сложности выбранного им способа рассуждений, его набор состоял из ненормально большого числа «плиток» разной формы – изначально их насчитывалось 20 426. Использовав некоторый дополнительный искусный прием, Бергеру удалось сократить это число до 104. А в 1971 году Рафаэль Робинсон довел его до шести, которые изображены на рис. 4.10 выше.

Другой непериодический набор из шести «плиток» представлен на рис. 4.11. Это множество я придумал сам в 1973 году, следуя в своих рассуждениях несколько отличным путем. (Я вернусь к этой теме в главе 10 «Плиточные структуры и квазикристаллы», где на рис. 10.3, изображен массив, покрытый такими «плитками».)

Рис. 4.11.Другой набор из шести плиток, который покрывает плоскость только непериодически

После того, как, я познакомился с «шестиплиточным» набором Робинсона, я начал думать о том, как сократить их число; и путем различных манипуляций с разрезаниями и склеиванием я, в конечном счете, смог довести количество «плиток» до двух. Две альтернативные схемы представлены на рис. 4.12.

Рис. 4.12.Две пары плиток, которые покрывают плоскость только непериодически («плитки Пенроуза»). Также показано замощение плоскости каждой из этих пар

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

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

Задача замощения, в том виде, как она исследовалась Вангом, Бергером и Робинсоном, формулируется для «плиток», построенных на квадратах. Я же здесь допускаю рассмотрение многоугольников произвольной формы, и поэтому необходимо наличие какого-нибудь способа изображения каждой из «плиток», поддающегося адекватному вычислению. Одним из таких путей могло бы быть представление вершин «плиток» точками плоскости Аргана, которые превосходно задаются алгебраическими числами.