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

В конце 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.

В августе 1936 года Алан Тьюринг направил для публикации в Proceedings of the London Mathematical Society статью под названием «О вычислимых числах, с приложением к проблеме разрешимости». Мы уже говорили о ней, так как именно в этой работе впервые упоминалась машина Тьюринга. Также в статье даются определения понятиям «вычислимое» и «невычислимое» и представлены фундаментальные идеи математики и информатики. По воле случая в том же году Алонзо Чёрч опубликовал в журнале American Journal of Mathematics статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером.

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

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

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

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

В этот период Тьюринг начал проявлять интерес к возможности создания своей машины, но эта цель так и не была достигнута. Именно во время пребывания в США проявился интерес ученого к hardware и, следовательно, к возможности создания с использованием электронных схем и электромеханических компонентов того, что еще недавно было не более чем интеллектуальным упражнением. И вновь, как и в случае появления идеи о машине Тьюринга на логическом уровне, мы сталкиваемся с тем, что ученый начал думать о реализации своей машины в эпоху, когда еще не было компьютеров. Он создал машину для умножения с использованием электромагнитных реле, которая позволяла умножать двоичные числа (то есть числа, которые можно представить с использованием только двух знаков: 0 и 1).

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

В августе 1939 года Тьюринг получил предложение работать в Блетчли-парке над расшифровкой перехваченных сообщений нацистов.

Глава 2

Машины против кода.

Вторая мировая война не была просто еще одной войной в истории человечества. В ней сражались и солдаты, и гражданские лица, и даже ученые. Соединенное Королевство подвергалось жесточайшим атакам нацистской Германии по морю и с воздуха. Британцы смогли победить врага, но для этого им пришлось привлечь к работе величайшие умы своей страны, среди которых был и Алан Тьюринг. Война способствовала появлению научных открытий, таких как ядерная энергия, и удивительных изобретений, таких как компьютер.

Битва за Атлантику, продлившаяся практически до последних дней Второй мировой войны, началась 3 сентября 1939 года. За этот период на театре военных действий были реализованы самые масштабные военные операции. На протяжении всего конфликта немецкие подлодки систематически атаковали британский торговый флот, затрудняя снабжение Британских островов. Во время Первой мировой войны также происходили неоднократные столкновения немецкого и британского флотов, но во Второй мировой войне сценарий операций кардинально изменился. Появился новый класс судов — субмарины, ставшие смертельным оружием против британцев, так что те вынуждены были формировать военное сопровождение для защиты торговых кораблей. Эта стратегия дала временный результат: немецкие подлодки тогда были очень медлительными, для осуществления выстрела им необходимо было подняться на поверхность, и в это время они становились легкой добычей. К концу войны Германия потеряла около 75 % своих подлодок. Однако действия немецкого подводного флота вызвали серьезные проблемы со снабжением Соединенного Королевства. Также с 1940 по 1941 год страна подвергалась серьезным бомбардировкам. Хотя их основной целью был Лондон, пострадали и другие города: погибло большое количество мирного населения и было разрушено более миллиона жилых домов.