Текст книги "Десять великих идей науки. Как устроен наш мир."

Автор книги: Питер Эткинз (Эткинс)

сообщить о нарушении

Текущая страница: 28 (всего у книги 31 страниц)

Что также становилось ясным, так это существование проблем с теорией множеств, которую хотели представить как основание математики. Может быть, неприятности теории множеств можно проследить до подлинной проблемы, заключающейся в самом понятии множества, которое выглядит выхолощенным? Может быть, понятие множества слишком широко для математиков? В начале двадцатого века, приблизительно в то же время, когда Рассел и Фреге сражались со своими проблемами, эта точка зрения получила определенную поддержку в форме аксиомы выбора. Эта аксиома является логическим двойником пятого постулата геометрии Евклида (о параллельных прямых, глава 9) и привлекла к себе огромное внимание. Ее простейшая форма выглядит кроткой как овечка: если у вас есть набор множеств, то вы можете составить новое множество, выбирая по одному элементу из каждого множества и добавляя их в свою тележку для покупок. Все мы собираем таким способом элементы множеств в супермаркете, называя вновь сконструированное множество своим шопингом. Кто мог бы возразить против такой процедуры собирания множества?

Однако овечка сбрасывает шкуру и оборачивается волком, как только мы начинаем рассматривать бесконечные множества, поскольку, возможно, нет никакого способа точно определить выбор. Для конечного числа множеств мы можем просто составить список всех элементов, которые хотим выбрать – список покупок. Рассмотрим, однако, следующую задачу. У нас есть бесконечное число множеств, одно состоит из действительных чисел, лежащих между 0 и 1, другое между 1 и 2 и так далее. Мы решили образовать новое множество путем случайного выбора по одному элементу в каждом из этих множеств. К сожалению, мы не можем составить список наших выборов, потому что их число бесконечно, и не можем определить их правилом, потому что их выбор должен быть случайным. Таким образом, мы образовали множество, которое не можем точно определить. Рассел привел бытовую иллюстрацию трудности, которую создает аксиома выбора: богатый человек, имеющий бесконечное число пар носков, поручает слуге выбрать по одному носку из каждой пары. Слуге не удается это проделать, так как у него нет способа решить, какой носок в каждой паре он должен выбрать.

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

Если математика не является в чистом виде ответвлением логики, что заставляют предполагать все эти неудачи, то какие еще дополнительные составляющие заложены в ней? Чтобы раскопать одну вероятную составляющую, мы должны обратиться к сыну шорника и наиболее трудно понимаемому, но и наиболее влиятельному из философов восемнадцатого века, возможно, на четверть шотландцу, Иммануилу Канту (1724-1804). В своем обсуждении метафизического познания, представляющего собой философское познание, выходящее за пределы опыта, в своей книге Kritik der reinen Vernunft(Критика чистого разума, 1781), Кант вводит различие между «синтетическими» и «аналитическими» суждениями. Аналитическое суждение, в котором предикат (свойство) предмета может быть выявлен путем только рассуждения, не приносит нового знания, как, например, высказывание «морковь является овощем». Согласно логическим позитивистам начала двадцатого века, принявшим и уточнившим этот термин, истинность аналитического суждения зависит только от значений составляющих его слов и правил грамматики, управляющих их сочетанием. Однако синтетическое суждениеявляется таким, в котором предикат не содержится в предмете, например, «эта роза – красная», поскольку не все розы красные; такие утверждения несут новое знание. Далее, эти категории подразделяются на суждения a priori, для которых оценка их истинности не зависит от свидетельства опыта, и суждения a posteriori, для которых оценка истинности определяется в опыте.

Кант предположил, что синтетические суждения a priori, которые выражают новое знание, но являются не связанными с опытом, представляют собой подходящие объекты для философского исследования. Такие суждения включают в себя утверждения о пространстве и времени, которые, с его точки зрения, неоспоримы, и восприятие которых каким-то образом встроено в наши мозги. Для Канта принципы геометрии Евклида и свойства натуральных чисел были синтетическими суждениями a priori. С точки зрения Канта, теоремы математики представляют собой «евклидизацию» свойств пространства и времени, которая некоторым образом выявляет работу нашей нервной системы (это, разумеется, не тот термин, который он использовал) и наши способы восприятия.

Идею о том, что в натуральных числах присутствует нечто врожденное, являющееся непосредственно очевидным синтетическим априорным свойством мира, датский математик Луитцен Эгбертус Ян Брауэр (1881-1966), один из создателей топологии, в своей докторской диссертации, защищенной в 1907 г. в Амстердамском университете, развил в философию математики, известную как интуиционизм. Брауэр отмел кантовский взгляд на геометрию как на синтетическую априорную конструкцию, который, на самом деле, уже был превращен в пыль тем, что пятый постулат Евклида, хотя он и согласуется с другими постулатами, можно заменить другими, не создавая противоречия (как мы видели в главе 9). То есть Брауэр признал, что Кант был неправ, предполагая, что евклидова геометрия необходимоверна, поскольку существуют альтернативные геометрии, которые, как показывает опыт, лучше описывают пространство и время. Однако он не отверг в целом точку зрения Канта на математику как на средство изучения пространства и времени, он отверг только ее пространственную составляющую. Брауэр считал, что математика является выражением нашего осознавания времени, и пропагандировал тот взгляд, что натуральные числа происходят из последовательного просмотра набора объектов и временного разделения наших восприятий каждого из них, которое и представляет собой способ их различения. Брауэр, на самом деле, шел дальше: он был соллипсистом и считал, что все существующее, включая наши сознания, происходит из одного сознающего ума. Однако это точка зрения не является необходимой составляющей интуиционистской повестки дня, и на первый взгляд кажется, что нет необходимости говорить о ней далее (но позднее я еще коснусь с одобрением одного ее варианта).

Интуиционист принимает точку зрения, что натуральные числа имеют особый статус и что мы имеем прямую их интуицию: они не являются объектами, которые можно разработать лучше с помощью дальнейших описаний. Для того чтобы, следуя Брауэру, прийти к понятию натурального числа, мы должны замечать, как наше восприятие проводит различия между объектами, возникающие из упорядоченного во времени их просматривания, с отгибанием пальца всякий раз, как в поле нашего зрения попадает еще один. Из такого взгляда следует, что натуральные числа являются выражением нашей умственной активности. Подобным же образом арифметические операции, такие как сложение, следует считать изображениями умственных процессов, происходящих у нас в голове. Таким образом, чтобы подтвердить, что 2 + 3 = 1 + 4, мы должны выполнить множество операций; мы должны найти результат прибавления 2 к 3, так же как и 1 к 4, а затем должны удостовериться, что эти результаты равны друг другу.

У интуиционизма есть определенные неприятные следствия, которые не становятся немедленно очевидными при кратком описании, но которые необходимо отметить, поскольку они наносят удар в самое сердце классической логики. Это, в частности, случай, когда имеют дело с утверждениями о бесконечных наборах объектов, с которыми нельзя ассоциировать никакую умственную активность, связанную с их восприятием, поскольку у нас нет прямого опыта бесконечности. Например, Аристотель считал одним из столпов логики свой закон исключенного третьего, согласно которому любое утверждение либо истинно, либо ложно. Этот закон оказывается не выполняющимся в интуиционистской математике, поскольку в ней может существовать утверждение, которое не может быть доказано или является логически неразрешимым. В любом случае, это не та ситуация, в которой утверждение либо истинно, либо ложно, лишь бы это когда-либо могло быть доказано. Одним из следствий такого положения дел является то, что утверждение «неверно, что это предложение ложно» не эквивалентно утверждению «это предложение истинно». В то время как мы могли бы утверждать, что сказать «неверно, что в коробке с бесконечным числом шаров найдется шар не красного цвета» это то же, что сказать «все шары в коробке красные», интуиционист отверг бы такое заключение. Согласно интуиционизму, истинность утверждения «в коробке найдется шар не красного цвета» может быть установлена только перебором всех находящихся в коробке шаров, что невозможно в случае бесконечного набора. Еще одним следствием такого положения является невозможность доказать некоторое утверждение, используя аргумент reductio ad absurdum, то есть показать, что отрицание этого утверждения ложно или ведет к противоречию. Для интуициониста единственно приемлемым утверждением является такое, доказательство которого может быть явно построено и требует конечного числа шагов.

Давид Гильберт (1862-1943), прекрасный танцор и любитель пофлиртовать, был одним из наиболее влиятельных математиков двадцатого столетия. Он, как и Кант, родился в Кенигсберге, в Восточной Пруссии (по странному совпадению, Гольдбах тоже родился там). Он знаменит, в частности, тем, что сформулировал проблемы математики, которые, по его ощущениям, на грани веков, то есть в начале двадцатого века, являлись самыми выдающимися. С тех пор многие математики пытались разрешить представленные Гильбертом проблемы, сообщение о которых он сделал на Втором Международном конгрессе математиков в Париже в 1900 г. В лекции были представлены десять проблем; пока Гильберт работал над версией для публикации, их число выросло до двадцати трех. Влияние этих проблем – которые правильнее считать комплексом из группы проблем и намеков на проблемы, чем двадцатью тремя точно сформулированными отдельными экзаменационными вопросами – проистекает из того, что они представляли собой ответ на вопрос о том, что считать хорошей проблемой. Так, проблемы, предъявленные Гильбертом, стоили того, чтобы потратить время на их решение: они были трудными, но не выглядели нерешаемыми, а решение их осветило бы более широкий круг вопросов, чем те, которые они содержали.

Некоторые из этих проблем решены; некоторые оказались неразрешимыми; иные все еще подвергаются атакам исследователей. Некоторые из проблем, в том виде, в котором Гильберт их сформулировал, являются настолько грандиозными, что неясно, будет ли когда-нибудь получено их решение, столь же определенное, как для других проблем. Например, одной из грандиозных проблем была аксиоматизация физики, утверждение ее на кратком и надежном основании, как это проделал Евклид для своего варианта геометрии, а он, Гильберт, строго формализовал его в своем авторитетном труде Grundlagen der Geometric(Основания геометрии, 1899). То, что он здесь имел в виду, можно истолковать, как формулирование «общей теории всего». Однако большая часть этих проблем вполне опеределенна, особенно если их великодушно интерпретировать. Например, они включали доказательство континуум-гипотезы Кантора (которая оказалась недоказуемой) и гипотезы Риманао том, что некоторая определенная функция комплексного переменного zобращается в нуль на бесконечном множестве значений z, каждое из которых имеет действительную часть, равную 1/2 (рис. 10.9).

Рис. 10.9.Известно, что все решения уравнения 1 + 1/2 ^z+ 1/3 ^z+ 1/4 ^z+ … = 0, где  z– комплексное число, лежат в окрашенной полосе между 0 и 1. Одна из форм гипотезы Римана утверждает, что все решения этого уравнения на самом деле лежат на центральной линии полосы (как обозначено маленькими кружками), на которой действительная часть равна 1/2 в каждом случае.

Последняя проблема может показаться не слишком уместной, но на самом деле она имеет фундаментальную важность для изучения простых чисел; она остается нерешенной и считается одной из важнейших нерешенных проблем математики. Позднее мы встретимся с двумя другими проблемами Гильберта явно. Его второй проблемой, которую атаковал и решил отрицательно Гёдель, было доказательство непротиворечивости аксиом арифметики. Его десятой проблемой, так называемой Enischeidungsproblem(проблема решения), которую также атаковали и решили отрицательно Алан Тьюринг и Апонз Чёрч, было обнаружение процесса, посредством которого можно было бы определить, решаемо ли уравнение за конечное число шагов или нет.

Гильберт развил также философию математики, которая стала называться формализмом. Он видел математику как два плотно склеенных листа: один лист состоит из конечных расположений символов, получаемых с помощью применения определенных правил. Эти символы просто образуют определенный рисунок на странице и совершенно лишены смысла. Такие бессмысленные рисунки и есть то, что мы на самом деле понимаем под математикой. Даже аксиомы системы являются просто строчками значков, из которых вытек смысл, интеллектуальными трупами, а новые картинки выводятся из этих строчек посредством применения абстрактных правил. С этой точки зрения математики являются дизайнерами обоев. Единственные надежные доказательства, согласно Гильберту, являются финитистскими, а том смысле, что они являются финитными(то есть конечными) наборами символов, поскольку лишь такие наборы можно обозреть и проверить: безопасная математика – это финитная математика. На втором листе находится метаматематика, которая состоит из комментариев к реальной математике, она содержит комментарии типа «эта строка символов имеет сходство с другой», или «xнужно интерпретировать как особый знак для объекта», или «особая группа знаков указывает на то, что модель является полной», или «вот доказательство этого предложения». Мы можем представлять себе собственно математику как всевозможные расположения фигур на шахматной доске, а сопровождающую ее метаматематику как комментарии типа «для белых существует двадцать возможных первых ходов» или «в этой позиции следует шах и мат». Согласно формалистам, математика – это абстрактный символизм и порождение моделей: метаматематика наделяет символизм и модели значением для человека, она пропитывает значки «смыслом», она восстанавливает у трупов кровообращение.

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

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

Я рассмотрю теперь две из важнейших проблем Гильберта, те две, которые наносят удар в самое сердце философии математики и наиболее прямо исследуют ее возможности. Как я уже упоминал, одной из этих проблем является так называемая Entscheidungsproblem, проблема отыскания систематического способа для определения того, можно ли доказать некоторое утверждение символического языка с помощью аксиом этого языка. Атаку на эту проблему почти одновременно предприняли двое, одним был американский логик Алонзо Чёрч (1903-95), который ввел и разработан то, что он назвал λ-исчислением, а другим – британский математик Алан Мэтисон Тьюринг (1912-54), который ввел «логическую вычислительную машину», известную как машина Тьюринга. Эти два подхода изначально были различны на поверхностном уровне, но сотрудничество Чёрча и Тьюринга показало, что на самом деле они математически эквивалентны. Существует одна чрезвычайно важная сильная сторона математики, ее способность показывать эквивалентность с виду совершенно несравнимых вещей. Мы сосредоточим внимание на подходе Тьюринга, поскольку он имеет больше сходства со знакомым нам современным миром компьютеров, но не должно пройти незамеченным, что λ-исчисление Чёрча ассоциируется с используемым в них программным обеспечением и является его основой.

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

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

Рис. 10.10.Версия машины Тьюринга. Машина состоит из бесконечно длинной ленты бумаги, разделенной на ячейки, в которых могут быть записаны символы (обычно, 0 или 1), и механизма, который может считывать эти символы, реагируя на считываемое в соответствии со своим внутренним состоянием в данный момент, меняя символы, если это требуется, и переходя к соседним ячейкам в соответствующем направлении. В этом представлении внутреннее состояние обозначается световым сигналом на одной из сторон считывающей головки. Правая диаграмма показывает возможный отклик: машина находится во внутреннем состоянии, обозначенном световым сигналом, и считывает 1; в результате она заменяет 1 на 0, меняет свое внутреннее состояние и сдвигает ленту на один шаг вправо.

Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.

Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t ₁, t ₂, и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина  t ₁₀принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t ₁₀(3) = 42. Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина  t ₂₂принимает число 17. Чтобы зарегистрировать этот результат, запишем t ₂₂(17) = □. Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены.

Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга, которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать:

001:если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо.

Подобным же образом, код 010 может означать:

010:если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо.

Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu. Заметим, что, в то время как индивидуальнаямашина Тьюринга считывает только данные, универсальнаямашина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t ₁₀, мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме  t ₁₀, а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42, где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t ₂₃, и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (hздесь от английского глагола «halt» – останавливаться). Если thполучает остановку для частной комбинации программы и данных, например t ₂₃и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t ₂₂и 17, thнапечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что thне включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата.

Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t ₀, t ₁, t ₂, … и составляем таблицу, верхним левым фрагментом которой является следующая:

Номер матрицы	0	□	□	□	□
	1	3	□	4	1
	2	1	1	1	1
	3	0	1	□	2

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

Теперь мы делаем второй шаг. На этот раз мы рассортируем результаты с помощью машины th, которая настроена так, что выдает 0, если решает, что соответствующие вычисления не остановятся, и не выдает никаких данных, если решает, что вычисления остановятся. Она также делает себе пометку, чтобы запомнить, где она заменила □ на 0, так как не хочет, чтобы машина, программа которой имитируется, была снова втянута в бесконечные вычисления. Например, когда мы загружаем в машину thчисло 4, а затем число 2, она, в соответствии с программой t ₄и данными 2, инспектирует ленту, производит некоторого рода вычисления, решает, что вычисление t ₄(2)не остановится, если мы будем его выполнять, и поэтому ставит 0 в соответствующую ячейку таблицы и делает себе пометку, что данное вычисление не остановится. В конце этого этапа вычислений верхний левый фрагмент таблицы выглядит так:

Номер матрицы	0	0	0	0	0
	1		0
	2
	3			0

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

Номер матрицы	0	0	0	0	0
	1	3	0	4	1
	2	1	1	1	1
	3	0	1	0	2

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

Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на thи машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th, которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblemне имеет решения.

Теперь я перехожу к высшей точке этой главы, к тому, что называют самым красивым достижением логики двадцатого века, к теореме Гёделя. Австрийский логик Курт Гёдель (1906-1978) родился в Брюнне, Австро-Венгрия (ныне Брно, Республика Чехия), где работал Грегор Мендель, и учился в Венском университете. Хотя он и не был евреем (вопреки утверждению Бертрана Рассела), Гёдель не смог терпимо относиться к нацистским репрессиям и в 1934 г. поехал в США, в 1940 г. эмигрировал туда насовсем и провел оставшуюся часть жизни в Принстоне, где он и Эйнштейн стали большими друзьями. Конечно, в свои последние годы Гёдель внес существенный вклад и в общую теорию относительности, когда обнаружил неожиданное решение уравнений Эйнштейна, позволяющее времени течь в прошлое. По своему облику и образу жизни Гёдель не был человеком, которого можно было считать вполне приемлемым в обществе. Возвратись в Австрию после своей первой поездки в США, он женился на разведенной танцовщице и увез ее в Принстон, где ее не могли хорошо принять из-за преобладавшего в то время снобизма. К концу жизни у него развились классические признаки депрессии и паранойи: он был убежден, что является жертвой тайного общества убийц, что в конце концов привело его к отказу от еды и к ношению лыжной маски, чтобы избежать заражения во время прогулок в опасной и сильно загрязненной, как он считал, атмосфере Принстона. Он скончался, веся лишь 30 кг, от «недоедания и истощения» (вызванных отказом от пищи), явившихся, как гласит заключение о смерти, результатом «душевного расстройства».