30.000$ за решение задач о Правиле 30 для клеточных автоматов — конкурс от Стивена Вольфрама

Оригинал перевода в моём блоге

Поясним для читателей, что означает «Правило 30» — это элементарный клеточный автомат (см. Wiki), состояние которого (правило построения нового уровня ячеек на основе старого) в двоичной системе счисления задается как 0-0-0-1-1-1-1-0, что можно интерпретировать как 30 в десятичной системе счисления.

Итак, с чего все началось? — «Правило 30»

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

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

Итак, сегодня я предлагаю соискателям 30000 долларов США в качестве общей суммы призов за ответы на три основных вопроса о Правиле 30.

Правило 30 чрезвычайно просто:

Существует последовательность строк черных и белых клеток (ячеек) и, учитывая конкретную строку чёрно-белых ячеек, определяются цвета ячеек в строке ниже, рассматривая каждую ячейку в отдельности и ее смежных соседних ячеек, затем к ним применяется следующее простое правило подстановки, а именно:

Код

RulePlot[CellularAutomaton[30]]

[Посмотрите ролик, в котором за пару минут рассказывается суть клеточных автоматов и Правила 30 — примечание переводчика]

Что произойдет если начать с одной черной клетки? [Берется ряд из белых клеток, бесконечный в обе стороны и одна черная клетка, затем к этому ряду применяются правила, показанные выше, получается новый ряд и т. д. — примечание переводчика] Допустим, (как это сделал я сам сначала), что правило это достаточно простое, и шаблон, который получается на основе его работы, должен быть соответственно тоже простым. Однако если вы проведете эксперимент, то увидите, что получится после первых 50-ти шагов работы алгоритма:

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

Отсюда видно, что появляется некоторая закономерность — с левой стороны пирамиды. Но при этом многие аспекты этого шаблона выглядят как нечто образованное случайным образом.

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

На основе этой гипотезы я разработал подход к формированию науки совершенно нового типа — на базе принципов наблюдения за работой простых алгоритмов.

Постепенно накапливалось все больше доказательств этих принципов.

Однако вернемся к Правилу 30 и рассмотрим предметно, что именно оно нам позволяет делать, и в чем его польза? Что конкретно можно сказать о поведении данного алгоритма? Сразу бросается в глаза, что даже ответы на самые очевидные вопросы оказываются сложными.

Даже после десятилетий, за которые не было найдено ответов, я решил, что пришло время задать некоторые конкретные вопросы о Правиле 30, при этом простимулировав данное направление серьезными денежными призами.

Я уже пытался делать нечто подобное в 2007 году, назначив премию за ответ на основной вопрос о конкретной машине Тьюринга. И в данном случае результат был положительным и не заставил себя долго ждать. Всего через несколько месяцев этот приз был выигран — при этом навсегда установив, что из себя представляет простейшая из возможных универсальных машин Тьюринга, а также весьма убедительно доказав общий принцип вычислительной эквивалентности, разработанный ранее мной лично.

Конкурс по Правилу 30 снова ставит перед собой целью решение ключевой задачи, а именно: насколько сложным является поведение Правила 30? Каждая из задач ставит вопрос в этой области по-своему и конкретно. Как и само Правило 30, все они обманчиво просты в своей изначальной постановке. И все же решение любого из них будет огромным достижением, которое в итоге поможет осветить фундаментальные принципы свойств формирования вычислительной вселенной, которые выходят далеко за пределы специфики Правила 30.

Я работал над каждой из этих проблем более 35 лет. И все это время я пытался найти правильную идею в рамках непротиворечивого математического или вычислительного мышления, с целью наконец-то разрешить хотя бы одну из этих задач. Сейчас я хочу открыть этот процесс для обозрения всего мирового сообщества. Вместе с тем мне интересно будет узнать, чего можно достичь в решении данных вопросов, и какие методы при этом могут быть использованы.

Правило 30 — задачи для решения

Что касается конкурсных задач по Правилу 30, я ставлю в приоритет одну из ключевых особенностей работы алгоритма Правила 30, а именно: очевидную случайность формирования ячеек его центрального столбца. Начните с одной черной ячейки, затем проведите взглядом по последовательности значений цветов ячеек этого столбца и вы придете к выводу, что они случайны:

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

Задача 1: всегда ли центральный столбец остается непериодическим?

Рассмотрим начало центрального столбца Правила 30:

Не трудно обнаружить, что значения в данном столбце не повторяются — он не является периодическим. Но задача заключается в том, станет ли центральный столбец периодическим вообще когда-нибудь? Запустив Правило 30, мы видим, что последовательность не становится периодической даже в первом миллиарде шагов. Что же необходимо сделать, для того, чтобы доподлинно установить и доказать это.

Вот ссылка где находится первый миллион и первый миллиард значений данной последовательности (хранилище данных Wolfram).

Задача 2: Встречается ли каждый цвет ячейки (черный или белый) в среднем с равной вероятностью в центральной столбце?

Вот что мы получим на выходе, если подсчитаем количество черных и белых ячеек последовательно на большем количестве шагов в центральном столбце алгоритма Правила 30:

Результаты, безусловно, близки к равным для черных и белых ячеек. Здесь проблемным (вопросом задачи) является вопрос сходится ли это отношение к 1 при повышении числа шагов цикла.

Задача 3: Требует ли вычисление n-й ячейки центрального столбца хотя бы O(n) операций?

Чтобы найти n-ю ячейку в центральном столбце, всегда можно просто запустить Правило 30 для n шагов, вычисляя значения всех ячеек внутри выделенного на рисунке ниже ромба:

Но если сделать это напрямую, выполнится n² отдельных обновлений ячейки, поэтому требуемые вычислительные мощности возрастают как O(n²). Вопрос данной задачи — существует ли более (или самый) быстрый метод вычисления значения n-й ячейки без всех промежуточных вычислений — или, в частности, менее чем за O(n) операций.

Цифры из которых состоит число Пи

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

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

Просто чтобы сделать аналог немного ближе, вот первые несколько цифр Пи в системе счисления с основанием 2:

И вот первые несколько битов в центральном столбце Правила 30:

Ради интереса можно преобразовать их десятичную форму:

Конечно, известные алгоритмы вычисления цифр числа Пи значительно сложнее, чем сравнительно простое правило генерации ячеек центрального столбца Правила 30. Итак, что же нам известно о цифрах в числе Пи?

Во-первых, нам известно, что они не повторяются. Это было доказано еще в 60-х годах 18-го века, когда было показано что Пи — является иррациональным числом, поскольку единственные числа, цифры в которых повторяются, являются рациональными числами. (В 1882 году было также показано, что Пи трансцендентно, то есть, что его нельзя выразить через корни многочленов).

Так какую же здесь аналогию можно провести с постановкой задачи 2? Знаем ли мы, что в последовательности цифр числа Пи разные цифры встречаются с одинаковой частотой? К настоящему времени было вычислено более 100 триллионов двоичных цифр — и измеренные частоты цифр очень близки (в первых 40 триллионах двоичных цифр числа Пи отношение Единиц к Нулям составляет примерно 0,99999998064). Но при вычислении предела, будут ли частоты точно такими же? Ученые задавались этим вопросом в течение нескольких веков, но до сих пор математика не смогла дать на него ответа.

Для рациональных чисел последовательности цифр, из которых они состоят, являются периодическими, и при этом легко определить относительные частоты появления этих цифр в числе. Однако для последовательности цифр всех прочих «созданных природой (естественно построенных)» чисел, в большинстве случаев, практически ничего не известно о том к чему стремятся частоты цифр, входящих в число. Логично было бы предположить, что на самом деле цифры числа Пи (а также центральный столбец Правила 30) являются «нормальными» в том смысле, что не только каждая отдельная цифра, но и любой блок цифр заданной длины встречаются с равной предельной частотой. И, как было отмечено в работах по этой тематике 1930-х годов, вполне возможно «построить цифровую конструкцию (модель)» нормальных чисел. Постоянная Чемперноуна, полученная путем объединения цифр последовательных целых чисел, является примером вышесказанного рассуждения (это же можно получить на базе любого нормального числа, объединяя значения функций последовательных целых чисел):

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

Итак, рассмотрим, наконец, аналог задачи 3 для Пи? В отличие от Правила 30, где очевидным способом вычисления элементов в последовательности является один шаг за раз, традиционные способы вычисления цифр числа Пи включают в себя получение лучших приближений к Пи как к точному числу. Со стандартным («причудливым») рядом, изобретенным Рамануджаном в 1910 году и улучшенным братьями Чудновскими в 1989 году, первые несколько членов этой серии дают следующие приближения:

Так сколько же операций необходимо для того чтобы найти n-ю цифру? Число слагаемых, требуемых в ряду, равно O(n). Но каждое условие должно быть вычислено с n-значной точностью, которая требует, по меньшей мере O(n) отдельных вычислительных операций, подразумевающих, что в целом вычислительные трудозатраты будут больше, чем O(n).

До 1990-х годов предполагалось, что не существует никакого способа вычислить n-ю цифру Пи без вычисления всех предыдущих. Но в 1995 году Саймон Плуфф обнаружил, что на самом деле можно вычислить, хотя и с некоторой вероятностью, n-ю цифру, не вычисляя предыдущие. И хотя можно было бы подумать, что это позволит получить n-ю цифру меньше, чем за O(n) операций, тот факт, что нужно выполнять вычисления с точностью n-цифр, означает, что по крайней мере по прежнему требуется O (n) операций.

Результаты, аналогии и интуиция

Задача 1: всегда ли центральный столбец остается непериодическим?

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

Доказательство о паре столбцов использует особенность Правила 30. Рассмотрим структуру правила:

Существует возможность просто сказать, что для каждой тройки ячеек правило определяет цвет центральной ячейки по ней, но для Правила 30 можно также эффективно выполнять правило вбок: с учетом ячейки справа и выше можно также однозначно определить цвет ячейки слева. Это означает, что если взять два смежных столбца, можно восстановить весь шаблон слева:

Однако если бы столбцы имели периодическую структуру, из этого сразу бы следовало, что восстановленный шаблон также должен быть периодическим. Так, например, по построению, по крайней мере, начальные условия точно не являются периодическим, и, следовательно, оба столбца не могут быть периодическими. Это же утверждение справедливо, если столбцы не являются смежными, и если не известны все ячейки в обоих столбцах. При этом не существует никакого известного способа распространить это положение для одного столбца, такого как центральный столбец, и, таким образом, оно не решает первую задачу конкурса по Правилу 30.

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

Как вы считаете, это правдоподобно? Переходные процессы случаются — и теоретически (как и в классической задаче остановки машины Тьюринга) они могут быть даже произвольной длины. Здесь рассмотрим некоторый пример — найденный при поиске — Правила с 4-мя возможными цветами (общий код 150898). Предположим, мы запустим его на 200 шагов, при этом, как видно, центральный столбец будет являться совершенно случайным:

После 500 шагов весь шаблон выглядит совершенно случайно:

Здесь видно, что при приближении к центральному столбцу, происходит нечто удивительное: после 251 шага центральный столбец, кажется, перерождается до фиксированного значения (или, по крайней мере, фиксируется на последующие более чем миллион шагов):

Может ли такой же переходный процесс произойти и в Правиле 30? Рассмотрим шаблоны из Правила 30, и выделим те, где диагонали слева имеют периодичность:

По всей видимости, здесь существует граница, которая отделяет порядок слева от беспорядка справа. И, по крайней мере, за первые 100 000 шагов или около того, кажется, что граница смещается в среднем примерно на 0,252 шага влево на каждом шаге — с некоторыми случайными отклонениями:

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

Это, безусловно, именно тот случай, который иллюстрирует существование систем с исключительно длинными «переходными процессами». Теперь рассмотрим распределение простых чисел и вычислим LogIntegral[n] — PrimePi[n]

Да, колебания присутствуют, но на данной иллюстрации это выглядит так, как будто бы эта разница всегда будет в положительной области. И это, например, то, о чем рассуждал Рамануджан, но в итоге оказывается, что это не так. В начале граница того, где он потерпел неудачу, была, для того времени, астрономически большой (число Скивса 10^1010964). И хотя до сих пор никто не нашел явного значения n, для которого разность отрицательна, известно, что до n=10³¹⁷ она должна существовать (и в конечном итоге разность будет отрицательной).

У меня сформировалось мнение, что ничего подобного не происходит с центральным столбцом Правила 30, но пока у нас нет доказательств того, что это невозможно, утверждать этого нельзя.

Следует отметить, что существует возможность сделать предположение, что хотя принципиально и существует возможность доказать периодичность, раскрывая регулярность в центральном столбце Правила 30, ничего подобного не будет возможно проделать для непериодичности. Известно, что существуют шаблоны, центральные столбцы которых непериодические, хотя они и являются весьма регулярными. Основным классом таких примеров являются вложенные шаблоны. Вот, например, очень простая иллюстрация из Правила 161, в котором центральный столбец имеет белые ячейки, когда n=2^k:

А вот еще немного более сложный пример (из 2-цветного Правила 69540422 для двух соседей), в котором центральный столбец является последовательностью Туэ–Морса — ThueMorse[n]:

Можно считать, что последовательность Туэ–Морса генерируется последовательным применением замены:

Оказывается n-й член в этой последовательности задается как Mod[DigitCount[n, 2, 1], 2] — данный объект никогда не будет являться периодическим.

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

Следует отметить, что все конкурсные задачи из Правила 30 рассматриваются в постановке алгоритма, работающего на бесконечном множестве клеток. Но что, если попробовать рассматривать только n ячеек, скажем, с периодическими граничными условиями (то есть брать правого соседа самой правой ячейки в качестве самой левой ячейки и наоборот)? При этом очевидно, что существует 2ⁿ возможных полных состояний системы — и можно построить диаграмму состояний перехода, которая будет показывать, какое одно состояние развивается до какого другого. Рассмотрим диаграмму для n=5:

И вот это для n=4 до n=11:

Структура ее заключается в том, что существует группа состояний, которые появляются только как переходные процессы, вместе с другими состояниями, которые находятся в циклах. Неизбежно, что цикл не может быть длиннее 2ⁿ (на самом деле, соображения симметрии показывают, что он всегда должен быть несколько меньше).

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

И, по крайней мере, для этих значений n период довольно хорошо аппроксимиуется функцией 2^0.63n. И да, по крайней мере, во всех этих случаях период центрального столбца равен периоду общей эволюции клеточного автомата. Но что означают эти результаты для конечного размера в случае распространения выводов, полученных на их основе, на совокупности ячеек бесконечного размера? Ответ не является очевидным и тривиальным.

Задача 2: Встречается ли в среднем каждый цвет ячейки с одинаковой частотой в центральной колонке или нет?

Рассмотрим график отклонений количества Единиц от Нулей на 10000 шагах центрального столбца Правила 30:

За миллион шагов:

И миллиард шагов:

На основе этих данных можно увидеть, что существуют случаи, когда есть превышение количества 1 (единиц) над 0 (нулями), и наоборот, хотя, по мере приближения к миллиарду шагов количество Единиц, кажется, выигрывает у Нулей, по крайней мере, на данный момент.

Так давайте же вычислим отношение общего числа Единиц к общему числу Нулей. Вот такая картина у нас получится после 10 000 шагов:

Как вы считаете, приближается ли это к значению 1? Сложно сказать…

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

Отклонение становится все меньше, но все еще трудно сказать, что произойдет в итоге. Построение отклонения отношения количества Единиц и Нулей от 1 на графике при миллиарде шагов позволяет предположить, что оно систематически уменьшается:

Как можно быть уверенными, что эта тенденция сохранится? На данный момент у нас не может быть такой убежденности. И действительно, все может оказаться довольно плохо. Возможно, колебания Единиц против Нулей увеличиваются, поэтому, даже если мы усредняем по более длинным последовательностям, общее соотношение никогда не сойдется до определенного значения.

Опять же, у меня существуют сомнения, что это произойдет в центральном столбце Правила 30, но без доказательств мы не можем знать этого наверняка.

Здесь мы рассматриваем частоты появления черных и белых клеток, но очевидное здесь обобщение состоит в том, чтобы задать вместо этого вопрос о частотах для блоков ячеек длины k. Мы можем рассмотреть вопрос, все ли 2^k таких блоков имеют одинаковую предельную частоту или нет. Или мы можем задать более простой вопрос о том, встречаются ли когда-либо все из этих блоков, или, другими словами, если один блок заходит достаточно далеко, центральный столбец Правила 30 будет содержать любую данную последовательность длины k (допустим побитовое представление некоего литературного произведения).

В крайнем случае, здесь мы можем получить эмпирические доказательства. Например, по крайней мере, до k=22, все 2^k последовательностей имеют место быть, и вот сколько шагов нужно, чтобы подтвердить это:

Следует отметить, что можно добиться приемлемого результата для блоков одной длины, но потом потерпеть неудачу для блоков большего размера. Например, упомянутая выше последовательность Туэ–Морса имеет равные частоты Нулей и Единиц, но пары не встречаются с одинаковыми частотами, а тройки идентичных элементов просто никогда не встречаются.

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

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

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

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

А вот гистограмма значений, достигнутых на следующих этапах:

Эта гипотеза согласуется с тем, что стремящаяся к пределу гистограмма является плоской или, другими словами, эти числа равномерно распределены в интервале от 0 до 1.

В начале 1900-х годов было получено множество математических результатов об этом виде равномерных распределений. В частности, известно, что последовательность вида FractionalPart[h n] для последовательного n будет всегда равномерно распределена если h не является рациональным числом. Также известно, что последовательность FractionalPart[hⁿ] равномерно распределена почти для любых h (числа Пизо как и золотое сечение являются исключениями), но конкретные случаи — как FractionalPart[(3/2)ⁿ] — ускользали от анализа как минимум полвека. (Кстати, известно, что цифры Пи в 16-ричной системе и, следовательно, в 2-ичной системе могут быть сгенерированы с помощью рекуррентной формулы FractionalPart[16x_n-1 + r[n]], где r[n] фиксированная рациональная функция от n.)

Вопрос 3: Требует ли вычисление n-й ячейки центрального столбца использования около O(n) операций?

Рассмотрим шаблон, созданный по Правилу 150:

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

Как мы определяем значение n-й ячейки? Что ж, в данном конкретном случае оказывается, что в сущности есть простая формула: значение задается как Mod[IntegerExponent[n, 2], 2]. Другими словами, просто посмотрите на число n в двоичной системе, и спросите, является ли число нулей в конце четным или нечетным.

Сколько вычислительных мощностей потребуется, чтобы «оценить эту формулу»? Ну, даже если мы должны проверить каждый бит в n, существует только о Log[2, n] из них. Таким образом, мы можем ожидать, что потребуется O(logn) операций.

Так как же все-таки будет обстоять дело для случая Правила 30? Мы знаем, что можем определить значение n-й ячейки в центральном столбце, просто явным образом применив алгоритм Правила 30 для обновления правила n² раз, но здесь вопрос в том, есть ли способ сократить необходимую вычислительную работу. В прошлом в математических науках существовало неявное предположение, что если у ученого есть подходящая математическая модель для чего-либо, то, просто проявив достаточную сообразительность, он всегда найдет способ делать предсказания — или, другими словами, выяснить, то как модель системы будет реагировать, используя гораздо меньше вычислительных мощностей, чем этого требует реальная эволюция системы.

Существует множество примеров «точных решений» (например, задача двух тел, двумерная модель Изинга и т. д.), где, по сути, мы просто получаем формулу того, что будет делать система, но существуют и другие случаи (например, задача трех тел, 3D-модель Изинга и т. д.), когда этого невозможно добиться.

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

Таким образом, в действительности Задача 3 ставится о вычислительной неприводимости Правила 30 или, по крайней мере, о его конкретном аспекте. (Оценка сложности O(n) операций несколько произвольна; другой вариант этой проблемы может потребовать O(n^α) для любого α <2, или, в этом отношении, O(log^β(n)) — или некоторого критерия, основанного как на времени, так и на ресурсах оперативной памяти.)

Если ответ на вопрос Задачи 3 будет отрицательным, то очевидным было бы просто дать явную программу, которая успешно вычисляет n-ое значение в центральном столбце с меньшими вычислительными усилиями, чем O(n), как мы это делали для Правила 150 до этого.

Что такое сложность вычислений O (n)? Какую именно систему (среду) мы должны использовать для вычислений, как мы измеряем «вычислительные мощности»? Здесь феномен вычислительной универсальности подразумевает, что — в рамках некоторых основных ограничений — это, в конечном счете, не имеет значения.

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

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

Я уверен, что Правило 30 вычислительно неприводимо, и что вопрос 3 имеет положительный ответ, но если нет, то я предполагаю, что в конечном итоге появится программа, которая, очевидно, будет вычислять n-ое значение меньше, чем за O(n) операций и это потребует многочисленных споров о деталях того, правильно ли подсчитаны при этом вычислительные ресурсы.

Однако доказать, что такой программы не существует, гораздо сложнее. И хотя я подозреваю, что вычислительная неприводимость довольно повсеместна, всегда очень трудно показать явные нижние границы сложности выполнения конкретных вычислений. На самом деле, почти все явные нижние границы, известные в настоящее время, являются довольно слабыми и, по сути, сводятся к рассуждениям о содержании информации — например, необходимо O(logn) шагов, чтобы только прочитать все цифры в значении n.

Несомненно, самой известной проблемой нижней границы является вопрос равенства классов P и NP. Я не думаю, что есть прямая связь с нашей проблемой Правила 30 (которая больше похожа на вопрос P против LOGTIME ), но, возможно, здесь следует попытаться понять, как все эти задачи логически связаны между собой. Суть заключается в том, что прямая эволюция клеточного автомата, скажем, для n шагов от начального условия с указанием n ячеек, является не более чем вычислением O(n²) и, следовательно, происходит за P («полиномиальное время»), но вопрос о том, существует ли начальное условие, которое развивается, чтобы произвести некоторый конкретный конечный результат, находится в классе NP. Если у вас получится («недетерминированно») выбрать правильное начальное условие, то на выходе вы затратите полиномиальное время, чтобы это проверить, но при этом не следует забывать, что потенциально существует 2ⁿ возможных начальных условий для этой проверки.

Существует множество клеточных автоматов, где не нужно проверять все эти 2ⁿ начальных условий, и при этом вычисления будут выполнены за полиномиальное время, которого будет явно достаточно. Существует возможность построить клеточный автомат, где нахождение начального условия является NP-полной задачей, или, другими словами, где можно кодировать любую проблему в NP для данной конкретной проблемы инверсии клеточного автомата. Является ли при этом задача обращения Правила 30 NP-полной? Нам это не известно, хотя кажется вполне вероятным, что это может быть доказано (и если кто-то это докажет, то Правило 30 может в конечном итоге стать криптосистемой с полной доказуемостью NP).

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

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

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

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

Итак, рассмотрим другое направление, в котором существует возможность получения эмпирических данных о нашей Задаче 3. Существует ли способ использовать статистику, или криптоанализ, или математику, или машинное обучение чтобы хоть немного снизить вычислительные мощности, необходимые для вычисления n-го значения в центральном столбце шаблона?

Известно, что вся двумерная модель Правила 30 далеко не случайна. На самом деле, из всех 2^m2 пятен может быть только m×m и на практике это число, взвешенное по вероятности, намного меньше. Я не сомневаюсь, что подобные факты могут быть использованы для уменьшения вычислительных мощностей центрального столбца до значения, меньшего, чем O(n²) (и это было бы хорошим частичным результатом). При этом может ли это быть меньше, чем O(n) вычислений? Вот это гораздо более сложный вопрос.

Ясно, что если бы на Задачу 1 был дан отрицательный ответ, тогда это может быть, но в каком-то смысле запрос на вычисление центрального столбца менее чем O(n) — это то же самое, что запрос на наличие «предсказуемых закономерностей». Конечно, даже если бы можно было найти мелкомасштабные статистические закономерности в последовательности (как можно предположить, отвечая на Вопрос 2 отрицательно), они сами по себе не позволили бы сделать больше, чем возможно, при этом только слегка улучшив постоянный множитель в скорости вычисления последовательности.

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

Для решения данной задачи можно попробовать использовать статистические методы. Если бы мы могли обнаружить статистическую «неслучайность» в последовательности, то это означало бы способность сжимать последовательность и, соответственно, получать некоторую избыточность или предсказуемость в последовательности. Однако я перепопробовал все виды статистических тестов на случайность в центральной колонке Правила 30 и не обнаружил каких-либо существенных отклонений от случайности. (А в течение долгих лет — пока мы не нашли чуть более эффективное правило — мы использовали последовательности из систем Правила 30 конечного размера в качестве генератора псевдослучайных случайных чисел для языка Wolfram Language, и никаких принципиальных ошибок «и это не случайно!» Никогда не обнаруживалось).

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

Итак, попробуем использовать идеи из математики для предсказания последовательности Правила 30. Становится ясным, что Правило 30 не связано с какой-либо хорошо развитой областью математики. Но, конечно, возможно, что какое-то сопоставление может быть найдено между Правилом 30 и идеями, скажем, в области, подобной теории чисел, — и что они могут либо помочь найти предпосылки для вычислений Правила 30, либо показать, что вычислению эквивалентна некоторая задача, такая как целочисленный факторинг, которая считается принципиально сложной.

Существует несколько примеров достаточно интересных взаимодействий между традиционными математическими структурами и клеточными автоматами. Например, рассмотрим цифры последовательных степеней 3 по основанию 2 и по основанию 6:

Оказывается, что в случае по основанию 6 правилом генерации является именно клеточный автомат. (Для основания 2 есть дополнительные переносы на большие расстояния). Хотя оба эти шаблона выглядят сложными, оказывается, что их математическая структура позволяет нам ускорить определенные предсказания о них.

Рассмотрим s-ю цифру от правого края строки n в каждом шаблоне. Это просто s-я цифра в 3ⁿ, которая задается «формулой» (где b — это основание, в нашем случае 2 или 6) Mod[Quotient[3ⁿ, b^s], b]. Так насколько же легко оценить эту формулу? Можно подумать, что для вычисления 3ⁿ нужно выполнить n умножений, но это оказывается не так: вместо этого можно, например, построить 3ⁿ используя повторное возведение в квадрат, с умножением на log(n). То, что это, возможно, является следствием свойством ассоциативности умножения. Очевидно, что нет ничего подобного Правилу 30, но всегда вероятно, что существует возможность найти какое-то отображение на математическую структуру, подобную этой.

В Задаче 3 мы говорим о вычислительных мощностях по вычислению n-^го значения в центральном столбце Правила 30 и спрашиваем, может ли оно быть меньше, чем O(n), но представьте, что у нас есть определенный алгоритм выполнения вычислений и для любого данного n мы можем видеть, какие вычислительные ресурсы он использует. Предположим, результат r[n] тогда мы спрашиваем, является ли r[n] меньше «O-большое» от n или, другими словами, что MaxLimit[r[n]/n, n→∞ ]<∞.

Представьте, что у нас есть конкретная машина Тьюринга (или какая-то другая вычислительная система), которая реализует наш алгоритм. Может случиться так, что r[n] будет по крайней мере асимптотически просто гладкой или иначе регулярной функцией от n, для которой легко увидеть, каков предел, но если кто-то только начинает перебирать возможные машины Тьюринга, он сталкивается с примерами, где r[n] имеет пики случайных высот в случайных местах. Возможно даже, что где-то будет значение n для которого машина Тьюринга вообще не останавливается (или что-то в этом роде), так что r[n] бесконечно. В общем, как мы обсудим более подробно позже, может быть даже невозможно решить, как растет r[n] относительно O(n).

Формальная постановка задач Правила 30

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

В языке Wolfram Language первые значения t в центральном столбце Правила 30 задаются следующим образом:

И с этим определением три проблемы могут быть сформулированы как предикаты c[t].

Задача 1: Всегда ли центральный столбец остается непериодическим или нет?

или же

или не существует периода p и начальной длины i что для всех t, таких что t>i, с[t + p] равно c[t].

Задача 2: Каждый цвет ячейки встречается в среднем одинаково часто в центральной колонке или нет?

или же

или предел суммы значений в c[t]/t при t→∞ равен 1/2.

Задача 3: Требует ли вычисление n-й ячейки центрального столбца хотя бы O(n) операций?

Определим machine[m] как функцию, параметризованную m (например, может быть машина Тьюринга TuringMachine[...]), и пусть machine[m][n] дает на выходе список {v, t}, где v — выходное значение, а t — количество выполненных вычислительных мощностей (например, количество шагов). Тогда задача может быть сформулирована как:

или «не существует числа m, такого, чтобы machine[m] для всех n выдавала c[n] и для которой предел количества операций, деленный на n, конечен». (Также существует требование чтобы m было конечным, чтобы «правило» машины не могло просто хранить ответ).

Формальный характер решений

Прежде чем мы обсудим задачи раздельно, очевидный вопрос, который необходимо задать, заключается в том, какова может быть взаимозависимость проблем. Если ответ на Вопрос 3 отрицательный (в чем я лично сильно сомневаюсь), то он дает возможность для простых алгоритмов или формул, из которых следуют ответы на Задачи 1 и 2, которые могут стать простыми. Если ответ на Задачу 3 является положительным (как я сильно надеюсь), то это означает, что ответ на Задачу 1 также должен быть положительным. Противоположное также верно: если ответ на Задачу 1 отрицательный, то это означает, что ответ на Задачу 3 также должен быть отрицательным.

Если ответ на Задачу 1 отрицательный, следовательно, в центральном столбце есть некоторая периодическая последовательность, то есть тот, кто явно знает эту последовательность, может сразу ответить на Задачу 2. Можно подумать, что ответ на Задачу 2 в отрицательной форме подразумевает кое-что о Задаче 3. И действительно, неравные вероятности для черного и белого цвета подразумевают сжатие с постоянным коэффициентом в виде информации Шеннона но для вычисления значения с меньшим, чем O(n) операций — и, следовательно, для отрицательного ответа на Проблему 3, требуется, чтобы можно было в некотором смысле идентифицировать бесконечно большее сжатие.

Итак, что нужно для того, чтобы получить ответы на все задачи?

Если на Задачу 1 получен отрицательный ответ, то можно вообразить, что она явно демонстрирует шаблон, сгенерированный Правилом 30 на каком-то заданном шаге, и может видеть периодическую последовательность в центре. Конечно, на Задачу 1 можно ответить отрицательно, но менее конструктивно. Можно было бы показать, что в конечном итоге последовательность должна быть периодической, но не знать даже каких-либо границ, где это может произойти.

Один из способов (весьма неправдоподобный, на мой взгляд), что и задача 2, и задача 3 могут быть решены отрицательно, — это явно указывает на то, что существует алгоритм для центрального столбца, который делает очевидным, что черные и белые ячейки появляются с одинаковой частотой. В общем, если на Задачу 3 получен отрицательный ответ, способ сделать это состоит в том, чтобы явно указать алгоритм (или, скажем, машину Тьюринга), который выполняет вычисления с использованием менее чем O(n) операций.

Допустим, у кого-то есть такой алгоритм. При этом необходимо доказать, что для всех n алгоритм правильно воспроизведет n-ое значение. Тогда как это можно будет сделать достаточно легко. Возможно, будет простое доказательство по индукции или что-то в этом роде, но одновременно это может быть сколь угодно сложно. Например, может быть, что для большинства n время работы алгоритма явно меньше n. Однако это может быть не очевидно, что время выполнения всегда будет даже конечным. Действительно, «задача остановки» для алгоритма может быть просто неразрешимой. Но просто демонстрация, что конкретный алгоритм не останавливается для данного n, на самом деле ничего не говорит при получении ответа на задачу. Для этого нужно показать, что не существует алгоритма, который успешно остановился бы менее чем за O(n) операций.

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

Может ли быть так, что ответы на вопросы зависят от системы выбора аксиом или даже от того, что они не зависят от традиционных аксиом (в смысле теоремы Гёделя о неполноте)? Исторический опыт математики подсказывает, что это может быть крайне маловероятным, поскольку на сегодняшний день, по существу, все «естественные» проблемы в математике, по-видимому, оказались разрешимыми в (иногда довольно неявной) системе аксиом, которая используется в математике.

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

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

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

В лучшем случае можно было бы просто явно продемонстрировать эту серию приложений правил — таким образом, чтобы компьютер мог сразу проверить, что они верны. Возможно, ряд приложений правил можно найти с помощью автоматического доказательства теорем (как в FindEquationalProof). Скорее всего, оно (доказательство) может быть построено с использованием системы ассистента доказательства.

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

Здесь отсутствует точное определение понятия о том, что такое доказательство. В наших пошаговых решениях в Wolfram|Alpha мы эффективно доказываем результаты (например, в расчетах) таким образом, чтобы студенты могли отслеживать их. В академическом математическом журнале приводятся доказательства, которые успешно проходят процесс рецензирования.

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

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

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

Что потребуется для решения задач?

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

Конечно, может оказаться так, что ни одна из существующих «башен» знаний — скажем, в области математики — не будет иметь отношения к рассматриваемым задачам, и что для их решения потребуется строительство новой башни «с нуля». И действительно, именно это в итоге и произошло с решением задач для моей 2,3 премии Тьюринга в 2007 году.

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

Прямой способ вычислить n элементов в центральном столбце — запустить Правило 30 для n шагов, используя на промежуточном этапе до n ячеек памяти. Фактические данный вид вычислений довольно хорошо оптимизированы в языке Wolfram Language. Работая на моем настольном компьютере, требуется менее 0,4 секунды для вычисления 100 000 элементов:

Внутренние алгоритмы используют тот факт, что Правило 30 может быть выражено как Xor[p, Or[q, r]], и реализовано с использованием побитовых операций над целыми словами данных одновременно. Использование явных битовых операций на длинных целых числах занимает примерно в два раза больше чем, встроенный в функцию CellularAutomaton алгоритм:

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

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

Обобщения и связи

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

Например, вместо того, чтобы рассматривать вертикальный столбец ячеек в центре шаблона Правила 30, можно посмотреть на столбец ячеек в другом направлении. При взгляде под углом 45° на паттерн, порождаемы Правилом 30, легко видеть, что любая последовательность должна быть периодической. Слева периоды увеличиваются очень медленно; справа они увеличиваются быстро. Но как насчет рассмотрения под другими углами?

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

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

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

Можно также задуматься над тем, что происходит, когда есть не только одна черная клетка, но и более длинная последовательность в начальных условиях. Как меняется центральный столбец с различными начальными последовательностями? Существуют ли конечные начальные последовательности, которые приводят к «более простым» центральным столбцам?

Или существуют бесконечные начальные условия, генерируемые другими вычислительными системами (скажем, системами замещения), которые не являются периодическими, но все же дают как-то простые шаблоны Правила 30?

Тогда можно представить себе как выйти за пределы «Правила 30». Что произойдет, если добавить в правила «исключения» более дальнего действия? Когда расширения Правила 30 показывают поведение, которое может быть проанализировано тем или иным способом? И можно ли тогда увидеть эффект устранения «исключений» в правиле?

Конечно, можно также рассмотреть правила, совершенно отличные от Правила 30, и, возможно, надеяться развить интуицию или методы, относящиеся к Правилу 30, взглянув на другие правила. Даже среди 256 двухцветных правил (работающих с соседями данной ячейки) есть другие, которые демонстрируют сложное поведение, начиная с простого начального условия:

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

Наконец давайте обсудим конкретные Призовые правила Конкурса «Правила 30». Для того чтобы исследовать возможность периодичности в Правиле 30 (как в задаче 1), можно изучить множество различных правил, искать примеры с очень длинными периодами или очень длинными переходными процессами — и попытаться использовать их для разработки представления о том, как и когда это может произойти.

Чтобы исследовать явление одинаковой частоты в Задаче 2, можно взглянуть на различные статистические особенности и увидеть как в Правиле 30, так и в разных правилах, когда можно обнаружить регулярность их поведения.

Для Задачи 3 можно начать смотреть на разные уровни вычислительной мощности. Можно ли найти n-ое значение за O(n^γ) операций для любого γ <2 (я не знаю какого-либо метода для достижения этой цели)? Можно ли показать, что нельзя найти n-ое значение за менее, чем O(log(n)) операций? Как насчет менее чем O(log(n)) доступной памяти? А как насчет разных правил? Периодические и вложенные шаблоны вычисляются легко и быстро. Какие еще примеры можно найти?

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

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

Являются ли поставленные в конкурсе задачи сложными и насколько?

Когда в 2007 году я учредил свои 2,3 премию Тьюринга я не догадывался, через сколько она будет разрешена — через месяц, год, десятилетие, век или больше. Как оказалось, она разрешилась фактически примерно через четыре месяца. Так что же произойдет с задачами призового конкурса Правила 30? Я не знаю. Спустя почти 40 лет я был бы удивлен, если бы какая-либо из них может быть решена через месяц (но это было бы действительно невероятно, если бы это так случилось!). И, конечно, некоторые внешне похожие проблемы (например, особенности цифр Пи) существуют уже более века.

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

Я не знаю, будут ли решения поставленных задач «очевидно правильными» (будет весьма полезно, если они будут конструктивно решены и представлены в вычисляемой форме), или же потребуется длительный период проверки их доказательств. Я не знаю, будут ли доказательства сравнительно короткими или невероятно длинными. Я не знаю, будут ли решения зависеть от деталей систем аксиом («предполагая гипотезу континуума» и т. д.). Или они будут надежными для любого разумного выбора аксиом. Я не знаю, являются ли три задачи какими-то «сравнительно трудными», или, если одна или две могут быть решены, а другие продержатся не решенными очень долго…

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

Естественно, прожив сейчас с неразрешенными задачами для Правила 30 в течение почти 40 лет, я лично буду рад узнать наверняка еще что-то новое о его замечательном поведении.

Хотите научиться программировать на языке Wolfram Language?
Недавно вышел курс «Основы эффективной работы с технологиями Wolfram» и скоро начнется новый курс (зарегистироваться).

Автор: OsipovRoman

Источник