Rafael Lahoz-Beltra - Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Один момент из игры «Жизнь».

В игре «Жизнь» каждый конечный автомат граничит с восьмью клетками, окружающими его в направлениях С, Ю, В и 3, а также по диагонали: С-В, Ю-В, Ю-3 и С-3. Считается, что для всех конечных автоматов возможны только два состояния: состояние 0 («мертвые клетки») и состояние 1 («живые клетки»); каждому из них соответствует свой цвет. Состояния конечных автоматов актуализируются с применением следующих правил перехода.

— Правило 1: если состояние конечного автомата α t ij0 или 1, его следующее состояние, а именно α t+1 ij, будет таким же, как предыдущее, если количество соседних клеток в состоянии 1 равно 2:

α t+1 ij =α t ij, если сумма соседних клеток (α t ij) = 2.

— Правило 2: конечный автомат перейдет в состояние 1, если количество соседних клеток в состоянии 1 равно 3, изменение состояния автомата произойдет только при условии, что его состояние было 0 во время t. В противном случае состояние останется равным 1:

α t+1 ij= 1 если сумма соседних клеток (α t ij) = 3.

— Правило 3: описывает изменения при разном количестве соседних автоматов, находящихся в состоянии 1. Если количество автоматов рядом в состоянии 1 меньше 2 (то есть один или ни одного) или более 3 (четыре, пять, шесть, семь или восемь), конечный автомат «умирает», принимая значение 0. В этом случае изменение состояния происходит, только если во время t его состояние было 1, в противном случае состояние не будет изменено и останется равным 0:

если сумма соседних клеток (α t ij) < 2

α t+1 ij= 0

или сумма соседних клеток (α t ij) > 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 статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером.

Месяц спустя, в сентябре 1936 года, Тьюринг отправился в США. Там он планировал получить докторскую степень и провести два года в Институте перспективных исследований в престижном Университете Принстона. Под руководством Алонзо Чёрча Тьюринг обратился к теме, странной даже сегодня — использованию в математике интуиции. Не теряя времени на философские объяснения, скажем, что интуиция может быть определена как продукт здравого смысла. То есть речь шла о предвосхищении или ментальном видении, которое помогает нам при рассуждениях прийти к умозаключению. Учитывая, что в ходе рассуждений мы связываем факты в логическую цепь, интуиция представляет собой дополнительный компонент, необходимый для разрешения задачи.

Математическое рассуждение схематично можно рассматривать как упражнение в комбинировании двух факторов — интуиции и изобретательности.

Алан Тьюринг, «Логические системы, основанные на ординалах»

Тьюринг предполагал, что человеческая интуиция возможна благодаря неким процессам, которые не могут быть выражены в виде алгоритма. Эти «внеалгоритмические» этапы включены в ход рассуждения, помогают обнаружить взаимосвязь фактов и прийти к умозаключению. Интуиция присутствует не только в математике — и врач, и автослесарь в момент диагностики пользуются ею.