Нечасто гипотетические механизмы, существовавшие только в воображении автора, становились фундаментом грандиозных перемен. Машине Тьюринга, абстрактной математической модели алгоритмов, это удалось в полной мере, а 24‑летний британский математик, фактически предсказав устройство и логику всех ­вычислительных машин нашего времени, невольно стал отцом информационных технологий, полностью изменивших мир.

Эта статья была опубликована в журнале OYLA №9(37). Оформить подписку на печатную и онлайн-версию можно здесь.

Наша жизнь буквально пронизана всевозможными инструкциями и алгоритмами, ведь если вдуматься, жизненный опыт — это сумма усвоенных алгоритмов: чем их больше, тем легче в разных условиях добиться желаемого результата. А большая часть физио­логических процессов в нашем теле, таких как дыхание и пищеварение, настолько автоматизированы, что организм выполняет их с точностью прописанной программы. Не делает ли это нас подобием машин? От этой мысли совсем недалеко до принятия концепции детерминизма. Согласно ей, мир — это сложная, но всё же машина, работающая на основе простых физических законов. Следовательно, взаимодействие этих машин подчинено причинно-следственной связи: зная совокупность причин, можно однозначно предсказать исход события. Например, если говорить о движении небесного тела вокруг звезды, то, зная массу, начальную скорость объектов и всемирный закон тяготения Ньютона, можно с большой точностью предсказать местоположение этого объекта в любой момент его существования.

Подобных взглядов придерживался великий французкий математик Пьер-Симон Лаплас. В 1814 году, описывая мысленный эксперимент, он предложил представить гипотетическое существо (наречённое позже демоном Лапласа), способное абсолютно точно предсказать все события во Вселенной на основе знания о положении и скорости всех её частиц. Приведём рассуждение учёного:

«Мы можем рассматривать настоящее состояние Вселенной как следствие его прошлого и причину его будущего. Разум, которому в каждый определённый момент времени были бы известны все силы, приводящие природу в движение, и положение всех тел, из которых она состоит, будь он также достаточно обширен, чтобы подвергнуть эти данные анализу, смог бы объять единым законом движение величайших тел Вселенной и мельчайшего атома; для такого разума ничего не было бы неясного и будущее существовало бы в его глазах точно так же, как прошлое».

Лаплас предполагал, что Демон будет оперировать законами классической механики. Но последующие открытия в физике показали, что законы Вселенной намного сложнее механики Ньютона. Термодинамическая необратимость и законы неопределённости в квантовой механике опровергают даже гипотетическую возможность существования Демона. Из чего следует, что наш мир не настолько детерминирован. Несмотря на это, именно детерминизм оказал сильнейшее влияние на научный метод, ведь он подталкивал учёных искать первопричину тех или иных явлений.

Спустя столетие подобными вопросами задался кембриджский студент Алан Тьюринг. Ещё в школьные годы он решал сложные математические задачи и самостоятельно освоил такие непростые дисциплины, как дифференциальное и интегральное исчисления. Математика стала его истинной страстью, и Тьюринг с радостью вступил в ряды её ревностных служителей. С наставником Алану тоже повезло: им вызвался быть талантливый математик Годфри Харди, видевший в древней науке такую же красоту, как на полотнах Леонардо и в сонетах Шекспира. Кстати, Харди считал своим величайшим достижением не работы по теории чисел, а открытие миру гениального индийца Сринивасы Рамануджана, который самостоятельно, без специального образования и общения с профессорами, дошёл до вершин математической науки.

Вернёмся к Тьюрингу. С таким замечательным наставником Алан всё чаще вспоминал отрывок из прочитанной в детстве книжки популяризатора науки Эдвина Тенни Брюстера ­«Чудеса природы, о которых должен знать ребёнок»:

«Человеческое тело представляет собой машину. Очень замысловатую машину с гораздо, гораздо более сложным устройством, чем у любой другой, созданной человеком, но всё-таки машину».

В машине теоретически можно определить всё: количественное взаимодействие частей, поведение в прошлом, настоящем и, главное, в будущем. Кроме того, раз можно рассчитать все мыслимые параметры для одной машины, то почему бы не сделать это для десятка? Для миллиона? Триллиона, наконец? Вспомним детерминизм Лапласа.

На практике дело упирается лишь в вычислительную мощь устройства расчёта и необходимое для него время. А что мы понимаем под словом «расчёт»? Формально это последовательность некоторых операций над некими символами (числами и буквами). Причём заданная последовательность операций — не что иное, как алгоритм. Например, нам необходимо рассчитать значение функции f(x, y) = x²+ y² для некоторых x и y. Мы видим следующие символы: x, y, 2, +. И два вида операций: возведение в квадрат и сложение. А ведь все действия, подумал Тьюринг, в конечном счёте сводятся к нескольким элементарным: считать символ, произвести операцию, записать результат и перейти к следующему действию. Все эти расчёты умела делать машина Тьюринга, более того, на её базе можно было составлять алгоритмы. Хотя Тьюринг описывал свою машину как абстрактную, она имеет достаточно механическое воплощение. Об этом и поговорим далее.

На идею о механизме Тьюринга натолкнула пишущая машинка. Казалось бы, при чём здесь машинопись? Не вдаваясь в детали конструкции и особенности привода (ручного или электрического), пишущая машинка — это устройство работы с символами: буквами, цифрами, знаками препинания и т. д. На каждое нажатие клавиши она отвечает строго определённым образом, переходя в одно из возможных состояний — верхний или нижний регистры, соответствующие прописным или строчным буквам.

К моменту набора очередного символа оператор сравнивает текущее и необходимое состояние устройства. Если они совпадают, то всё в порядке, если же нет — от оператора требуется перевести машину в другой регистр. Элементарно? Конечно! Но вот что интересно: можно было совершенно точно сказать, в каком состоянии будет находиться старенький, но исправный «ремингтон» в момент, когда напечатают последний символ текста.

А что, если объединить оператора и пишущую машинку в автоматического исполнителя алгоритмов? Ведь на базовом уровне всё соответствует: обрабатываемые символы, алгоритм действий, разные состояния. А ещё каретка машинки могла перемещаться и печатать символы в любом месте листа, то есть устройство срабатывало в произвольной, но корректной в заданных условиях позиции. Механизм, придуманный Тьюрингом, был аналогом пишущей машинки, но более универсальным и не требующим присутствия и вмешательства человека. Гипотетический агрегат обладал заданным числом конфигураций-состояний и однозначно (это важно) срабатывал в каждом из них.

Лента. Чтобы не распыляться на технические детали вроде валика для протяжки бумаги, Тьюринг для своей машины выбрал простейший вариант: рабочая поверхность представляла собой бесконечную ленту, разбитую на клетки, в каждую из которых впечатывается (или стирается) один символ. На этой ленте изначально записывается некоторое выражение, которое требуется рассчитать. То есть она используется для хранения информации.

Каретка. Каретка свободно перемещается влево и вправо на неограниченное количество позиций. Существенное отличие от пишущей машинки заключалось в том, что каретка могла «сканировать» (по выражению самого Тьюринга) информацию в клетке и при необходимости стирать её. Обработав ячейку, каретка смещается на следующую позицию.

Машина Тьюринга — агрегат «умный», обходится без помощи человека. В зависимости от комбинации отсканированного символа и собственной конфигурации (помните регистры у пишущей машинки?) она выполняет следующие действия:

1. записывает новый символ в пустую ячейку;
2. оставляет уже записанный символ нетронутым;
3. стирает символ и оставляет ячейку вакантной;
4. сохраняет собственную конфигурацию или меняет её на заданную ранее;
5. перемещается на ячейку влево или вправо либо остаётся на месте.

В результате по заданному на ленте набору символов машина Тьюринга должна выдать некий результат и прекратить работу.

Давайте создадим машину Тьюринга, которая будет складывать два натуральных числа N и M, а результат, как и исходные числа, — записывать на ленте в виде последовательности единиц. Каретка находится в самой левой части ленты (в месте, обозначенном как ↓).

Для наглядности приведём пример результата работы машины Тьюринга для задачи 4 + 3 = 7:

Все состояния машины можно занести в таблицу-инструкцию. Машина начинает ­работу с состояния q₀ и заканчивает в состоянии q₅.

Что может «увидеть» каретка в состоянии q₀? Скорее всего, 1, так как мы складываем два ненулевых числа. Следовательно, машина должна выполнить команду 0→ q₁: перезаписать значение этой клетки на 0, сдвинуть каретку на одну позицию вправо (→) и перейти в состояние q₁. В следующем состоянии каретка может «увидеть» либо 1, либо + , для каждого из этих значений есть соответствующее действие. Попробуйте самостоятельно проверить работу этой программы для произвольных чисел.

Поменяйте что-нибудь в таблице — и вы получите другую машину! А так как изменения можно вносить бесконечно, то и машин будет множество. Правила перехода можно сделать такими, что машина Тьюринга превратится в универсальный автомат, способный выполнять арифметические операции, искать определённые символы, вычислять тригонометрические функции, наконец, останавливать работу, достигнув так называемой терминальной конфигурации. Такой «всеядности» способствует простейшее обстоятельство: цифры тоже символы, а значит, машине Тьюринга подвластны не только буквы, но и сложнейшая математика.