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

Алан Тьюринг в письме английскому математику Робину Гэнди

В 1931 году Алан Тьюринг стал студентом математики Королевского колледжа Кембриджского университета. С этих пор он отдалился от старшего брата Джона, который занялся адвокатской практикой в Лондоне. К счастью для Алана, университет был для него более подходящим местом, чем школы, в которых он успел поучиться: в Кембридже он попал в интеллектуальную среду, необходимую для развития его способностей. Свободное время Тьюринг посвящал занятиям спортом — бегу и гребле. Что касается его академических интересов, то после прочтения работы Джона фон Неймана о логических основах квантовой механики внимание Алана привлекла математическая логика. Известно, что он также прочел книгу Бертрана Рассела (1872-1970) «Введение в философию математики» (Introduction to mathematical philosophy, 1919) и знаменитый трехтомник «Принципы математики» (Principia mathematical 1910-1913), написанный Расселом совместно с Альфредом Нортом Уайтхедом (1861-1947). Без сомнения, эти работы повлияли на интеллектуальное созревание личности будущего ученого.

Алан Тьюринг в 1928 году в возрасте 16 лет.

Здесь родился Алан Тьюринг, 1912-1954, криптограф, пионер информатики. Надпись на одной из пяти синих табличек, размещенных на разных зданиях Соединенного Королевства, где жил Тьюринг.

Королевский колледж Кембриджского университета.

Однако наибольшее влияние на Тьюринга оказал Курт Гёдель (1906-1978), особенно его знаменитая статья, опубликованная в 1931 году и посвященная теоремам о неполноте. Эта работа подтолкнула молодого человека к изобретению машины Тьюринга, которая могла определять, какие математические функции могут быть вычислены, а какие нет. Если функцию возможно вычислить, машина через определенный промежуток времени, который, по словам другого великого математика, Давида Гильберта (1863-1943), должен быть конечным, выдаст результат. Напротив, если функция невычислима, машина будет производить операции без остановки. По мнению Ходжеса, Тьюринг был более философом, чем математиком, что и объясняет его интерес к проблемам математической логики. Ученый, возможно, сам не осознавая этого, внес большой вклад в создание теоретических основ информатики, причем сделал это задолго до того момента, когда компьютер стал реальностью.

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

В 1934 году Тьюринг закончил обучение в университете, получив диплом математика. В следующем году ему предоставили двухгодичную стипендию Королевского колледжа, входящего в Кембриджский университет. В этот период можно наблюдать первые вспышки его гениальности. В 1936 году Тьюринг получил премию Смита (в Кембридже ее присуждают молодым исследователям по теоретической физике, математике или прикладной математике) за работу по теории вероятностей под названием «О функции ошибок Гаусса» (On the Gaussian error function) — она не была опубликована. Любопытно, что в этом исследовании была заново открыта знаменитая центральная предельная теорема, одна из основных теорем статистики. В том же году Тьюринг написал научную статью, озаглавленную «О вычислимых числах, с приложением к проблеме разрешимости» (On computable numbers with an application to the Entscheidungsproblem), в которой описано его важнейшее научное достижение — машина Тьюринга. Эти труды обеспечили академическое будущее ученого и стали его первыми шагами к блестящей карьере.

Весной 1935 года Тьюринг посещал в кампусе Кембриджского университета, стипендиатом которого он был, курс Макса Ньюмана (1897-1984), знаменитого тополога, и у них завязалась долгая дружба. Топология — раздел математики, изучающий свойства объектов, которые остаются неизменными при непрерывных трансформациях. Тьюринг общался с Ньюманом в течение всей своей жизни, и это было чрезвычайно полезным для обоих с научной точки зрения. Во время Второй мировой войны они вместе работали в Блетчли-парке над расшифровкой перехваченных немецких сообщений, а позже в Манчестерском университете создавали программы для Baby, одного из первых послевоенных компьютеров.

В Кембридже Тьюринг смог принять участие в одном из самых интригующих этапов развития науки. Британский философ и математик Бертран Рассел утверждал, что логика является основополагающей при установлении математической истины. Эта идея была ключевой в его книге Principia mathematica, написанной незадолго до этого совместно с философом Уайтхедом. Если математика могла быть интерпретирована с точки зрения логики, в таком случае ничто не препятствовало ее сведению к основам логики. Одновременно, в начале 1930-х годов, другой философ и математик, Курт Гедель, уроженец Брно (этот город сегодня входит в состав Чехии, а в то время был частью Австро-Венгерской империи), установил в математике знаменитый философский принцип. Он ввел теорему о неполноте, которую можно представить как идею о том, что существуют неразрешимые математические выражения, или утверждения, которые не могут быть ни доказаны, ни опровергнуты. В общем случае эти утверждения могут быть истинными или ложными. Например, если кто-нибудь скажет, что «2 + 3 = 5», мы заметим, что это утверждение истинно. На математическом языке мы бы выразили это так:

А = [2+3=5] => [А истинно]

С другой стороны, если кто-то предложит утверждение «2∙3 = 8», мы скажем, что это утверждение ложно:

В = [2∙3=8]=> [В ложно]

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

Гедель перенес этот парадокс из языка в математику, в частности в сферу логики, доказав в 1931 году теорему о неполноте, описывающую неполные системы, истинность или ложность утверждений которых мы не можем установить. Невероятно захватывающим представляется вопрос о том, как эти философские рассуждения, па первый взгляд далекие от реального мира, заставили поколебаться основы математики.

Представьте, что мы выражаем на математическом языке следующее утверждение G:

G = [это утверждение не истинно].

Если мы установим, что утверждение G истинно, мы подтвердим, что оно ложно. И наоборот, если мы решим, что G ложно, это будет означать, что G истинно. Этот парадокс имеет место в самореферентных системах, к которым принадлежит и фраза в описанном примере, и такой ее вариант, как «Я лгу». В результате мы получаем странную петлю. Независимо от того, как мы будем рассуждать, мы всегда приходим в ту же точку, откуда начали. Другими примерами самореферентности являются рука, рисующая руку, на знаменитой картине Эшера, синтез белков и ДНК клетки или «микрофон, слушающий колонку», представленный в книге Дугласа Хофштадтера «Я странная петля»(I am a strange loop).

«Рисующие руки» (1948), Мауриц Корнелис Эшер.

В тот период некоторые ученые сформулировали следующий вопрос: может ли математическая интуиция быть кодифицирована в свод правил, или (па современном языке) в компьютерную программу? Необходимо было понять, возможно ли создание механического разума, сегодня именуемого компьютером, с помощью которого мы сможем автоматически исследовать или доказать без вмешательства человека истинность или ложность какого-либо математического доказательства или утверждения. Например, для того, что мы сегодня называем искусственнглм интеллектом, не существует системы правил для вычисления или вывода, которая позволила бы определить с помощью программы свойства натуральных чисел. Натуральные числа N = [1, 2, 3, 4, ...], которые мы используем для счета элементов целой величины, например количества яблок, имеют определенные свойства.

Пусть a, b и с будут числом яблок, равным 2, 3 и 5 соответственно. Свойство ассоциативности устанавливает, что (а + 6) + с = а + (b + с), в то время как согласно свойству дистрибутивности а • (b + с) = а • b + а • с. Если мы представим эти два свойства натуральных чисел в виде утверждений, назвав ассоциативность утверждением H, а дистрибутивность — утверждением /, и заменим а, b и с их числовыми выражениями