Клеточные автоматы

[Bitman]

Игра “Жизнь” многим кажется заманчивой моделью, описывающей реальность. Главная причина этого, как мне видится, в том, что вселенная этой игры описывается набором целых (а не действительных) чисел. Это значит, что для описания этой вселенной, если она конечна, достаточно конечного набора информации (действительные же числа требуют, кажется, бесконечного объема информации).
Немецкий математик Леопольд Кронекер сказал: «Целые числа сотворил Бог, а всё прочее – дело рук человеческих».
Но конкретно у игры “Жизнь” есть следующие недостатки:
1) Там нет детерминизма. Точнее, там детерминизм направлен только в будущее – зная состояние вселенной в настоящее время, можно предсказать его состояние в любой момент будущего, но нельзя восстановить состояние в прошлом. Другими словами, с течением времени в этой вселенной теряется информация, и если бы в ней существовали разумные существа, они бы “помнили” только будущее;
2) Там нет законов сохранения импульса и энергии.
Можно ли придумать клеточный автомат, у которого нет этих недостатков? С детерминизмом уже достаточно ясно: если каждая клетка, например, просто меняет значение с 0 на 1 и обратно каждый ход, получается полный детерминизм.

[Весельчак Ы]

Можно ли придумать клеточный автомат, у которого нет этих недостатков?

Наверняка, можно, но даже физическая вселенная отнюдь не столь проста, как клеточный автомат (а о сложности реальности я уже недавно писал). Более того, Захар Гинзбург, исходя из метафизического априорного принципа простоты плана физической вселенной считает случайность в ней необходимой, см. его работы «Физик и небесная канцелярия», «Поэма о физике. Первая часть», «Записки студента-физика», «О математической сложности физических теорий» и «Философские заметки».

[Весельчак Ы]

Логично предположить что квантование всё-таки существует и для абсолютного точного описания вселенной (если она конечна) достаточно конечного (а не бесконечного) количества информации.

Кому логично, а кому и нет.

Главная причина этого, как мне видится, в том, что вселенная этой игры описывается набором целых (а не действительных) чисел. Это значит, что для описания этой вселенной, если она конечна, достаточно конечного набора информации (действительные же числа требуют, кажется, бесконечного объема информации).
Немецкий математик Леопольд Кронекер сказал: «Целые числа сотворил Бог, а всё прочее – дело рук человеческих».

Сейчас я уже не уверен в том, что Кронекер так считал, кажется, была какая-то история с этой цитатой. И другой немецкий математик Готфрид Вильгельм Лейбниц сказал: «Je suis tellement pour l’infinie actuel, qu’au lieu d’admettre, que la nature l’abhorre, comme l’on dit vulgairement, je tiens qu’elle l’affecte partout, pour mieux marquer les perfections de son Auteur». («Opera omnia studio Ludov. Dutens». Tom. II. part. I. p. 243.), что значит «Я в такой мере стою за актуальную бесконечность, что не только не допускаю, что природа боится ее, как обыкновенно выражаются, но и признаю, что природа всюду являет именно такую бесконечность, чтобы лучше отметить совершенство своего Творца». Эти слова стали эпиграфом к книге «Парадоксы бесконечного» (doc-версия) чешского математика Бернарда Плацидуса Иоганна Непомука Больцано.

[Bitman]

Сейчас я уже не уверен

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

[Весельчак Ы]

Скажите, ваше мнение меняется и сейчас ваша интуиция уже не так поддерживает идею, что клеточные автоматы служат хорошей моделью реальности?

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

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

Эх, что вы знаете о жизни! Прочитав статью в «Юном технике», я играл в неё еще лет 30-35 тому назад, пуговичками на клетчатой простыне. Вот немного старых материалов и программ о «Жизни». Рекомендую начать со статей Гарднера, а потом глянуть маленькую коллекцию конфигураций. А 2-го марта 2000 года Пол Ренделл анонсировал, что он построил Машину Тюринга в игре «Жизнь».

PS. Структуры складываются не из правил, а из элементов по заданным правилам.

[Нгаан]

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

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

[Н. Светлов]

можно, конечно, попробовать

установить AnyLogic PLE, изучить java…

[Нгаан]

Можно и java, хотя в похожие игры в своё время я играл и лепил в Borland C++ Builder.

Было у меня поле 50х50 клеток и были эти клетки двух типов: бактерия и еда. Бактерии имели четыре стадии жизни, а запасы еды были трёх уровней. Дальше можно было играться сколько душа пожелает, переделывая правила потребления и изменяя способ просмотра карты и так далее.
Хотя, несомненно, что профессиональные пакеты в этом смысле и полнее и гибче.

► Показать

Бактерии и еда рассеваются с помощью генератора случайных чисел. Потом они начинают жить. Если рядом с бактерией есть определённое количество еды, то она живёт и здоровеет, а потом делится и заселяет соседнюю свободную клетку. Если еды недостаточно, то бактерия начинает хиреть, умирает и превращается в еду. По умолчанию поле жизни является бесконечным, то есть правый крайний столбец смыкается с левым крайним столбцом, а самая верхняя строка смыкается с самой нижней строкой. Но можно поле жизни разомкнуть по одной координате (столбцы не смыкаются или строки не смыкаются - игра на цилиндрической форме). Можно разомкнуть поле одновременно по обеим координатам, тогда просмотр идёт на плоском (квадратном) поле. В ходе экспериментирования в программе можно задавать некоторое количество циклов жизни и смотреть как распределяются волны жизни по полю. Минимальное количество циклов жизни в проходе 1. Тыкаешь кнопочку "Жити" (Жить) и смотришь, что получается.

[visor]

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

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

[Н. Светлов]

Там нет детерминизма.

Тут его тоже нет.

Даже если закрыть глаза на квантовую механику - если некий шар, катясь по совершенно горизонтальной плоскости, остановился в точке x, фиг Вы установите, откуда он прикатился. При переходе от v ≠ 0 к v = 0, где v - вектор-градиент скорости-направления, информация о направлении движения тоже теряется.

если бы в ней существовали разумные существа, они бы “помнили” только будущее

Память - это не только дедукция от настоящего в прошлое. Фотография - ни разу не дедукция.

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

Какая модель вселенной, вы что.

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

[Bitman]

Было у меня поле 50х50 клеток и были эти клетки двух типов: бактерия и еда.

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

[Нгаан]

Я выше написал простой вариант

Другими словами, с течением времени в этой вселенной теряется информация, и если бы в ней существовали разумные существа, они бы “помнили” только будущее;

Вообще не понимаю о чём вы говорите? Помнить будущее?

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

Про память в системах с квазинепрерыными состояниями я вообще молчу. Там без ста граммов перцептронов тем более не разобраться.

Снабдить клеточный автомат памятью можно по аналогичной схеме. Глубина этой памяти будет зависеть от того каков объём запоминающего устройства. Можно увеличить объём памяти с учётом сжатия информации, но при этом следует учитывать, что сжатая информация требует времени на разжимание и потому инерционность системы в целом, то есть её способность "разумно" реагировать на быстроменяющиеся внешние воздействия, снижается.

► Показать

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

[visor]

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

Доля истины в этом есть. Каждая частица меняет своё состояние при взаимодействии с другой частицей. И это на всех уровнях масштаба. Сложность в том, что каждая частица - часть целого.
А проблема "памяти" в Вашем случае связана с проблемой энтропии.
Теряется ли информация/история с увеличением энтропии? Если бы поведение частиц описывалось механическими законами, то, наверное, имея супер-вселенский компьютер, можно было бы, затратив энергию Большого взрыва, рассчитать исходное состояние системы по текущему состоянию. Но ведь в микромире в событиях есть большая доля квантомеханической случайности. Может быть и в этом случае можно - не знаю.
Но я придумал, куда записывается история системы! Это скрижали бытия!!! Тепловая энергия - следствие работы системы охлаждения этих скрижалей.

[Нгаан]

Это скрижали бытия!!! Тепловая энергия - следствие работы системы охлаждения этих скрижалей.

Отличный термин и аналогия хорошая, брат Визор.

Скольжение резца по скрижалям происходит с трением. Тут даже можно предположить, что тёмная материя - это отходы в процессе резки.

[Bitman]

Вообще не понимаю о чём вы говорите? Помнить будущее?

А что такое "память" вообще?
Вот мы, находясь в настоящем, имеем определённую информацию о нашем прошлом и определённую информацию о нашем будущем. Вроде о прошлом у нас больше информации, хотя это тоже надо проверять. Информация о прошлом и будущем имеет разный характер. Наверно можно сказать что информация о прошлом более конкретна и более достоверна, например мы точно знаем, что в 1000 году не было падения на Землю астероида, но мы не можем настолько же достоверно утверждать, что в 3000 году падения астероида не будет.
Аналогично рассуждая, во вселенной игры "Жизнь", зная настоящее, можно точно сказать что через столько-то ходов состояние системы будет таким-то, а вот сказать, каким было состояние на столько-то ходов назад в прошлое - уже точно не получится.

[Нгаан]

имеем ... определённую информацию о нашем будущем.

Если под этим подразумевать "вероятностный прогноз на основе статистических данных", то да. Достоверность этой "информации" весьма своеобразна и прогноз погоды тому отличный пример.

Наверно можно сказать что информация о прошлом более конкретна и более достоверна

Если она записана в "скрижалях" независимым наблюдателем, что характерно исключительно для объективных природных процессов и то не всех. Социальная информация искажается при записи ежедневно и даже ежесекундно. Информация в биологических системах записывается значительно чаще, чем считывается: из тысячи семян прорастёт только одно.

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

[Нгаан]

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

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

О чём-то подобном и пытался сказать вам проф:

если некий шар, катясь по совершенно горизонтальной плоскости, остановился в точке x, фиг Вы установите, откуда он прикатился. При переходе от v ≠ 0 к v = 0, где v - вектор-градиент скорости-направления, информация о направлении движения тоже теряется.

[Н. Светлов]

► Показать

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

Вообще говоря, это не всегда верно. Разработка для случая, когда цель сформулирована неопределённо, возможна: для того и придуман системный анализ (Н.Н. Моисеев, «Математические задачи системного анализа», гл. II, §1, с.64; §2, с.70-76). Говоря совсем грубо и опустив приёмы, позволяющие упростить и ускорить решение задачи, суть дела сводится вот к чему: разработать что-нибудь исходя из примерного понимания терминов, упоминаемых в спойлере; посмотреть, как оно работает; оценить разницу между желаемым и наличным; вернуться к фазе разработки (попутно немного уточнив смысл терминов). Далее repeat { } until ( );

<Спор о словах>

А что такое "память" вообще?

Обычно под памятью понимают переменные (ячейки, если хотите) моделируемой системы, состояние которых гомоморфно состоянию системы и её среды в определённые моменты прошлого.

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

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

</Спор о словах>

[Нгаан]

разработать что-нибудь исходя из примерного понимания терминов, ... посмотреть, как оно работает;

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


В терминах клеточного автомата понятие "вселенная" вполне конкретно: поле 50х50 с определёнными свойствами каждой клетки и поля в целом это и есть "вселенная". Если система расширяемая, может в какой-то момент при каких-то условиях стать полем 100х100 клеток, это тоже "вселенная". Чего система не может в силу внутренних ограничений и в соответствии со своими внутренними правилами, это не есть "вселенная".

[Bitman]

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

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