Аннотация:
Рассматриваются одномерные клеточные автоматы, названные
ординарными, с минимальным числом состояний или числом соседних клеток.
Приводятся оценки моделирования поведения любых
одномерных клеточных автоматов ординарными. Доказывается существование
универсального
клеточного автомата с двумя состояниями и шестнадцатью соседними
клетками, моделирующего универсальную машину Тьюринга.
Библиогр. 5.
Полный текст:
PDF файл (315 kB)