Статья 2455

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