Том 9, серия 1, номер 4 , 2002 г., Стр. 50-56
УДК 519.713
И. И. Захарчук
О сложности одномерных универсальных клеточных автоматов
Аннотация:
Рассматриваются одномерные клеточные автоматы, названные ординарными, с минимальным числом состояний или числом соседних клеток. Приводятся оценки моделирования поведения любых одномерных клеточных автоматов ординарными. Доказывается существование универсального клеточного автомата с двумя состояниями и шестнадцатью соседними клетками, моделирующего универсальную машину Тьюринга.
Библиогр. 5.
Захарчук И. И. 1
1. Военный инженерно-космический университет им. А. Ф. Можайского,
Ждановская наб., 13, 197082 Санкт-Петербург, Россия
е-mail: vlars-i3@mail.ru
Статья поступила 9 июля 2002 г.
