Как профессор информатики помог найти неуловимую плитку Эйнштейна

Прочитано: 77 раз(а)


Наконец-то решена математическая задача почти 60-летней давности.

История началась прошлой осенью, когда Дэвид Смит, отставной типограф из Йоркшира, Англия, наткнулся на фигуру с дразнящими свойствами. Энтузиаст плитки на протяжении всей своей жизни обнаружил 13-гранную форму, названную шляпой, которая способна заполнить бесконечную плоскость без наложений или пробелов в узоре, который не только никогда не повторяется, но и никогда не может быть повторен.

Эта неуловимая форма известна математикам как апериодическая моноплитка или эйнштейн, умный каламбур, получивший свое название от немецких слов ein и stein, означающих один камень.

«Мы с Дэйвом поддерживали связь на протяжении многих лет, и мы принадлежим к одному и тому же старомодному списку для людей, интересующихся тайлингом, — смесь энтузиастов тайлинга, программистов и математиков», — вспоминает профессор Школы компьютерных наук Черитон Крейг С. Каплан. который сотрудничал со Смитом, разработчиком программного обеспечения Джозефом Майерсом и математиком Хаимом Гудман-Штраусом над статьей, доказывающей существование неуловимого Эйнштейна.

«Дэйв был на пути к чему-то большому, историческому, но он уперся в то, что мог сделать вывод об этой форме, работая с вырезками из бумаги. Он знал, что я недавно опубликовал статью на связанную тему, для которой я разработал статью. программного обеспечения, которое мы могли бы использовать, чтобы понять, что делает его фигура. Он прислал мне электронное письмо с вопросом: «Эй, можешь запустить это через свое программное обеспечение и посмотреть, что произойдет?»

Математики пытались найти форму, подобную фигуре Эйнштейна Дэвида Смита, с 1960-х годов, когда американский математик Роберт Бергер открыл первый пример апериодической мозаики.

«Апериодический набор фигур Бергера был найден в середине 1960-х годов, и в этом наборе было 20 426 фигур», — объяснил профессор Каплан. «Это была сложная конструкция с комбинаторным набором функций, которая требовала множества форм, чтобы гарантировать, что шаблон не повторяется. Это было важным открытием, но следующий естественный вопрос для математиков: можем ли мы получить меньшие наборы? наименьшее количество фигур, с которыми мы можем это сделать?»

К 1970 году набор фигур, которые, как было доказано, апериодически укладываются мозаикой, сократился примерно до 100, а в 1971 году математик Рафаэль Робинсон сократил его до шести. Затем, в 1974 году, сэр Роджер Пенроуз обнаружил одноименные плитки Пенроуза, которые сократили их число до двух.

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

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

«Знаменитая проблема P и NP в компьютерных науках — вопрос о том, сколько времени требуется для выполнения определенного класса алгоритмов — все еще остается открытой, но есть консенсус, как это будет происходить», — сказал профессор Каплан. «Почти каждый ученый-компьютерщик думает, что P не равно NP. Но существование апериодической моноплитки не относится к этой категории. Мнения разделились. Это одна из вещей, которые мне нравятся в этой проблеме. ложно. Единственное, что я знал наверняка, это то, что если оно ложно (если не существует апериодической моноплитки), то это будет чрезвычайно трудно доказать, потому что это утверждение обо всех возможных формах. Тогда как доказать, что конкретная фигура является апериодической моноплиткой, проще. потому что, ну, вот оно Вы только пытаетесь доказать свойство одной формы.

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

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

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

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

«Ключевая компьютерная часть нашего доказательства состоит в том, чтобы сказать: «Мы должны быть в состоянии сказать что-то об общих мозаиках шляпы, о которых мы ничего не знаем». Но как мы можем что-то сказать о мозаике, над структурой которой мы не властны?В этой части доказательства мы показываем, что даже если вы ничего не знали о входе, у мозаики есть определенная структура, которую вы можете объяснить. Один из способов сделать это — исчерпывающе перечислить маленькие окрестности плиток — все маленькие окрестности, которые могут встретиться в реальной плитке».

От многого можно отказаться. В одном конкретном районе вы видите, что нет возможности окружить эти плитки другим слоем плиток, поэтому это не может произойти в реальной плитке. Это просто изолированная капля.

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

Было обнаружено, что плитка Пенроуза имеет глубокую связь с миром природы. В 1982 году профессор Университета штата Айова Дэн Шехтман обнаружил, что симметрии, подобные симметрии в плитках Пенроуза, обнаруживаются в молекулярных структурах, называемых квазикристаллами — кристаллической молекуле, которая упорядочена, но не периодична — открытие, за которое он получил Нобелевскую премию по химии в 2011 году. .

«Размышлять интересно, но я не физик и не инженер», — сказал профессор Каплан. «То, что мозаика Пенроуза имеет связь с наукой о материалах, удивительно, но это не гарантирует того, что другие апериодические мозаики имеют такое же отношение или шляпу. Моя работа связана с применением математики в искусстве. Прежде всего, для меня мозаика шляпы интересно и визуально захватывает. Люди уже используют его для создания интересных дизайнов в различных средствах массовой информации. Пожалуйста, продолжайте в том же духе. Это потрясающе, и мне это нравится».

Возможно, шляпа могла бы оставить свой след в Ватерлоо более конкретным образом.

«В Математическом институте Оксфордского университета есть каменный двор, где работает Пенроуз, выложенный плиткой Пенроуза . Если у вас есть прорыв в теории укладки плитки, почему вы не укладываете ее на пол в одном из ваших учебных корпусов? теперь почти идеально, когда здание Math 4 было одобрено для строительства и находится на стадии проектирования».

Как профессор информатики помог найти неуловимую плитку Эйнштейна



Новости партнеров