Алан Тьюринг

 

Иван Долмачев

 

 

 

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

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

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

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

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

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

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

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

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

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

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

Глава I

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

Иштван Барна

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

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

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

ХУДШИЙ В КЛАССЕ

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

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

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

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

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

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

КРИС

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

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

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

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

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

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

Глава II Кембриджский дон

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

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

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

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

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

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

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

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

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

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

ОТСТУПЛЕНИЕ О ГАМЕЛЬНСКОМ ДУДОЧНИКЕ

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

Рихард Курант (1888—1972), крупный математик нашего столетия, ученик и сотрудник Гильберта

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

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

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

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

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

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

ГИЛЬБЕРТ И ЖЕНЩИНЫ

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

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

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

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

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

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

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

ГИЛЬБЕРТ И МУЗЫКА

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

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

ГИЛЬБЕРТ И ИЗОБРАЗИТЕЛЬНОЕ ИСКУССТВО

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

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

ГИЛЬБЕРТ И ЛИТЕРАТУРА

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

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

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

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

ГИЛЬБЕРТ И ПОЛИТИКА

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

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

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

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

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

ГИЛЬБЕРТ И ЭКОНОМИКА

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

ГИЛЬБЕРТ И ГИПОТЕЗА РИМАНА

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

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

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

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

* * *

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

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

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

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

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

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

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

ГЛАВА III

Сущность математики лежит в ее свободе.

Г. Кантор

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

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

Георг Кантор (1845 - 1918)

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

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

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

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

КАНТОРОВСКИЙ ДИАГОНАЛЬНЫЙ ПРОЦЕСС

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

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

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

Самый простой способ решения — это "тупой перебор": будем по очереди выписывать (генерировать) всевозможные строки из крестиков и ноликов, сравнивать их с каждой из строк заданной таблицы Т и повторять это до тех пор, пока мы не найдем строку, не входящую в таблицу. Такая строка заведомо в конце концов найдется: ведь всевозможных строк длины п, составленных из крестиков и ноликов, имеется 2" штук, а в таблице имеется только п строк, причем некоторые из строк таблицы могут даже быть одинаковыми. Поэтому существует по крайней мере 2" — п различных строк, не входящих в таблицу. (Например, в случае таблицы 5х5 этих строк будет 25 — 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. Тогда мы бы имели

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

для всех индексов 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, х2, х3, х4, ...                (1)

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

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

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

( здесь х1 = 2, х2 = 4, х3 = 6, х4 = 8 и т.д). Допускает ли пересчет множество всех целых чисел ? Это множество обычно изображается в виде последовательности, "бесконечной и вправо, и влево":

... , -3, -2, -1, 0, 1, 2, 3, ...                      (2)

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

Нетрудно построить и другие пересчеты множества всех целых чисел. Гораздо менее простой пример — пересчет множества всех рациональных дробей вида — m/n , где т и п — натуральные числа. Для получения такого пересчета нужно догадаться, что все рациональные дроби могут быть помещены в таблицу с бесконечным числом строк и бесконечным числом столбцов:

Рис. 3

В этой таблице в столбце номер т и строке номер п находится дробь m/n  . Все элементы таблицы можно последовательно "обойти", продвигаясь "змейкой" из левого верхнего угла и "разворачиваясь" на первой строке и первом столбце таблицы, как показано стрелками на рис. 3. Тогда по "змейке" мы обойдем все рациональные дроби, получив не что иное, как их пересчет:

1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2. ...  (3)

Здесь мы уже не пишем для наглядности символы х1, х2, х3, х4, ... сверху, как это делали раньше. Идея "обхода змейкой" бесконечной таблицы принадлежит.   Кантору и находит важное применение в основах теории множеств. "Канторовская змейка" изображена на бронзовом обелиске Г. Кантору в г. Нойштадте. Кстати говоря, этот же обелиск украшен знаменитым выска зыванием Кантора о математике, вынесенном в эпиграф к этой главе (по-немецки "Das Wesen der Mathematik liegt in ihrer Freikeit" ).

Но вернемся к пересчету (3).

Если из последовательности (3) вычеркнуть все сократимые дроби ( 2/2, 2/4, 3/3 и т.д.) и заново перенумеровать оставшиеся, то мы получим пересчет множества (положительных) рациональных чисел:

1/1, 2/1, 1/2, 1/3,  3/1, 4/1, 3/2, 2/3, 1/4, 3/2, 2/3, 1/4, 1/5, 5/1 ...  (4)

Вычеркнуть сократимые дроби нужно было потому, что каждое рациональное число должно входить в пересчет лишь однин раз, а в (3) это не имело места: например, число

входит в (4) бесконечное количество раз. Так произошло потому, что одно и то же рациональное число может быть представлено в виде дроби m/n    различными способами (но только одним способом в виде несократимой дроби).

Множества, допускающие пересчет, получили название "счетных". Как мы только что видели, счетными являются множество натуральных чисел, множество четных чисел, множество рациональных дробей, множество положительных рациональных чисел. Пересчет может быть устроен сравнительно сложно: например, для получения пересчета множества положительных рациональных чисел мы сначала расположили рациональные дроби в таблицу на рис. 3, обошли ее "змейкой", получив пересчет (3), а затем вычеркнули "лишние" (сократимые) дроби, получив окончательный пересчет (4). Кантор задался вопросом: а существует ли пересчет, пусть даже и очень сложный, множества всех действительных чисел? (Напомним, что, кроме рациональных чисел, множество которых, как мы видели, допускает пересчет, существуют и иррациональные числа. Например, квадратный корень из 2 - иррациональное число, т.е. оно не может быть равным никакой рациональной дроби m/n.) Иначе этот вопрос можно сформулировать так: является ли множество всех действительных чисел (обозначаемое далее через R) счетным?

Выдающемуся математику Рихарду Дедекинду (1831—1916) вопрос о счетности множества действительных чисел, присланный ему Кантором в письме 1873 г., показался "не представляющим практического значения". Это было вполне естественно — с такого рода вопросами математика того времени еще не сталкивалась, и до Кантора никому из математиков ничего подобного не приходило в голову. (Когда Дедекинд получил письмо Кантора, самого понятия "счетности" еще не существовало — мы пользуемся здесь современной терминологией; Кантор и Дедекинд в своей переписке пользовались другими терминами.) В ответном письме Дедекинд признается, что ответа на вопрос Кантора он не знает, советуя Кантору не уделять ему слишком много труда, и одновременно приводит доказательство счетности множества всех алгебраических чисел.

Действительное число называется алгебраическим, если оно является корнем какого-нибудь алгебраического уравнения с целыми коэффициентами. Любое рациональное число m/n - алгебраическое: оно является корнем уравнения пх — т = 0. Квадратный корень из 2, не являясь рациональным, также алгебраическое число: оно является корнем уравнения второй степени х2 2 = 0. Вообще все числа, получаемые из целых чисел с помощью арифметических действий, и операции извлечения корня — алгебраические (например, -

в то же время существуют алгебраические числа, не представимые указанным способом). Числа, не являющиеся алгебраическими, называются трансцендентными. Первым, кто доказал (в 1844 г.), что не все числа алгебраические (т.е. что существуют трансцендентные числа), был французский математик Жозеф Лиувилль (1809—1882). В 1874 г. Шарль Эрмит (1822—1901) доказал трансцендентность неперова числа (числа е — "основания натурального логарифма") и признался в опубликованной им статье, что он долго, но безуспешно пытался доказать трансцендентность числа "пи". Лишь в 1882 г. Карл Линдеман (1852—1939), развивая методы Эрмита, доказал, что число "пи" трансцедентно. Эта замечательная теорема Линдемана о трансцендентнос­ти числа "пи" положила конец более чем двухтысячелетним поискам решения знаменитой античной задачи о "квадратуре круга". Из трансцендентности числа "пи" следует, что с помощью лишь циркуля и линейки невозможно построить квадрат, равновеликий (равный по площади) данному кругу, т.е. квадратура круга невозможна.

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

Возьмем совокупность всех целых положительных индивидов п и обозначим ее через {п}. Затем рассмотрим совокупность всех действительных положительных числовых величин и обозначим ее через (х). Тогда возникает вопрос: можно ли сопоставить (п) с (х) так, чтобы каждому индивиду одной совокупности соответствовал один и только один индивид другой ? На первый взгляд кажется, что это невозможно, так как (п) состоит из дискретных частей, тогда как (х) образует континуум. Однако это возражение ничего не дает, и как бы я ни был склонен думать, что между (n) и (х) невозможно однозначное соответствие, я тем не менее не могу найти основание для этого, хотя оно, возможно, просто и именно оно занимает меня.

Не столь ли соблазнительно было бы заключить, что {п) нельзя поставить в однозначное соответствие с совокупностью (p/q) всех рациональных чисел (p/q)? И тем не менее нетрудно доказать, что (n) можно поставить в однозначное соответствие не только с этой совокупностью, но и с более общей совокупностью

где, любое число неограниченных целых положительных индексов".

(Г. Кантор — Р. Дедекинду, 29 ноября 1873 года)

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

(Г.Кантор — Р.Дедекинду, 2 декабря 1873 года)

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

(Из личных записей Р.Дедекинда, 1873 год; цит. по [1] )

Рихард Дедекинд (1831 - 1916)

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

Кантор опубликовал свои результаты в 1874 г. [3]. Доказательство Кантора вызвало восторг у Дедекинда и многих других математиков: оно было самым коротким и простым доказательством существования трансцендентных чисел (и остается таковым и поныне). Доказательство несчетности множества R, опубликованное Кантором в упомянутой статье, вопреки широко распространенному мнению, не использовало диагонального процесса. "Диагональный процесс" Кантор придумал гораздо позже и изложил его в докладе на научной конференции, но опубликовал его (в наиболее общей форме) лишь, как уже упоминалось, в 1891 году [2]. Суть канторовского доказательства, основанного на диагональном процессе, сводилась к следующему. Пусть дана произвольная последовательность действительных чисел, лежащих в числовом интервале от 0 до 1:

х1, х2, х3, х4, ...                (5)

Докажем, что всегда существует число х, большее 0 и меньшее 1, отличное от всех членов последовательности (5). (Если мы это докажем, то это будет значить, что множество действительных чисел, расположенных в интервале от 0 до 1, не допускает никакого пересчета, иначе говоря, отсюда будет следовать несчетность этого множества и тем более несчетность множества R.)

Каждое из действительных чисел из интервала от О до 1 может быть записано в виде бесконечной десятичной дроби с нулевой целой частью. (Мы будем представлять действительные числа в виде бесконечных десятичных дробей. Например, число 0,25 представляется бесконечной десятичной дробью 0,250000......) Рассмотрим представление чисел х1, х2, х3, х4, .... в виде бесконечных десятичных дробей, расположенных друг под другом. Например, представление этих чисел может быть таким:

x1 = 0,32433...

x2 = 0,11239...

x3 = 0,61520...

x4 = 0,00719...

x5 = 0,49961...

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

Рис. 4

Читатель, уяснивший идею диагонального процесса, уже, наверное, догадался, как завершить доказательство. Рассмотрим, как и раньше в случае с крес­тиками-ноликами, диагональ этой таблицы и заменим в ней цифры, например, по следующему правилу: если на диагонали стоит единица, то заменяем ее на двойку, а если на диагонали стоит цифра, отличная от единицы, то заменим ее на единицу (см. рис. 4). Мы получим бесконечную "исключительную" последовательность цифр (единиц и двоек), которая отлична от всех строк таблицы на рис. 4а. Тогда число х, записанное как десятичная дробь с нулевой целой частью и со знаками после запятой, взятыми из полученной с помощью диагонального процесса "исключительной" последовательности из единиц и двоек, будет отлично от всех чисел х1, х2, х3, х4, ...! (В нашем примере х = 0,12122...) Таким образом, нужное нам число х, не входящее в последовательность (5), будет построено. Удивительно остроумное решение!

Как приведенный метод построения соотносится с формальными обозначениями Т и D, введенными ранее? Здесь Т [i,j] — j-я цифра после запятой в представлении числа хi. в виде десятичной дроби. "Массив" D представляет знаки после запятой у числа х. Т и D связаны между собой соотношением (*). Это соотношение обеспечивает условие того, что число х отлично от каждого из чисел в последовательности (5). Можно также сказать, что в качестве канторовских "двух исключающих друг друга признаков" (крестика и нолика — см. рис, 2) здесь взяты признаки для цифр "быть единицей" и "не быть единицей".

Очень интересное философское обсуждение диагонального процесса в связи с понятием счетного и несчетного можно найти в заметках выдающегося философа Людвига Витгенштейна [4].

По мнению автора этих строк, наилучшее из существующих доступных для школьников изложений основ канторовской теории множеств (в том числе и диагонального процесса) имеется в учебнике И.Р. Шафаревича [5].

В отличие от первоначального доказательства несчетности множества R, данного Кантором в статье [3], приведенное выше доказательство с помощью диагонального процесса вполне доступно большинству нематематиков. В силу этого обстоятельства диагональный процесс и его применение к доказательству несчетности множества R стали объектом бесчисленных псевдонаучных спекуляций, производство которых не прекращается и до сих пор, — см., например [6] — одну из наиболее "свежих" (и наиболее диких) работ в этом направлении. (Остается только диву даваться, каким образом подобные "исследования" могут финансироваться грантами Российского гуманитарного научного фонда.)

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

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

Библиография

1. Г.Кантор. Труды по теории множеств, под ред. А.Н. Колмогорова и А. П. Юшкевича. Серия "Классики науки". М.: Наука, 1985.

2. G. Cantor. Uber eine elementare Frage der Man-nigfaltigkeitslehre Jahr. Dt. Math. Ver. 1890/1891, Bd. 1, S. 75-78. (Рус. пер. [I], с. 170-172.)

3. G. Cantor. Uber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen J. reine und angew. Math, 1874, Bd. 77, S. 258-262. (Рус. пер.: Г.Кантор. Об одном свойстве совокупности всех действительных алгебраических чисел — [1], с. 2—81.)

4. А.Витгенштейн. Замечания по основаниям математики, ч. I (1937—1938 гг.), приложение 2. В кн.:

А.Вштенштейн. философские работы. М.: Гнозис, 1994, с. 59 и далее.

5. И.Р. Шафаревич. Избранные главы алгебры. Гл. VI—VII. Математическое образование, 1998, № 3—4, с. 2-81.

6. В.К. Петросян, Общий кризис теоретико-множественной математики и пути его преодоления. Версия 1.0. М.: Янус-К, 1997.

7. D.Hubert. Uber das Unendliche Math. Ann. 95 (1925), S. 161-190. (Рус. пер.: А-Гильберт. О бесконечном — в кн.: Д.Гильберт. Основания геометрии. Добавление VIII, с. 338-364.)

Продолжение следует

 

 

 

 

TopList