Статья 2454

При этом надо установить, насколько сложен последний. В клеточных автоматах соответствие между физическими и вычислительными процессами особенно велико. Клеточный автомат можно рассматривать как модель физической системы, а также и как вычислительную систему, аналогичную обычной цифровой вычислительной машине. Последовательность начальных значений клеток в клеточном автомате можно считать абстрактными данными, или информацией, подобно последовательности двоичных разрядов в памяти цифровой вычислительной машины. В ходе эволюции клеточного автомата информация обрабатывается, значения клеток изменяются в соответствии с определенными правилами. Точно так же разряды, хранящиеся в памяти цифровой вычислительной машины, изменяются по правилам, встроенным в центральный процессор вычислительной машины.
Эволюция клеточного автомата от некоторой начальной конфигурации может, таким образом, рассматриваться как вычисление, обрабатывающее информацию, которую содержит эта конфигурация. Для клеточного автомата, проявляющего простое поведение, вычисление тоже просто. Например, оно может состоять только в выборе последовательности трех клеток, начальные значения которых равны 1. Эволюции клеточных автоматов, ведущих себя сложным образом, должно соответствовать сложное вычисление.
Непосредственной имитацией каждого шага всегда можно определить итог данного числа шагов в эволюции клеточного автомата. Проблема состоит в том, чтобы установить, имеется ли более эффективная процедура. Можно ли вместо пошаговой имитации найти более короткий способ - некоторый алгоритм, который дает конечный результат после нескольких шагов в эволюции клеточного автомата, не проделывая в действительности каждый шаг. Такой алгоритм можно было бы выполнить с помощью вычислительной машины, и он бы предсказывал эволюцию клеточного автомата, не имитируя ее в явном виде.