Примеры клеточных автоматов, которые выполняют задачи реального мира

Question

Я читал об одномерных клеточных автоматах и ​​заинтригован идеей, что они могут решать реальные проблемы.

Однако я не нашел ни одного примера.

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

Вместо этого я говорю о чем-то измеримом. Есть ли пример, который добавляет? Умножение? Шаблон-спички?

Или автоматы, которые выполняют такие вещи, требуют ошибок специальных правил, которые нарушают простоту концепции?

Answer 1

Этот компьютер WireWorld вычисляет простые числа:

http://www.quinapalus.com/wi-index.html

Answer 2

Я использую клеточных автоматов для создания очень интересные фрактальной искусства:

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

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

Answer 3

Отъезд http://is.ifmo.ru/english/ (Большая часть сайта на русском языке, вы можете использовать автоматический перевод, я полагаю.) Я знаю профессора Шалыто лично. Он много лет проводил исследования различных применений конечных автоматов, в том числе клеточных автоматов. В частности, он работал со многими очень яркими учениками в области информатики, возможно, одним из самых ярких в России, и они создали множество различных проектов, используя конечные автоматы различными способами для решения реальных задач.

Профессор Шалыто сделал некоторые другие очень полезные вещи, в том числе его усилия по продвижению открытой проектной документации, а также его настойчивость в поддержке обучения информатике в России. Однако, что касается конечных автоматов, я убедился, что они хороши для ничего практичного, кроме, может быть, программирования компилятора, транзакций ATM, контроля производственных процессов на крупных заводах и ряда других приложений ниши. Кроме того, что касается клеточных автоматов, я убедился, опять же, наблюдая за усилиями проф. Шалыто и его много талантливых учеников, что они (клеточные автоматы) в основном хороши ни для чего. Кроме, конечно, их математической красоты.

Answer 4

Вдохновленный работой Стивена Вольфрама по клеточным автоматам в начале 1980-х годов, произошел всплеск интереса к прикладному использованию алгоритмов СА. До того, как интерес закончился примерно через десять лет, было опубликовано немало статей, в которых показано, как CA (обычно 1-D, двоичный) может использоваться для генерации псевдослучайных последовательностей, кодов коррекции ошибок, криптографии, тестирования FSM, обработки сигналов и куча других вещей. Однако эти статьи были, как правило, просто математическими эскизами, и есть мало кода, который вы могли бы выкопать, чтобы посмотреть.

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

Вы сказали, что вас не интересуют симуляции, но если вы хотите увидеть CA, используемую в значительном приложении реального мира, посмотрите на моделирование потоков трафика. Вероятно, это область, в которой методы CA стали ближе всего к принятию в качестве полезного инструмента. Ознакомьтесь с главой 13 в последней книге, Traffic Flow Dynamics: Data, Models and Simulation.