О структуризации класса обратимых клеточных автоматов

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