|
Один момент из игры «Жизнь». В игре «Жизнь» каждый конечный автомат граничит с восьмью клетками, окружающими его в направлениях С, Ю, В и 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. АМЕРИКАНСКОЕ ПРИКЛЮЧЕНИЕВ августе 1936 года Алан Тьюринг направил для публикации в Proceedings of the London Mathematical Society статью под названием «О вычислимых числах, с приложением к проблеме разрешимости». Мы уже говорили о ней, так как именно в этой работе впервые упоминалась машина Тьюринга. Также в статье даются определения понятиям «вычислимое» и «невычислимое» и представлены фундаментальные идеи математики и информатики. По воле случая в том же году Алонзо Чёрч опубликовал в журнале American Journal of Mathematics статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером. — 23 —
|