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

         ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

         Нижегородский государственный  технический университет

          имени Р. Е. Алексеева

         Кафедра «Прикладная  математика» 
 

          КУРСОВАЯ РАБОТА

                 ДИСЦИПЛИНА: «Теория компиляции» 

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

                                                                         Выполнила: студентка 2 курса

                                                                         дневного отделения гр. 08-ПМ

                                                                        Барзёнок Ольга Игоревна

                                                                         Проверил: Ковригин Дмитрий

                                                                         Анатольевич 
 
 

         Нижний Новгород

         2010 год

          Замощение – это покрытие всей плоскости неперекрывающимися фигурами.  Вероятно, впервые интерес к замощению возник в связи с построением мозаик, орнаментов и других узоров. Известно много орнаментов, составленных из повторяющихся мотивов. Одно из простейших замощений приведено на рисунке справа. Плоскость покрыта параллелограммами, причем все параллелограммы одинаковы. Любой параллелограмм этого замощения можно получить из розового параллелограмма, сдвигая последний на вектор   (векторы и определяются ребрами выделенного параллелограмма, n и m – целые числа). Следует заметить, что всё замощение как целое переходит в себя при сдвиге на вектор (или ).  Это свойство можно взять в качестве определения: именно, периодическим замощением с периодами и    назовём такое замощение, которое переходит в себя при сдвиге на вектор  и на вектор . Периодические замощения могут быть и весьма замысловатыми, некоторые из них очень красивы.

         Как известно, плотное  заполнение плоскости может быть осуществлено с помощью треугольников (Рис.1а), квадратов (Рис.1б) и шестиугольников (Рис.1г). С помощью пятиугольников (пентагонов) такое заполнение невозможно (Рис.1в).

                 а)                б)                       в)                г)                                                  

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

         Но это речь шла  о периодичеких  мозаиках. Нас  же интересуют непериодические.

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

         На протяжении многих десятилетий специалисты полагали, что таких наборов не существует, но их мнение оказалось неверным. В 1961 г. Хао Ван заинтересовался задачей о замощении плоскости множествами единичных квадратов, стороны которых раскрашены по-разному. Такие множества получили название "Домино Вана". Задачу, которую поставил Ван, можно сформулировать так: найти процедуру, позволяющую для любого набора домино решать, можно ли из него простроить мозаику, если домино укладывать так, чтобы смежные ребра были одного цвета. Поворачивать домино или заменять их зеркальными отражениями не разрешается. Поставленная Ваном задача важна потому, что связана с проблемой разрешимости в математической логике. Ван предположил, что любой набор домино, которым можно замостить плоскость, позволяет построить периодическую мозаику, и показал, что если его гипотеза верна, что для задачи о построении мозаики существует решающая процедура.

          В 1964 г. Роберт Берджер в своей докторской диссертации  по прикладной математике, представленной Гарвардскому университету, показал, что гипотеза Вана неверна. Общей решающей процедуры не существует. Это означает, что существует какой-то набор домино Вана, из которых можно построить только непериодическую мозаику. Берджер построил такой набор из более чем    20000 домино. Впоследствии ему удалось найти меньший набор, состоящий из 104 домино, а Доналду Кнуту удалось уменьшить число домино в наборе до 92.

         Каждый такой набор  домино Вана нетрудно превраить в  многоугольные фигуры, из которых  можно строить только непериодические мозаики. Для этого нужно просто снабдить соприкасающиеся стороны домино, уложенных в мозаику, точно подогнанными друг к другу выступами ("шипами") и впадинами ("пазами"). Соответствие шипов и пазов заменяет прежнее условие совпадения цветов примыкающих друг к другу сторон домино. Согласно прежнему условию примыкающие стороны должны быть одного цвета. Это условие должно соблюдаться для всех цветов. Допуская повороты и отражения элементарных областей, Робинсон построил 6 фигур (см рис. 2) допускающих в указанном смысле построение непериодической мозаики. В 1977 г. Роберт Амманн обнаружил другой набор из 6 фигур, из которых также можно сложить непериодическую мозаику. Неизвестно, можно ли сложить из фигур такого квадратного типа мозаику, если число их меньше 6. Имеются веские основания предполагать, что число 6 минимально.

          Роузболловскому профессору математики Оксфордского университета Пенроузу удалось найти меньшие  наборы фигур неквадратного типа, из которых можно построить непериодическую  мозаику. Работая в основном в области теории относительности и квантовой механики, Пенроуз проявляет активный интерес к занимательной математике. Это - фамильная черта Пенроузов: отец Роджера - генетик Л.С. Пенроуз также был любителем занимательной математики. В 1973 г. Роджер Пенроуз обнаружил набор из 6 фигур, из которых можно построить непериодическую мозаику. Вскоре ему удалось сократить число фигур до двух.

          Форма двух основных фигур Пегроуза может быть различной, но наиболее интересна пара фигур, которые  Конуэй назвал "наконечником дротика" и "воздушным змеем". На рис.3 показано, как построить наконечник и змей из ромба с углами в 72^о и 108^о. Разделим длинную часть ромба в отношении, равном хорошо известному золотому сечению (1 + 5^½)/2 = 1,61803398… , и соединим точку деления с вершинами тупых углов. Вот и все. Пусть φ - золотое сечение. Тогда каждый прямолинейный отрезок - сторона наконечника или змея - имеет длину, равную либо 1, либо φ. Наименьший угол равен 36^о. Все остальные углы кратны ему.

         Разумеется, ромбом с внутренними углами в 72^о и 108^о можно выложить периодически всю плоскость, но складывать наконечники и змеи  так, чтобы они образовали ромб, не разрешается.  Избежать запретных вариантов соединяя фигуры мы можем, снабжая стороны наконечников и змеев соответствующими  шипами и пазами, но той же цели можно достичь и проще. Например, вершины фигур можно обозначить буквами H и T так, как это показано на рисунке 3Б, и ввести правило, по которому при подгонке сторон разрешается совмещать только вершины, помеченные одинаковыми буквами. Вершины для облегчения составления мозаики можно пометить точками двух различных цветов (один цвет соответствует букве Н, другой - букве Т), но Конуэй предложил более изящный метод - проводить на каждый фигуре дуги окружностей двух цветов (на рисунке 3 эти дуги изображены чёрным и серым цветом). Каждая такая дуга делит стороны фигур, а также оси симметрии на части, длины которых образуют золотое сечение. Правило построения мозаики состоит в том, что при совмещении сторон должны соединяться дуги одного цвета.

         Чтобы в полной мере оценить красоту и загадочность мозаики Пенроуза, необходимо изготовить набор, состоящий по меньшей мере из 100 змеев и 60 наконечников. Число змеев находится к числу наконечников (так же, как площадь змея к площади наконечника) в отношении, равном золотому сечению. Вам могло показаться, что меньших по размерам наконечников потребуется больше, чем змеев, но в действительности дело обстоит иначе: змеев в мозаике оказывается в 1,618... больше, чем наконечников. В бесконечной мозаике отношение числа змеев к числу наконечников в точности равно золотому сечению. Иррациональность этого отношения лежит в основе данного Пенроузом доказательства непериодичности его мозаики, так как если бы мозаика была периодической, то отношение числа змеев к числу наконечников было бы рациональным.

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

         Незавершающиеся вычисления

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

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

         Под «числом» в данном случае я подразумеваю «натуральное число», т. е. число из ряда

         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, .... 

         Под квадратом числа понимается результат умножения натурального числа на само себя, т. е. число из ряда 

         0, 1, 4, 9, 16, 25, 36, ...;

         представленные в  этом ряду числа получены следующим  образом:

         0 х 0 = 0²,    1 х 1 = 1²,    2 х 2 = 2²,    3 х 3 = 3²,    4 х 4 = 4²,    5х5 = 5²,    6 х 6 = 6²,....

         Такие числа называются «квадратами», поскольку их можно представить в виде квадратных матриц (пустой матрицей в начале строки обозначен 0):

         С учетом вышесказанного решение задачи (А) может происходить следующим образом. Мы поочередно проверяем каждое натуральное число, начиная с 0, на предмет того, не является ли оно суммой трех квадратов. При этом, разумеется, рассматриваются только те квадраты, величина которых не превышает самого числа. Таким образом, для каждого натурального числа необходимо проверить некоторое конечное количество квадратов. Отыскав тройку квадратов, составляющих в сумме данное число, переходим к следующему натуральному числу и снова ищем среди квадратов (не превышающих по величине рассматриваемое число) такие три, которые дают в сумме это самое число. Вычисление завершается лишь тогда, когда мы находим натуральное число, которое невозможно получить путем сложения любых трех квадратов. Попробуем применить описанную процедуру на практике и начнем наше вычисление с нуля. Ноль равен 0² + 0² + 0², что, безусловно, является суммой трех квадратов. Далее рассматриваем единицу и находим, что она не равна О² + О² + О², однако равна О² + О² + I². Переходим к числу 2 и выясняем, что оно не равно ни 0² + 0² + 0², ни 0² + 0² + 1², но равно0² + 1² + 1². Затем следует число 3 и сумма 3 = 1² + 1² + 1²; далее — число 4 и сумма 4 = 0² + 0² + 2²; после 5 = 0² + 1² + 2² и 6 = 1²+1²+2² переходим к 7, и тут обнаруживается, что ни одна из троек квадратов (всех возможных троек квадратов, каждый из которых не превышает 7)

         0²+0²+0²    0²+0²+1²    0²+0²+2²    0²+1²+1²    0²+1²+2²

         0²+2²+2²    1²+1²+1²    1²+1²+2²    1²+2²+1²    2²+2²+2²

         не дает в сумме 7. На этом этапе вычисление завершается, а мы делаем вывод: 7 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.

         Будем считать, что  с задачей (А) нам просто повезло. Попробуем решить еще одну:

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

         На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне возможно: 7 = 1² + 1² + 1² + 2², поэтому мы переходим к числу 8 (сумма 8 = 0² + 0² + 2² + 2²), далее — 9 (сумма 9 = 0² + 0² + 0² + З²) и 10 (10 = 0² + 0² + 1² + 3²) и т.д. Вычисления все продолжаются и продолжаются (. . . 23 = 1² + 2² + 3² + 3², 24 = 0² + 2² + 2² + 4², . . . , 359 = 1² + 3² + 5² + 18², . . .) и завершаться, похоже, не собираются. Мы предполагаем, что искомое число, должно быть, невообразимо велико, и для его вычисления нашему компьютеру потребуется чрезвычайно большой промежуток времени и огромный объем памяти. Более того, мы уже начинаем сомневаться, существует ли оно вообще, это самое число. Вычисления все продолжаются и продолжаются, и конца им не видно. Вообще говоря, так оно и есть: описанная вычислительная процедура завершиться в принципе не может. Известна теорема, впервые доказанная в 1770 году великим французским (и отчасти итальянским) математиком Жозефом Луи Лагранжем, согласно которой в виде суммы квадратов четырех чисел можно представить любое число. Теорема эта, кстати, весьма непроста (доказать ее как-то пытался великий современник Лагранжа, швейцарский математик Леонард Эйлер, человек, отличавшийся удивительной математической интуицией, оригинальностью и продуктивностью, однако его постигла неудача).