Пиксель. История одной точки - Элви Рэй Смит

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

Поставленная Гильбертом задача предполагала поиски алгоритма решения, а не самого вывода. Он не требовал, чтобы в результате систематического процесса действительно из аксиом выводилось утверждение, а требовал, чтобы точно определялась возможность или невозможность вывода. Различие кажется несущественным. Если вы можете определить истинность утверждения, зачем показывать, как оно получено из аксиом? Однако это принципиально важно.

Сегодня научная генеалогия позволяет узнать, что, скажем, Джозеф, живший в XVIII веке, был прямым предком ныне живущего Якова; формально отслеживать родственные связи от отца к сыну — поколение за поколением — при этом не требуется. Если у них одинаковые ДНК на Y-хромосоме (мужской), что легко подтверждается простым лабораторным тестом, значит, они связаны по мужской линии. Путь между ними должен существовать. Но знание о его существовании совсем не похоже на конкретный перечень мужчин, передавших конкретную ДНК своему потомку, то есть на то, что довольно трудно установить документально. Однако наличие такого знания может побудить вас приложить усилия для поиска фактического пути, ведь вы будете уверены, что не потратите время впустую.

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

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

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

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

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

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

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

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

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

Не только Тьюринг формализовал понятие систематического процесса. Как мы уже видели, то же самое