Max Home IndustryСтивен Вольфрам только что объявил приз за три доказательства, касающиеся правила 30. Что такое Правило 30 и почему оно так интересно?
Клеточные автоматы-это очень простые вычислительные системы. У вас есть набор правил, которые применяются на каждом шаге, и вы наблюдаете за развитием начальных конфигураций. Самый известный пример-жизнь 2D Конвея, но Стивен Вольфрам изучил и классифицировал более простой набор правил 1D.
Идея 1D CA ничем не отличается от 2D, но мы начинаем с строки ячеек, и на следующем тике строка заменяется новой строкой, определяемой правилом, которому следуют.
Поскольку это всего лишь 1D-схема, нам на самом деле не нужно заменять существующую строку, просто отобразите новую строку внизу, чтобы создать полную картину развития CA. Также можно указать правило в терминах цвета ячейки, двух ее соседей и цвета новой ячейки чуть ниже.
Например, шаблон:
задает правило, согласно которому, если ячейка белая и имеет двух черных соседей, то ячейка ниже должна быть черной.
Поскольку существует только восемь возможных вариантов расположения соседей, полное правило, которое точно определяет, что должно произойти в любой ситуации, должно перечислять только то, является ли результат каждого из восьми черным или белым.
Думая о черном как 1 и белом как 0, вы можете дать каждому соседнему шаблону число от 0 до 7, а затем прочитать полученную черную или белую ячейку в следующей строке как набор из восьми нулей или единиц, т. Е. двоичное число. Это можно использовать в качестве индекса для указания правила.
Это означает, что вы можете ссылаться на любое из 256 правил, которые возможны в 1D CA по номеру. Это само по себе является чем-то вроде концептуального прорыва, потому что теперь вы можете начать думать о классификации поведения каждого из возможных правил.
Из всех правил, которые мы можем рассмотреть, самое интересное-это правило 30, да, я знаю, что жаль, что это не правило 42.
Правило 30, по-видимому, создает псевдослучайный паттерн. Почему это интересно? Потому что сложное поведение от такого простого правила является неожиданным. Это то, что вы получаете, начиная с одной черной клетки:
Да, слева есть закономерность, но справа паттерн выглядит сложным, и он продолжает развиваться без повторений по мере увеличения числа поколений.
Есть так много вещей, которые мы не знаем о клеточных автоматах, и Вольфрам выбрал три теоремы, которые нуждаются в доказательствах для правила 30. Приз составляет 10 000 долларов за каждого:
Проблема 1: Всегда ли центральный столбец остается непериодическим?
Другими словами, можете ли вы доказать, что центральный столбец никогда не повторяется, или доказать, что он в конечном итоге является периодическим. Компьютерное моделирование уже показало, что он не становится периодическим после одного миллиарда шагов.
Проблема 2: Встречается ли каждый цвет ячейки в среднем одинаково часто в центральном столбце?
Если вы вычислите соотношение черных и белых клеток, это, по-видимому, будет сходиться к 1 по мере увеличения числа поколений, но точно ли это 1?
Задача 3: Требует ли вычисление n-й ячейки центрального столбца по крайней мере O(n) вычислительных усилий?
Прямой способ вычисления n-й ячейки с помощью моделирования-O(n2), но есть ли короткий путь?
Удивительно, что не только непонятно, как даже подойти к этим проблемам, но и кажется, что мы плохо представляем, насколько они сложны. Может потребоваться изобретение некоторых новых математических или компьютерных методов, чтобы даже начать. Возможно, решения очевидны, и все, что нам нужно, — это какой-то гений, чтобы взглянуть на проблемы по-новому.
Возможно, вы не подумаете, что 10 000 долларов-это слишком много для такой проблемы. Это, конечно, не связано с 1 миллионом долларов, предложенным за проблему P=NP, но решите любую из проблем правила 30, и люди обратят на вас внимание. Клеточные автоматы были предложены в качестве основы для новой физики, но проблема в том, что мы не можем с ними работать. Ответы на подобные вопросы могут подтолкнуть математику и физику к следующей важной теории.
Подробная информация о призе и о том, что именно вам нужно сделать, находится на его веб-странице, и у Вольфрама есть сообщение в блоге, которое посвящает вас в свои мысли по этому вопросу, и это делает необходимым чтение, если вы думаете о том, чтобы попробовать какую-либо из проблем.