436
правок
Изменения
Classification fixed
= Классификация клеточных автоматов =
== Классификация Вольфрама ==
{{Определение
# Поведение сложное, во многих отношениях выглядит хаотическим;
# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.
== Классификация Эпштейна ==
Д. Эпштейн в работе<ref name="eppstein">Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html</ref> резко критиковал классификацию С. Вольфрама, в частности, назвал её совершенно несостоятельной из-за невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>
Для решения проблемы он предложил свою классификацию двухмерных двоичных клеточных автоматов на основе возможностей порождаемых клеточным автоматом объектов к расширению и уменьшению.
Классы, предложенные Д. Эпштейном<ref name="skakov" />:
# Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит в состояние 1, если она имеет ровно одного соседа в состоянии 1);
# Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1, если она имеет ровно двух / трёх соседей в состоянии 1).
# Уменьшение невозможно: в наборе правил есть правила S01234 или B23/S0 (клетка сохраняет состояние 1, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 и сохраняет это состояние, если у неё нет соседей в состоянии 1).
# Возможны и расширение и уменьшение объектов: все остальные случаи.<br>Однако, данная классификация так же не лишена недостатков, в частности не удовлетворяет поставленным перед ней же требованиям: целью данной классификации является выделение кандидатов в универсальные клеточные автоматы. Эпштейн утверждал, что универсальные клеточные автоматы могут принадлежать только к классу 4, однако, существует<ref name="skakov" /> универсальный клеточный автомат, относящийся к классу 3 по данной классификации. Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова<ref name="skakov" />. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы.
= Одномерные клеточные автоматы =
