Клеточный автомат будущего и Новая интерпретация квантовой механики
Стоит, пожалуй, выбраться из спячки в ЖЖ, чтобы поведать об одной идее.
Меня давно уже преследует (несколько безумная) мысль о клеточном автомате, на состояние которого будет влиять не прошлое, а будущее.
А именно, правила автомата начинают действовать только тогда, когда автомат уже перешёл в своё следующее состояние.
Идея на самом деле довольно простая: на состояние клетки влияют не её соседи в текущем поколении, как в обычном автомате, а её соседи в следующем поколении.
То есть, например, клетка остаётся жить в следующем поколении, если в следующем же поколении у неё будут два или три соседа. Пустая клетка рождается в следующем поколении, если в следующем поколении у неё будет ровно три соседа. (Здесь и далее я использую правила стандартной игры Жизнь Конвея).
Всё это можно изобразить на рисунках:
1) Зелёная клетка в текущем поколении останется жить в следующем поколении в каждом из возможных четырёх случаев - если у неё будет 2 или 3 соседа в следующем поколении (при этом совершенно не имеет значения, что именно находится в текущем поколении в соседних клетках, обозначенных вопросами):
2) Зелёная клетка в текущем поколении исчезнет в следующем поколении в каждом из четырёх возможных случаев (когда в следующем поколении у неё только один или совсем нет соседей).
3) Пустая клетка в текущем поколении родится в следующем поколении, если в следующем поколении у неё будет ровно три соседа:
На всех этих примерах изображена угловая клетка и доска не циклическая, поэтому варианты именно такие. Конечно, для центральных клеток варианты будут другие.
Настоящая сложность возникает, когда пытаешься представить, как эту задачу решить. Что значит, что у клетки будет два соседа в следующем поколении? Разве наличие самих этих двух соседей (каждого из них) не определяется их собственным окружением в будущем, которое включает в себя и ту клетку, с которой мы начали? Ведь все эти клетки и их соседи взаимозависимы, и мы входим в бесконечный цикл, пытаясь определить, какая из клеток на какую влияет.
Казалось бы, выхода из этой ситуации нет, и идея обречена.
Однако, недавно меня осенило. Чтобы опробовать эту идею на практике, нужно поле конечного размера и проверка всех возможных состояний этого поля на предмет возможности их перехода в любое из возможных состояний этого поля в будущем.
То есть, если мы возьмём какое-то начальное состояние и проверим все возможные следующие поколения так, чтобы правила, определённые выше, соблюдались - мы, возможно, увидим какой-то разрешенный правилами переход из текущего состояния в следующее. И так для всех начальных состояний.
Я тут же написал программу для доски 4х4, которая проработала 8 часов (проверив, как понятно, (2^16)*(2^16) = 4,294,967,296 варианта) и получил следующие результаты.
Всего существует 273 (из 65536) состояний, которые могут иметь следующее поколение. В этом отличие от обычного автомата, в котором любое состояние имеет следующее поколение. На самом деле, таких начальных состояний гораздо меньше, если выкинуть все повороты и отражения.
Пример перехода:
Самая устойчивая комбинация, в которую переходит абсолютное большинство начальных состояний (а именно 256 из них), такова:
Без поворотов и отражений таких переходов всего 16, если не ошибаюсь.
Вторая возможная комбинация (с учётом поворотов), в которую переходят остальные состояния такова:
Есть ещё тривиальное состояние пустого поля, в которую переходит только полностью заполненное поле.
Интересно, что для такого автомата переход может быть неоднозначным, то есть для одного поколения может существовать несколько следующих поколений. Например, следующее состояние может иметь два возможных продолжения:
После такого тщательного исследования идея, конечно, не выглядит особенно интересной. Но это и понятно при таком минимальном размере доски. Проверить доску 5x5 я не в состоянии (1,125,899,900,000,000 проверок, и даже если убрать все повороты, число всё равно будет огромное).
Но гораздо более интересное исследование можно провести на одномерном клеточном автомате, которые исследовал Вольфрам). Таких автоматов всего 256, поэтому исследовать их можно все до одного. Возможно, какие-то из правил и приведут к автомату, у которого будет несколько поколений, а может быть, какие-то из них даже получатся циклическими, то есть такой автомат будет жить вечно.
Интересно также будет посмотреть, какие у разных автоматов получаются устойчивые состояния, сколько возможных следующих поколений будет у разных автоматов и т.д.
Это предмет будущих исследований.
И тут меня посетила ещё одна мысль.
Что, если Вселенная устроена именно таким образом - а именно, на положение элементарных частиц (или, выражаясь по-научному, на состояние квантовой системы в гильбертовом пространстве) влияет не их текущее состояние, а будущее состояние их «соседей» или будущее состояние системы.
Мы знаем, что случайность квантовой механики фундаментальна и Демон Лапласа невозможен, а отсюда исходят разные её интерпретации вроде мультивселенной и т.п. Однако, может быть, ещё одна возможная интерпретация квантовой механики состоит в том, что система переходит в следующее состояние не случайным, как нам представляется, образом (и тем более не переходит сразу во все возможные состояния в разных вселенных), а переходит она туда, подчиняясь правилам, которые нам никоим образом видны быть не могут, то есть, подчиняясь состоянию самой себя в будущем.
Если проводить аналогию с автоматом, то всё великое разнообразие начальных состояний (4096 без поворотов и отражений для крошечной доски 4x4) переходит всего в 2 (отбросим тривиальное) возможных следующих состояний, подчиняясь правилам, которые начинают действовать, только когда система уже находится в следующем состоянии. То есть, с точки зрения наблюдателя автомата, состояние его клеток меняется не то, чтобы хаотично, но каким-то совершенно непостижимым образом переходит в одно из двух «устойчивых» состояний, никак не зависящих от текущего состояния автомата. Такой сторонний наблюдатель никогда и ни за что не догадается, что правила всё-таки есть (они изложены выше), но правила эти таковы, что на следующее состояние автомата влияет оно само, а вовсе не текущее его состояние.
Говоря о принципе работы квантового компьютера, Дэвид Дойч задаёт вопрос: если квантовый компьютер совершает все эти вычисления, то откуда же он берёт ресурсы, если не из множества параллельных вселенных?
На этот вопрос можно ответить и по-другому: программа моего простейшего автомата тоже проводит огромные вычисления, чтобы определить возможный переход из одного состояния в другое; может быть, Вселенная тоже «проводит огромные вычисления», чтобы перейти в следующее состояние, подчиняясь правилам, которые станут релевантны для Вселенной в будущем, а не сейчас? И это и есть те самые ресурсы квантового компьютера.
Вот такие далеко идущие мысли родились из такой незатейливой идеи.