Интересные примеры клеточных автоматов

[leshabirukov]

Про окружность очень понравилось. Не поделитесь ссылкой на источник? А то когда говорят а вычислении на КА подразумевают часто только разновидности автомата фон Неймана, а тут версия естественная и красивая.

[kriot]

www.intsys.msu.ru/science/books
В.Б. Кудрявцев, С.В. Алёшин, А.С. Подколзин. Введение в теорию автоматов. Изд-во «Наука», М., 1985, 320 с. (7-я в списке)
Про окружность написано на стр. 264, пункт 7.

[leshabirukov]

Спасибо, (и похоже она есть в подсобном фонде в Ленинке). Хотя вряд ли там есть какая-то методология, а не отдельные диковинки. Ещё кстати, вспомнился способ вычленения односвязной области методом «разливания краски». Вообще, неясно как в общем виде описывать задачи для решения на клеточном автомате. Алгоритмы общего вида натягивать на КА можно (автомат фон Неймана), но вряд ли стоит, хотя бы из-за присущих КА топологических ограничений. (Правда эти ограничения можно отчасти преодолеть, я вот использовал для комбинаторного компьютера автомат с древовидной топологией.) В моделировании КА используются, но это немного не то. Хотелось бы видеть больше изящных решений специального вида задач вроде приведённых в статье, может быть когда-нибудь метод разовьётся.