Поиск ближайшего соседа на прямой с помощью клеточного автомата с локаторами

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