Современным математикам, программистам и компьютерным инженерам имя Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" — "основу основ" теории ал­горитмов. Без "машины Тьюринга" не обходится ни один серьезный учебник по математической логике и теории вычислимости.

Почти за каждым выдающимся научным открытием стоит удивительная история. За "машиной Тьюринга" стоит история жизни научного гения — гения, который лишь через много лет после своей трагической смерти получил достойное признание.

Роль А.Тьюринга в истории информатики отнюдь не исчерпывается одним лишь изобретением "машины Тьюринга", как это может иногда показаться из-за относительной скудости опубликованных (на русском языке) сведений о нем.

Алан Тьюринг может быть причислен к плеяде составляющих гордость человечества величайших математических и философских умов, таких, как Р.Декарт, Г.В. Лейбниц, Б.Рассел, Д.Гильберт, А.Витгенштейн. Удивительно, сколь злую шутку сыграло с Тьюрингом его полное безразличие к борьбе за приоритет в научных открытиях: вплоть до недавнего времени его место в истории развития научных и инженерных идей представлялось очень неполно, если не сказать однобоко (и не в последнюю очередь благодаря некоторым американским историкам науки, тщательно заботившимся об абсолютизации своего национального приоритета в создании компьютеров, да и, пожалуй, в создании всей информатики).

Мемориальная доска, установленная чуть больше года назад на стене одной из лондонских гостиниц, гласит:

"Здесь родился Алан Тьюринг (1912 — 1954), взломщик кодов [Code-breaker] и пионер информатики [computer science] ". Действительно, сейчас (но отнюдь не при жизни!) Тьюринг признан одним из основателей информатики и теории искусственного интеллекта, его считают первым теоретиком современного программирования и, наконец, первым в мире хакером. (Между прочим, его "хакерская деятельность" внесла во время второй мировой войны существенный вклад в победу союзных войск над германским флотом, а один из коллег Тьюринга однажды сказал: "Я не берусь утверждать, что мы выиграли войну благодаря Тьюрингу. Однако без него могли бы ее и проиграть".)

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

Мой очерк не является чисто биографическим, возможно, более точным названием для него было бы что-нибудь вроде следующего: "Алан Тьюринг и история развития идей математической логики и информатики (1930—1950-е гг.)". Дело в том, что я буду делать довольно много отступлений от собственно биографии Тьюринга — именно для того, чтобы обрисовать историческую эволюцию идей и научный фон, на котором были сделаны фундаментальные открытия. К сожалению, в нашей (да и зарубежной) учебной литературе можно встретить недопустимые неточности, касающие­ся подобных вопросов, а устная лекторская традиция иногда доводит такие неточности до крайних несуразностей. (Так, например, в одном из российских вузов студентов учили, что "машина Тьюринга" была изобретена с целью проиллюстрировать наиболее простым образом принципы работы программируемых вычислительных устройств.)

Большая часть биографических сведений о Тьюринге была взята мною из капитального 600-страничного труда Эндрю Ходжеса (Andrew Hodges. Alan Turing: the Enigma, 2^nd ed, L, 1992), по всей видимости, надолго (если не навсегда) ставшего самой фундаментальной монографией о Тьюринге (о переводе этой блестяще написанной книги на русский язык приходится пока только мечтать). Тем не менее мой текст не является переводом или пересказом фрагментов этой книги (и фрагментов Интернет-сайта Э.Ходжеса — http://www.turing.org.uk/ , которые также были мною использованы).

Я считаю приятной обязанностью выразить свою искреннюю признательность публицисту В. В. Шахиджаняну, предложившему мне написать этот очерк (который, кроме того, никогда не был бы закончен без его постоянных дружеских напоминаний), и профессору механико-математического факультета МГУ им. М.В. Ломоносова О.М. Касим-заде за многочасовые беседы о математике, логике и философии, прояснившие некоторые мои взгляды, нашедшие отражение в предлагаемом вашему вниманию очерке. Разумеется, указанные лица не несут никакой ответственности за возможные ошибки и неточности в тексте — ответственность за них лежит целиком на мне.

Автор. Октябрь 1999 г.

Будущие родители Алана Тьюринга — Юлиус Мэтисон Тьюринг и Этель Сара Стоуни познакомились и обвенчались в Индии. Тьюринг служил в английском колониальном ведомстве, а Этель Сара была дочерью главного инженера Мадрасских железных дорог. Это была добропорядочная английская аристократическая семья, принадлежавшая к так называемому "высшему среднему классу" (upper-middle-class) и жившая в соответствии со строгими традициями Империи.

В семье Тьюрингов родилось двое детей. Младший сын, названный Аланом Мэтисоном (Alan Mathison Turing), увидел свет 23 июня 1912 г. в лондонской лечебнице "Уоррингтон-Лодж". Биограф Тьюринга Эндрю Ходжес нашел символичным то, что в этой лечебнице, позже переоборудованной в гостиницу и ставшей во время второй мировой войны пристанищем многих беженцев из континентальной Европы, в 1938 году остановился один из таких изгнанников с родины по имени Зигмунд Фрейд. Тьюринг, как и Фрейд, был выдающимся исследователем человеческого Разума, хотя и не снискавшим столь громкую славу.

В детстве Алан и его старший брат Джон довольно редко видели своих родителей — их отец до 1926 г. служил в Индии; дети оставались в Англии и жили на попечении в частных домах, получая строгое английское воспитание, соответствующее их положению на социальной лестнице. В рамках такого воспитания изучение основ естественных наук фактически не предусматривалось.

Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте б лет, он просил у своих воспитателей разрешения читать научно-популярные книги. В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения  сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для  детей аристократов). Но ее опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School). Впрочем, вскоре ей пришлось опасаться уже того, сможет ли ее талантливый сын окончить эту школу...

...О школьных успехах Алана красноречиво свиде­тельствует классный журнал, в котором можно найти, например, следующее: "Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание [...]; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я все же не могу". Последнее место по успеваемости в классе. Это запись преподавателя английского языка.

По латыни — лучше: уже предпоследнее место. По другим предметам еще чуть лучше, но вердикты учителей однообразны: "безнадежное отставание", "безобразная успеваемость"... Директор школы пишет: "Этот мальчик из тех, кто обречен стать большой проблемой для любой школы или сообщества...".

Впрочем, в классном журнале имеются и другие записи: "Если он хочет быть только научным специалистом, он зря проводит время в Public School... Наверное, он будет математиком. Такие ученики, как он, рождаются один раз в 200 лет".

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

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

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

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

Алан искренне полюбил своего друга. После окончания школы они оба собирались поступать в Кембриджский университет, и Алан, избавившийся от многолетнего одиночества, возможно, был почти счастлив...

Первая попытка сдать предварительные экзамены в Кембридж, куда они ездили вместе, была для Алана неудачной. Но он не слишком расстраивался, потому что искренне радовался за Кристофера, который успешно прошел испытания и получил стипендию. Алан надеялся поступить со второй попытки, чтобы учиться вместе со своим другом. 13 февраля 1930 г. его Криса вдруг не стало. Внезапная смерть лучшего друга потрясла семнадцатилетнего Тьюринга, повергнув его в глубокую и долгую депрессию. Тем не менее он, бывший худший ученик в классе, нашел в себе силы поступить в Кембридж. Его поддерживало твердое убеждение в своей обязанности совершить в науке то, что Кристофер уже не мог... Тьюринг очень не скоро оправится от потрясения: уже будучи студентом Кембриджа, на протяжении нескольких лет он пишет матери Моркома проникнутые душевной болью письма. В этих письмах он постоянно возвращается к размышлениям о том, как человеческий Разум — и, в частности, разум Кристофера — размешается внутри материальной оболочки и каким образом он освобождается от нее в момент физической смерти тела.

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

Еще долгое время Тьюринг будет придерживаться подобных взглядов: пройдут годы и годы, прежде чем его друг юности Кристофер "умрет окончательно" — Тьюринг откажется от веры в существование разума после смерти. Но вопрос об устройстве человеческого разума будет волновать его всю жизнь.

В 1931 году Тьюринг стал студентом Кингз-колледжа (King's College) в Кембридже — знаменитого на весь мир старинного английского университета. Кембриджский университет, обладавший особыми привилегиями, дарованными английскими монархами, издавна славился либеральными традициями, и в его сте­ах всегда царил дух свободомыслия. Здесь Тьюринг обретает — пожалуй, впервые — свой настоящий дом, где он смог полностью отдаться науке.

Боль утраты все еще пронизывает его чувства, но сейчас главное место в жизни занимает увлеченное изучение столь интересующих его наук — математики и квантовой физики. Те годы были периодом бурного становления квантовой физики, и Тьюринг в сту­енческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Дж. фон Неймана "Математические основы квантовой механики", в которой он находит ответы на многие давно интересующие его вопросы. Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне — одном из самых известных университетов США. Еще позже фон Нейман, так же как и Тьюринг, будет назван "отцом информатики"... Но тогда, в начале 30-х годов, научные интересы обоих будущих выдающихся ученых были далеки от вычислительных машин — и Тьюринг, и фон Нейман занимаются в основном задачами "чистой" математики. (Отметим здесь математическую работу Тьюринга "Эквивалентность левой и правой почти-периодичности", вышедшую в 1935 году, в которой он упростил одну идею фон Неймана в теории непрерывных групп — фундаментальной области современной математики.)

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

Друзей у него было совсем не много. Высокомерных студентов-аристократов отталкивали его несколько беспорядочный стиль одежды, эксцентричные прически и манера говорить резким скрипучим голосом (к тому же он иногда сильно заикался) — Тьюринг, как обычно, не вписывался в "положенные" рамки общественных норм поведения.

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

Тьюринг блестяще заканчивает четырехлетний (^undergraduate) курс обучения. Одна из его работ, посвященная теории вероятностей, удостаивается специальной премии, его избирают в научное общество Кингз-колледжа — fellowship (нечто среднее между аспирантурой и преподавательским корпусом). Казалось, его ждет успешная карьера слегка эксцентричного кембриджского дона, работающего в области "чистой" математики (don — так в Кембридже и Оксфорде по традиции называют преподавателей).

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

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

Итак, в 1935 г. молодой докторант Кингз-коллед-жа Алан М. Тьюринг знакомится с фундаментальной проблемой, поставленной одним немецким математиком...

Впрочем, здесь лучше было бы сказать не "одним математиком", а "величайшим математиком XX века", который, кстати сказать, также никогда не "вписывался" ни в какие рамки, да и по экстравагантности поведения нисколько не уступал Тьюрингу. Сейчас я сделаю

"Гильберт представляется мне выдающимся примером человека, в котором проявляется необычайная творческая способность абсолютного научного гения...
Горе той молодежи, которая не может быть растрогана до глубины души примером такого человека, как Гильберт".

Герман Вейль (1885—1955), выдающийся математик XX столетия, ученик Гильберта

Если современного математика спросить, в чем сотоит вклад Давида Гильберта в математическую науку, ответ — конечно, при условии, что математик достаточно образован, — обещает быть довольно длинным. Как писал журнал "Nature" после смерти Гильберта, едва ли можно было встретить в мире математика, чья работа не была бы связана в той или иной степени с работами Гильберта. И это утверждение имеет достаточные основания и сейчас, спустя более чем полвека. Его имя навсегда останется в истории математики: существуют гильбертово пространство, неравенство Гильберта, преобразование Гильберта, инвариантный интеграл Гильберта, теорема неприводимости Гильберта, теорема Гильберта о базисе, аксиома Гильберта, подгруппа Гильберта, поле классов Гильберта, символ Гильберта.

Давид Гильберт (1862-1943)

Я не буду подробно рассказывать о математических работах Гильберта и ограничусь только известным замечанием, что его научная деятельность определила лицо математики двадцатого века.

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

Женщины были всепоглощающей — после математики, разумеется, — страстью Гильберта. По Геттингену ходили легенды о его похождениях, студенты с жаром обсуждали, кто является его очередной "пассией" (определение Гильберта). Гильберта находили "похожим немного на подростка, остановившегося в своем развитии". В теплые дни он являлся на лекции в рубашке с короткими рукавами и открытым воротом — наряде, совершенно не подобающем для профессора тех времен. Он носился по улицам, как уличный разносчик, с букетами из своего сада для своих "пассий". Корзину с удобрениями он мог везти на руле своего велосипеда так, как будто это был подарок. На концерте или в ресторане, как бы элегантно он ни был одет, почувствовав сквозняк, он мог одолжить меховую горжетку или боа из перьев у одной из присутствующих здесь дам. Но он всегда держался с таким естественным достоинством, что не вызывал ни у кого смеха.

Ему нравилось танцевать, и он всегда предпочитал ежегодный бал у ректора банкету, устраиваемому этим же официальным лицом каждый год для профессоров и их жен. Ему нравились симпатичные молоденькие дамочки, и он с радостью объяснял им математические идеи. "Но, моя девочка, — мог он сказать, — вы должны это понять".

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

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

Вместе с тем Гильберт очень противился женитьбе молодых ученых, считая, что женитьба будет им помехой для выполнения своего долга перед наукой. Его друг и ассистент Пауль Бернайс (1888—1977) (соавтор Гильберта по знаменитой монографии "Gmndlagen der Mathematilc" — "Основания математики") долгое время не мог позволить себе жениться...

Когда женился Вильгельм Аккерман (1896—1962) (с которым Гильберт писал книгу по теоретической логике — о ней пойдет речь ниже), Гильберт был очень рассержен. Он отказался помогать чем-либо Аккерману для достижения карьеры. А когда Гильберт услышал, что у Аккерманов должен вскоре появиться ребенок, он очень обрадовался.

"О, это чудесно! — сказал он. — Это замечательная новость для меня. Потому что если этот человек столь безумен, что женился и даже .заводит ребенка, то это полностью освобождает меня от обязанностей чем-либо помочь такому сумасшедшему".

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

В особенности Гильберт любил громкую музыку. В те времена громкость определялась размером граммофонной иглы, и Гильберт настаивал, чтобы игла его граммофона была большой. Однажды он отправился на концерт великого Карузо с большими надеждами. Однако его ждало разочарование. "Карузо поет на маленькой игле", — сказал он.

Считаясь в основном консервативным, он удивил всех своим предложением наградить Кете Кольвиц (1867—1945), известную своими крайне левыми взглядами, звездой ордена "Заслуги за мир". (Кольвиц стала одной из величайших художниц за всю историю искусства. Она посвятила свое творчество теме страданий человечества.)

"Конечно, на то, что она рисует, страшно смотреть, — сказал Гильберт своим друзьям, награжденным звездой. — Но когда в Кенигсберге мы часто танцевали в дни молодости, она была одной из первых девушек, танцевавших без корсета".

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

Существует один анекдот, в большой степени проливающий свет как на его отношение к литературе, так и на его чувства к математике. Некий математик стал романистом. "Почему он занялся этим? — изумлялись в Геттингене. — Как может человек, бывший математиком, писать романы?" — "Но это же совсем просто, — сказал Гильберт. — Для математики у него недоставало воображения, в то время как его вполне хватило на романы".

"У математиков есть на все свои тео­рии. У меня — теория о математиках. Мы так сосредоточены на наших рукопи­сях и уравнениях, что нас принято счи­тать слишком отрешенными и, следо­вательно, слишком холодными инеэмо-гщональными. Моя теория заключается в том, что именно потому, что математики так эмоциональны, они могут стать математиками. Им по крайней мере присуща способность увлечься аскетической красотой, которой обладает математика — "белая богиня", как поэт Роберт Гревс назвал музу поэзии — музу всех нас".

К.Фейс, современный математик

Гильберт часто спорил со своим ассистентом Паулем Бернайсом о политике. Гильберт никогда не считал- себя привязанным к какой-нибудь определенной политической доктрине. В спорах с Бернайсом он часто критиковал "либералов" за то, что они видят вещи такими, какими они хотят их видеть, а не такими, какие они есть на самом деле. "Иногда случается, — говорил он, — что кругозор человека становится все уже и уже и, когда его радиус стремится к нулю, он сводится к одной точке. Тогда эта точка становится его точкой зрения". Он частенько напоминал Бернайсу: "Человечество никогда не меняется".

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

"Ах, я хотел бы знать, что будет на этот раз! — с предвкушением сказал Гильберт своему соседу. Прошлый раз, когда созывали подобное собрание, среди профессоров распределяли нескольких гусей, полученных университетом от одного крестьянина. "Может быть, теперь мы получим свинью".

Ректор начал свою речь. У него были большие новости. "Наш главнокомандующий, его величество кайзер, только что объявил нашему врагу неограниченную подводную войну!"

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

В 1923 году в Германии с целью обеспечения экономической стабильности была введена новая денежная единица — Rentenmark. Гильберт скептически заметил, что "нельзя решить проблему, поменяв название независимой переменной".

В шестидесятых годах прошлого века немецкий математик Бернгард Риман (1826—1886) высказал некоторую математическую гипотезу (названную гипотезой Римана о нулях дзета-функции), которая не доказана и не опровергнута вплоть до настоящего времени, несмотря на то, что ею занимались и занимаются многие математики. (Доказательство этой гипотезы имело бы для математики большое значение, и сейчас, после доказательства Великой теоремы Ферма, пожалуй, именно гипотеза Римана занимает место самого знаменитого "нерасколотого орешка" в математике. )

Когда под дождем родственники и друзья покойного стояли со слезами на глазах над могилой, вперед вышел Гильберт. Он начал свою речь, сказав, что смерть такого одаренного молодого человека является настоящей трагедией, ведь у него были все возможности показать, на что он способен. Однако, продолжал он, несмотря на то, что его доказательство гипотезы Римана содержало ошибку, еще остается возможность, что когда-нибудь доказательство знаменитой проблемы будет получено на путях, намеченных покойным. "Действительно, — с энтузиазмом продолжил он, стоя под дождем над могилой умершего студента, — рассмотрим функцию комплексной переменной..."

(По кн.: Констанс Рид. Гильберт. М.: Наука, 1977)

* * *

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

Один из ведущих современных Гильберту математиков как-то сказал ему: "Вы заставили всех нас думать только над тем, над чем вы считали, что нам следует думать". Гильберта, оказавшего своими идеями такое огромное влияние на математический мир, называли Гамельнским Дудочником, "завлекшим молодых крысят в глубокие воды математики".

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

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

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

Давид Гильберт

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

Г. Кантор

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

Эту историю я начну за несколько десятков лет до рождения Тьюринга — с 70-х годов прошлого столетия, когда профессор университета немецкого города Галле, уроженец Петербурга Георг Фердинанд Людвиг Филипп Кантор заинтересовался определенными математическими задачами, которыми до него не занимался никто.

"Вряд ли можно назвать какую-либо возникшую в последней четверти прошлого столетия математическую дисциплину, которая оказала бы большее влияние на последующий прогресс всей математики и шире — на математическое мышление в целом, чем теория множеств. К идеям теории множеств в разное время подходили с разных сторон многие ученые, но оформление ее в самостоятельную науку, со своим особым предметом и методами исследования, осуществил на протяжении четверти века в работах 1872—1897 гг. Георг Кантор". Этими словами начинается редакторское предисловие А.Н. Колмогорова и А. П. Юшкевича к книге [I]. Георг Кантор первым вступил в одну из самых абстрактных областей математики, именно он впервые исследовал с математической (а не метафизической) точки зрения взгляд на бесконечность — понятие, волновавшее человеческий ум на протяжении многих веков. Теория множеств Кантора до сих пор остается фундаментом для классических разделов математики, таких, как алгебра, геометрия и анализ.

Судьба научных идей Кантора оказалась очень непростой. У них были как преданные защитники, такие, как Гильберт, сказавший однажды: "Никто не сможет нас изгнать из рая, созданного для нас Кантором!" [7], — так и непримиримые противники, среди которых был, например, авторитетный математик Леопольд Кронекер (1823—1891), отозвавшийся как-то о работах Кантора с долей презрения: "Это не математика, это теология!".

Эта глава почти целиком посвящена подробному описанию одной из самых оригинальных идей Кантора — диагональному процессу. Диагональный процесс, изобретенный Кантором в связи с доказательством существования трансцендентных чисел и понятием несчетных множеств, лежит, как мы увидим в дальнейших главах, в основе знаменитого парадокса Рассела, повергшего, по словам Гильберта, математический мир в состояние шока, в основе доказательства легендарной теоремы Гёделя о неполноте формальных исчислений и в основе тьюринговского доказательства алгоритмической неразрешимости некоторых проблем (и на самом деле в основе очень многих других фундаментальных логико-математических конструкций).

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

Пусть имеется квадратная таблица размера п X п, каждая строка и каждый столбец которой занумерованы числами от 1 до п. Известно, что в каждой строке таблицы нарисован один из двух символов — крестик или нолик, причем расстановка крестиков и ноликов в таблице совершенно произвольна. На рис. 1а показана одна из таких возможных таблиц размера 5х5 (рис. слева).

Рассмотрим следующую задачу. Требуется написать строку из п символов (каждый из этих символов должен быть крестиком или ноликом) так, чтобы она не совпадала целиком ни с одной строкой нашей таблицы. Например, для таблицы на рис. 1а в качестве ответа можно взять строку ХОООО или строку, состоящую из одних ноликов. А, скажем, строка ХОХОО в качестве ответа не подойдет: она входит в таблицу (это третья строка).

Как можно решить эту задачу в общем случае, т.е. как описать какой-нибудь общий способ нахождения строки, не входящей в заданную квадратную таблицу? Для читателей "Информатики", наверное, более понятной будет такая "программистская" формулировка этой задачи. Дан массив-таблица Т (двухмерный массив размера п х п), заполненный крестиками и ноликами. Требуется заполнить массив-строку D (одномерный массив длины п) крестиками и ноликами так, чтобы D не совпадал целиком ни с одной из строк массива-таблицы Т. (Вместо крестиков и ноликов можно, конечно, взять числа 1 и 0.)

Самый простой способ решения — это "тупой перебор": будем по очереди выписывать (генерировать) всевозможные строки из крестиков и ноликов, сравнивать их с каждой из строк заданной таблицы Т и повторять это до тех пор, пока мы не найдем строку, не входящую в таблицу. Такая строка заведомо в конце концов найдется: ведь всевозможных строк длины п, составленных из крестиков и ноликов, имеется 2" штук, а в таблице имеется только п строк, причем некоторые из строк таблицы могут даже быть одинаковыми. Поэтому существует по крайней мере 2" — п различных строк, не входящих в таблицу. (Например, в случае таблицы 5х5 этих строк будет 2⁵ — 5 = 32 — 5 = 27.) Любую из них можно взять в качестве ответа.

Способ решения "тупым перебором", конечно, не представляет собой ничего особенно примечательного (не говоря уж о том, что он кажется неоправданно трудоемким для того, чтобы найти всего лишь одну какую-нибудь строку, не входящую в таблицу).

Существует другой, гораздо более экономный и остроумный способ решения задачи. Вернемся к рис. 1а и посмотрим на элементы таблицы, расположенные по диагонали (на рис, 1а эти "диагональные элементы" обведены рамками). В таблице на рис. la по диагонали стоит ОХХОХ, т.е. эта последовательность — "диагональ" нашей таблицы. Преобразуем "диагональ", заменяя в ней каждый крестик на нолик и наоборот. Тогда из "диагонали" ОХХОХ получится ХООХО (см. рис. 1б). Полученная строка не будет целиком совпадать ни с одной строкой таблицы! Легко догадаться, почему. Если бы она совпадала с первой строкой таблицы, то ее первый элемент совпадал бы с первым элементом "диагонали" (ноликом), если бы она совпадала со второй — то ее второй элемент совпадал бы со вторым элемен­том "диагонали", и т.д. Но мы изготовили строку ХООХО так, что ее элементы как раз не совпадают с соответствующими элементами диагонали! Значит, наша строка не может совпадать ни с первой, ни со второй и вообще ни с какой строкой таблицы.

Наше рассуждение можно оформить более "математически", если воспользоваться обозначениями индексов (номеров) элементов таблицы и элементов строки. Пусть Т — исходная таблица (двухмерный массив) и T[i, j] обозначает ее элемент, находящийся в строке номер i и столбце номер j. (Например, Т[3, 2] — нолик, а Т [2, 3] — крестик в таблице на рис. 1а.) У "диагональных элементов" номера их строки и столбца одинаковые, т.е. на диагонали стоят элементы Т[1, I], Т[2, 2], Т[3, З], ..., иначе говоря, "диагональ" образована всевозможными элементами вида T[i,i].

Как мы изготовили строку (одномерный массив) D, не совпадающую ни с одной из строк таблицы Т? Принцип построения состоял в требовании, чтобы каждый элемент D [i] (т.е. элемент строки D, находящийся в позиции номер г) не совпадал с соответствующим диагональным элементом" Т [i, i]. Это можно выразить так:

D[i] не равно Т [г, г] для всех индексов i.       (*)

Отсюда сразу видно, почему строка D не может совпадать целиком ни с одной из строк таблицы Т. Действительно, если бы это было не так, то D совпада­ла бы с одной из строк таблицы, скажем, со строкой номер i. Тогда мы бы имели

для всех индексов j, в том числе и для индекса j, равного i. Но если подставить в предыдущее равенство индекс j равным i, то получится

D[i]=T[i,i],

что противоречит требованию (*). Значит, строка D не совпадает ни с одной из строк таблицы Т.

Метод построения строки D, выраженный требова­нием (*), чрезвычайно прост. Особого внимания заслуживает то обстоятельство, что для построения "исключительной" строки D нам не понадобилось знать все элементы таблицы Т. Нужна была только небольшая ее часть — "диагональ". (Для решения с помощью "тупого перебора", описанного ранее, понадобились бы все элементы таблицы Т.)

Процесс получения "исключительной" строки D по принципу (* ) получил название канторовского диагонального процесса, или диагонального метода, диагональной процедуры.

Рассмотренная нами задача кажется на первый взгляд довольно надуманной и в общем-то бесполезной, хотя ее решение с помощью диагонального процесса и выглядит весьма элегантным. Оказалось, однако, что простая идея диагонального процесса, придуманная Кантором, нашла очень глубокие проявления в математике и в математической логике (об этом будет рассказано ниже).

Заметим, что диагональный процесс "работает" и в случае таблицы из крестиков и ноликов, которая мыслится как бесконечно протяженная. Такую таблицу (см. рис. 2 слева) легко себе представить: она неограниченно продолжается вправо и вниз — иначе говоря, каждая ее строка бесконечна, и таких строк в таблице бесконечно много.

Для этой бесконечной таблицы наша первоначальная задача тоже имеет смысл: можно задаться вопросом, как построить строку (бесконечную последовательность) из крестиков и ноликов, чтобы она не совпадала целиком ни с одной из (бесконечных) строк исходной таблицы. Конечно, такая задача уже носит чисто математический характер: в ней участвует абстракция бесконечной последовательности. О каком-нибудь решении методом "тупого перебора" тут не может быть и речи. Тем не менее канторовский диагональный процесс все же дает нам метод построения бесконечной последовательности, не совпадающей ни с одной из строк таблицы! У бесконечной таблицы тоже есть "диагональ" (естественно, бесконечная), и мы можем последовательно, как и раньше, применять принцип (*), заменяя в "диагонали" крестики на нолики и наоборот, продолжая этот процесс неограниченно. Построенная таким образом последовательность D не будет совпадать ни с одной из строк таблицы Т ровно по тем же причинам, что и прежде: D не может совпадать с первой строкой таблицы, потому что ее первый элемент не совпадает с первым элементом "диагонали"; не может совпадать со второй строкой, потому что ее второй элемент не совпадает со вторым элементом диагонали; и так далее для всех строк таблицы.

Наше описание диагонального процесса по существу совпадает с оригинальным изложением Кантора в его знаменитой статье 1891 г. "06 одном элементарном вопросе учения о многообразиях" [2]. (Только Кантор рассматривал не крестики и нолики, как это сделали мы, а "два каких-либо исключающих друг друга признака [Charaktere] ".)

Над идеей диагонального процесса полезно поразмышлять каждому любознательному уму. Если вернуться к формулировке задачи (для бесконечной таблицы), то можно подумать, что она вообще лишена смысла — ведь кажется, что для предъявления бесконечной строки D, не совпадающей ни с одной из строк заданной бесконечной таблицы, необходимо обозреть эту бесконечную таблицу целиком. Вместе с тем диагональный процесс обеспечивает метод пошагового построения бесконечной строки D, причем для выполнения каждого шага нужно знать только "конечный" кусок бесконечной диагонали.

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

Математика постоянно имеет дело с бесконечными совокупностями (множествами). Таковы, например, множество всех натуральных чисел (1, 2, 3, ...), мно­жество всех точек на прямой, множество всех фигур на плоскости. Изображая бесконечные множества на бумаге, мы часто пишем что-нибудь в следующем роде:

Здесь многоточие призвано подчеркнуть, что последовательность "занумерованных иксов" неограниченно продолжается вправо. Запись типа (1) несет в себе и другой важный смысл: элементы рассматриваемого множества могут быть перенумерованы ("пересчитаны"). Это значит, что каждому элементу заданного множества можно сопоставить уникальный номер — натуральное число. При этом каждое натуральное число будет номером какого-то однозначно определенно­го элемента множества. Такое сопоставление номеров, как говорят, образует пересчет элементов данного множества. "Программистская формулировка" может быть такой: некоторое бесконечное множество допускает пересчет, если все его элементы могут быть "записаны" в "бесконечный одномерный массив" х[1], х [2], х [3], ... так, что каждый элемент этого множества "записан" в какой-то элемент массива х [i], при­чем только один раз (т.е. в разные ячейки массива "записаны" разные элементы множества). Вместо "программистских" х[1], х[2], х[3], ... мы пишем математические ,х₁, х₂, х₃, х₄, ... .

Например, множество натуральных чисел, разумеется, допускает пересчет:

— то есть здесь х₁ = 1, х₂ = 2, х₃ = 3, х₄ = 4 и т.д. Множество всех четных чисел также допускает пересчет: