С. В. Гаврилов, И. В. Матюшкин, А. Л. Стемпковский, “Вычислимость в клеточных автоматах”, Искусственный интеллект и принятие решений, 2016, выпуск 1,страницы 18

Эта публикация цитируется в 2 статьях

Интеллектуальные системы и технологии

Вычислимость в клеточных автоматах

С. В. Гаврилов^a, И. В. Матюшкин^b, А. Л. Стемпковский^a

^a Институт проблем проектирования в микроэлектронике РАН, г. Зеленоград
^b АО «Научно-исследовательский институт молекулярной электроники»

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

Ключевые слова: клеточные автоматы, вычислимость, сигнал, сортировка, параллельное умножение, алгоритм Атрубина, машина Тьюринга, времяконструируемость.