Одной из самых интересных задач является возможность создать машину Тьюринга, используя другую машину — игру «Жизнь». Этот автомат был придуман в 1970 году Джоном Хортоном Конвеем (р. 1937), профессором Кембриджского университета, где учился и Тьюринг. Речь идет о модели компьютера, которая была очень популярна среди любителей науки, особенно после того, как ее описал популяризатор математики Мартин Гарднер (1914-2010) в журнале Scientific American. Игра представляет собой клеточный автомат, то есть двумерную решетку, клетки которой заполнены конечными автоматами, также известными как машины конечных состояний. Речь идет об объекте, находящемся в одном из множества состояний, при этом данное множество конечно. Например, светофор может находиться в течение некоторого времени t в состоянии «зеленый», то есть в одном из трех возможных (красный, желтый, зеленый). Другой пример — нейрон, который может находиться в состоянии покоя или возбуждения. В машине Тьюринга, использующей для моделирования клеточный автомат, с течением времени (ί) состояния каждого конечного автомата обновляются. Обновление или расчет, каким будет состояние в следующий отрезок времени (£ + 1), происходит в соответствии с набором правил, известных как правила перехода, меняющие состояние каждого конечного автомата с учетом его актуального состояния и состояний соседних автоматов.
В конце XX века несколько ученых и любителей науки задались вопросом: можно ли построить машины Тьюринга с помощью игры «Жизнь»? Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Возможность моделирования машины Тьюринга с помощью игры «Жизнь» привела к удивительному выводу: игра «Жизнь» имела аналогичные с компьютером возможности. Более того, любое природное явление, например формирование колец Сатурна или взаимодействие зайцев и волков, можно смоделировать с помощью компьютера. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.
Один момент из игры «Жизнь».
В игре «Жизнь» каждый конечный автомат граничит с восьмью клетками, окружающими его в направлениях С, Ю, В и 3, а также по диагонали: С-В, Ю-В, Ю-3 и С-3. Считается, что для всех конечных автоматов возможны только два состояния: состояние 0 («мертвые клетки») и состояние 1 («живые клетки»); каждому из них соответствует свой цвет. Состояния конечных автоматов актуализируются с применением следующих правил перехода.
— Правило 1: если состояние конечного автомата αtij 0 или 1, его следующее состояние, а именно αt+1ij, будет таким же, как предыдущее, если количество соседних клеток в состоянии 1 равно 2:
αt+1ij = αtij, если сумма соседних клеток (αtij) = 2.
— Правило 2: конечный автомат перейдет в состояние 1, если количество соседних клеток в состоянии 1 равно 3, изменение состояния автомата произойдет только при условии, что его состояние было 0 во время t. В противном случае состояние останется равным 1:
αt+1ij = 1 если сумма соседних клеток (αtij) = 3.
— Правило 3: описывает изменения при разном количестве соседних автоматов, находящихся в состоянии 1. Если количество автоматов рядом в состоянии 1 меньше 2 (то есть один или ни одного) или более 3 (четыре, пять, шесть, семь или восемь), конечный автомат «умирает», принимая значение 0. В этом случае изменение состояния происходит, только если во время t его состояние было 1, в противном случае состояние не будет изменено и останется равным 0:
если сумма соседних клеток (αtij) < 2
αt+1ij = 0
или сумма соседних клеток (αtij) > 3.
При каждой итерации и применении правил перехода к каждому конечному автомату клеточный автомат эволюционирует, при этом появляются рисунки, характерные для данной игры. Образующиеся формы до сих пор вызывают восхищение среди компьютерных любителей. Существует большой выбор программ, позволяющих попробовать игру «Жизнь» (Life32, Xlife 2.0, Life 1.05/1.06, Pro Life, Mcell, dbLife и другие), из них самой впечатляющей является Golly.