Изменения

'''Линейным клеточным автоматом''' (ЛКА) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,находящихся на расстоянии не более <tex>r</tex> от данной.}} ==Другое определение линейного клеточного автомата=={{Определение|definition='''Линейным клеточным автоматом''' <tex>A</tex> назовем пару <tex>\{ \}</tex>}}{{Утверждение|statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.|proof=Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как <tex>D</tex>. Построим автомат <tex>B</tex> следующим образом: множеством вершин B будет объединение множеств вершин автоматов из <tex>D</tex>, переходы между вершинами <tex>u</tex> и <tex>v</tex> будет совпадать с переходами <tex>D_i</tex>, если <tex>u</tex> и <tex>v</tex> соответствуют вершинам из <tex>D_i</tex>, иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата <tex>D_k</tex>, который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением <tex>D_k</tex>.