Пиксель. История одной точки

Фактически в 1928 году Гильберт предложил задаться вопросом, есть ли у простой логики прием, вроде ДНК-теста, систематически определяющий истинность утверждения без фактического вывода из очевидно истинных аксиом. Это называется Entscheidungsproblem Гильберта.

Это устрашающее слово в переводе с немецкого означает «проблема разрешения». Существует ли систематический способ определить истинность утверждений, выраженных в простой логике? Написание на немецком, безусловно, придает ему мистическую глубину, особенно для читателей, не владеющих этим языком. «Проблема разрешения» звучит как тема лекции для бизнес-школы, но Entscheidungsproblem предполагает Götterdämmerung — гибель богов, которая потрясет и обновит наш мир, — что на самом деле и произошло. Давайте называть ее e-Problem или е-Проблема, по аналогии с email, поскольку Entscheidungsproblem — это слишком длинно.

Макс Ньюман в 1934 году рассказал о е-Проблеме на лекции в Кембриджском университете. Говоря о том, что мы называем систематическим процессом, он использовал термин «механический процесс». Выбранные Ньюманом слова сыграли ключевую роль в нашей истории. Он мог бы сказать «систематический процесс», «эффективный процесс», «рецепт» или «алгоритм». Точных слов для самой концепции еще не существовало. Именно в этом и заключалась проблема.

Студент Алан Тьюринг присутствовал на этой лекции. Будучи чрезвычайным буквалистом, он попытался с помощью простой бумажной «машины» формализовать «механический процесс», о котором говорил Ньюман. Лектор, конечно, искренне удивился, что один из его студентов — такой молодой (всего 22 года), неуклюжий и заикающийся — нашел решение сложнейшей математической е-Проблемы лишь с помощью идеи простой механической машины. Конечно, Ньюман сначала не поверил, что такое возможно. Машина казалась игрушкой, а не серьезной математической концепцией. Столь важный математический результат не мог быть получен с помощью такого простого устройства. Но Ньюман быстро убедился, что полученные Тьюрингом результаты верны.

Тьюринг использовал свою концепцию — теперь мы называем ее машиной Тьюринга — для решения е-Проблемы. Во-первых, он изобрел машинные вычисления — именно их делают машины Тьюринга. Затем он использовал свою концепцию машинных вычислений — точное описание того, что мы подразумеваем под систематическим или механическим процессом, — для решения проблемы. Последовательность простых шагов в логических выводах очень похожа на последовательность тривиальных операций, которые выполняются компьютерами. В обоих случаях из примитивных отдельных шагов получается что-то осмысленное. Тьюринг первым формально соединил эти два понятия, что и сделало его богом математики.

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

Когда Тьюринг занимался е-Проблемой в Кембридже, в Принстонском университете в Нью-Джерси над ней работал Алонзо Черч. Американский математик защитил дипломную работу в Геттингенском университете примерно в то время, когда Гильберт объявил об Entscheidungsproblem. Черч фактически опередил Тьюринга — он нашел математическое доказательство неразрешимости на несколько месяцев раньше. По правилам академических кругов статус первооткрывателя и вся слава должны были достаться ему. Но техника решения Тьюринга разительно отличалась от техники Черча. В математике метод доказательства не менее важен, чем сам факт доказательства. Ньюман считал, что математический мир должен знать о новом методе Тьюринга.

Ньюман предложил Черчу признать вклад Тьюринга, и тот согласился. Они оба опубликовали свои работы в 1936 году, что стало важным шагом, поскольку именно интуитивная, механистическая и даже отчасти самодеятельная концепция программно-вычислительной машины Тьюринга, а не заумная формализация Черча (лямбда-определимость) вдохновила появление компьютеров. В своей опубликованной работе Тьюринг продемонстрировал, что обе концепции эквивалентны, но решение, сформулированное в виде воображаемой алгоритмической машины, имело совершенно иные последствия. Фундаментальная проблема математики, с которой справились оба ученых, не имеет особого значения для Цифрового Света, но вот техника решения Тьюринга — его машина — очень важна.