Полiт.ua Государственная сеть Государственные люди Войти
15 декабря 2017, пятница, 02:10
Facebook Twitter LiveJournal VK.com RSS

НОВОСТИ

СТАТЬИ

АВТОРЫ

ЛЕКЦИИ

PRO SCIENCE

СКОЛКОВО

РЕГИОНЫ

21 июня 2006, 06:00

Пределы доказуемости

По мнению ученого Грегори Чейтина, сегодня, в 2006 году, мы все еще не знаем, насколько серьезна неполнота математических методов. В своей статье "Пределы доказуемости" известный американский математик, научный сотрудник Исследовательского центра им. Томаса Уотсона корпорации IBM, почетный профессор Университета Буэнос-Айреса и Оклендского университета, размышляет на тему способности научных теорий справиться со сложностью фактов окружающего мира и создать единую теорию, объясняющую их. Отправной точкой для Чейтина служит знаменитая теорема Курта Геделя О неполноте формальных систем : каждая логическая система либо неполна, либо противоречива. Гедель показал неизбежную неполноту математики: в ней существуют истинные положения, которые невозможно строго доказать. Согласно подходу Г. Чейтина, Гедель открыл только верхушку айсберга: существует бесконечное множество верных математических теорем, которые невозможно доказать, исходя из конечной системы аксиом. Ученым ещё предстоит дать ответ на вопрос, стоит ли из-за этого пересматривать сами математические методы. Статья опубликована в новом номере журнала "В мире науки" (2006. Июнь).

В 1956 г. журнал Scientific American опубликовал статью Эрнста Нагеля (Ernest Nagel) и Джеймса Ньюмана (James R. Newman) «Доказательство Геделя». Через два года ее авторы выпустили одноименную книгу, которая переиздается до сих пор. В те дни я был еще ребенком, но до сих пор помню трепет, который испытал, открыв ее в Нью-йоркской публичной библиотеке.

Меня поразило то, как Курт Гедель (Kurt Gödel) использовал математику, чтобы показать, что ее собственные возможности ограничены. Он опроверг высказанное около столетия назад Давидом Гильбертом утверждение о существовании полной теории математики, т.е. конечной совокупности принципов, из которых с помощью последовательного использования правил математической логики можно вывести все положения математики. Гедель показал, что существуют истинные математические утверждения, которые не могут быть доказаны таким образом. Его выводы основаны на двух самоотносимых парадоксах: «данное утверждение ложно» и «данное утверждение недоказуемо».

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

Сложность и законы науки

В 1686 г. было издано философское эссе Готфрида Лейбница (Gottfried W. Leibniz) «Рассуждения о метафизике» (Discours de métaphysique), в котором поставлен вопрос: как отличить факты, которые можно описать неким законом, от фактов, никаким законам не подчиняющихся? В четвертом разделе своего эссе Лейбниц высказал очень простую и глубокую мысль: теория должна быть проще данных, которые она объясняет, иначе она не объясняет ничего. Концепция научного закона становится бессмысленной, если допускает неограниченный уровень математической сложности, потому что в таком случае всегда можно сформулировать закон независимо от того, насколько случайны и беспорядочны факты. И наоборот, если единственный закон, объясняющий какие-то данные, оказывается слишком сложным, то рассматриваемые данные на самом деле не подчиняются никакому закону.

Современная математическая теория алгоритмической информации позволила дать точные количественные определения понятиям сложности и простоты. Обычная теория информации определяет объем информации числом битов, необходимых для ее кодирования. Например, для кодирования простого ответа «да/нет» нужен один бит. В отличие от этого, объем алгоритмической информации определяется длиной компьютерной программы, необходимой для генерации данных. Минимальное число битов, необходимых для хранения программы, называется количеством алгоритмической информации данных. Например, бесконечный ряд натуральных чисел 1, 2, 3,... содержит очень мало алгоритмической информации: все числа ряда можно получить с помощью коротенькой компьютерной программы. Не имеет значения, сколько времени понадобится для выполнения вычислений и какой объем памяти придется использовать, важна лишь длина программы в битах. (Разумеется, точное значение количества алгоритмической информации зависит от выбранного языка программирования, однако для рассматриваемых в данной статье вопросов это несущественно.)

В качестве другого примера возьмем число π, равное 3,14159... Количество алгоритмической информации в нем тоже невелико: для последовательного вычисления всех его знаков нужен довольно короткий алгоритм. А вот случайное число, содержащее всего миллион знаков, скажем, 1,341285...64, характеризуется гораздо бóльшим количеством алгоритмической информации. Поскольку в таком числе нет определяющей структуры, длина самой короткой программы, необходимой для его написания, будет близка к длине самого числа:

Начать
Напечатать «1,341285...64»
Конец
/P>

(В программу должны быть включены все цифры, замененные многоточием.) Никакая более короткая программа не позволит рассчитать подобную последовательность цифр: ее невозможно сжать, в ней нет избыточности. Самое лучшее, что можно сделать, – просто передать ее, как она есть. Такие последовательности называются неприводимыми или алгоритмически случайными.

Как же соотносятся вышесказанное с научными законами и фактами? Идея заключается в том, чтобы взглянуть на науку глазами программиста: научная теория подобна компьютерной программе, предсказывающей результаты наблюдений, т.е. экспериментальные данные. Такая точка зрения опирается на два фундаментальных принципа. Согласно первому («бритва Оккама»), из двух теорий, объясняющих некоторые данные, следует предпочесть более простую. Иначе говоря, наилучшей теорией является самая короткая программа, позволяющая рассчитать результаты наблюдений. Второй принцип, изложенный Лейбницем, в современных понятиях звучит так: теория, объем которой в битах равен количеству объясняемых ею данных, бесполезна, поскольку теорией такого размера можно описать совершенно случайные данные. Полезная теория обеспечивает сокращение количества информации: осмысление данных — это их сжатие в краткие алгоритмические описания. Чем проще теория, тем лучше понимание сути явления.

Достаточная причина

Лейбниц, живший за два с половиной века до появления компьютерных программ, очень близко подошел к современному понятию алгоритмической информации. Лейбниц знал, что все можно представить в виде двоичных кодов, и создал одно из первых вычислительных устройств; рассматривая понятия сложности и простоты, он осознавал огромный потенциал вычислений. Если бы Лейбниц объединил все известные ему элементы, то, скорее всего, усомнился бы в одном из устоев своей философии — принципе достаточной причины, согласно которому все происходящее имеет причину. Более того, если какое-то положение истинно, то оно истинно по какой-то причине. Бывает, что в суете и хаосе повседневной жизни в это трудно поверить. Даже если мы не всегда можем увидеть причину (возможно потому, что цепочка рассуждений слишком длинна и запутанна), ее видит Бог. Вот и все! Здесь Лейбниц соглашался с древнегреческими авторами этой идеи.

Математики, несомненно, безоговорочно принимают принцип достаточной причины Лейбница, потому что всегда стремятся все доказать. Даже если истинность теоремы очевидна, и миллионы примеров подтверждают ее, математики все равно требуют обобщенного доказательства, на меньшее они не согласны. И здесь концепция алгоритмической информации может внести удивительный вклад в философские рассуждения об источниках и пределах познания. Она показывает, что некоторые математические факты истинны безо всяких причин, и бросает вызов принципу достаточной причины. Как будет показано ниже, существует бесконечное число неприводимых математических фактов, истинность которых нельзя объяснить никакой теорией. Они неприводимы не только вычислительно, но и логически. «Доказать» эти факты можно только одним способом: признать их аксиомами без всяких рассуждений.

Понятие «аксиома» тесно связано с логической неприводимостью. Аксиомы — это математические положения, которые мы считаем самоочевидными и не пытаемся доказать, исходя из более простых принципов. Все математические теории основаны на аксиомах, из которых выводятся следствия, называемые теоремами. Именно так поступал Евклид два тысячелетия назад: его труды по геометрии стали классическим примером математического изложения.

В древней Греции, чтобы убедить сограждан проголосовать именно так, а не иначе, вы должны были бы привести им свои доводы. Вероятно, именно поэтому греки пришли к мысли, что математические положения нужно доказывать, а не выводить опытным путем. (В отличие от греков, древнейшие цивилизации Месопотамии и Египта, похоже, полагались на эксперимент.) Метод логических рассуждений оказался чрезвычайно плодотворным: с его помощью были созданы современная математика, математическая физика и все точные науки, включая технологию создания компьютеров — в высшей степени математичных и логичных машин. Утверждаю ли я, что подход, на котором математика и вся наука строились в течение двух тысячелетий, терпит крах? В каком-то смысле да. Моим контрпримером, иллюстрирующим ограниченность возможностей логики и рассуждений, моим источником бесконечного потока недоказуемых математических положений является число, которое я назвал «омега» (Ω).

Число Ω

Первый шаг к открытию числа Ω был сделан в знаменитой статье, опубликованной ровно через 250 лет после издания эссе Лейбница. В 1936 г. на страницах «Трудов Лондонского математического общества» (Proceedings of the London Mathematical Society) Алан Тьюринг впервые представил математическую модель простой универсальной вычислительной машины. Кроме того, он задался вопросом: можно ли определить, остановится когда-нибудь компьютерная программа или нет? Так была сформулирована знаменитая проблема останова.

Разумеется, запустив программу, вы можете со временем обнаружить, что она остановилась. Фундаментальная проблема заключается в том, чтобы решить, когда вы сдадитесь и престанете ждать, если программа не останавливается. Для множества частных случаев она может быть решена, но Тьюринг показал, что общего решения не существует. Никакой алгоритм и никакая математическая теория не позволят определить, какая программа остановится, а какая нет. Кстати, употребляя слово «программа» в современном смысле, я имею в виду совокупность самой компьютерной программы и данных, которые она обрабатывает.

Следующим шагом на пути к числу Ω становится рассмотрение множества всех возможных программ. Остановится ли когда-нибудь выбранная случайным образом программа? Вероятность останова и есть Ω. Определим сначала, как осуществить случайный выбор программы. Программа представляет собой последовательность битов, поэтому для выбора значения каждого последующего бита будем просто бросать монету. Сколько битов должна содержать программа? Будем бросать монету до тех пор, пока компьютер не перестанет запрашивать следующий бит. Число Ω есть вероятность того, что при введении такой случайной последовательности битов машина когда-нибудь остановится. (Численное значение Ω зависит от выбора языка программирования, но удивительные свойства этого числа с ним не связаны. Когда же язык выбран, Ω приобретает определенную величину, так же, как число π или число 5.)

Поскольку число Ω выражает вероятность, оно должно быть больше нуля, но меньше единицы, т.к. некоторые программы останавливаются, а некоторые – нет. Число Ω, записанное в двоичном коде, будет иметь вид вроде 0,1110100... Последовательность битов после запятой неприводима, а сами они оказываются неприводимыми математическими фактами (каждый факт состоит в том, является ли данный бит нулем или единицей).

Число Ω можно определить как бесконечную сумму, и каждая программа длиной N битов вносит в нее свой вклад, равный ½N (стр. 77). Иными словами, каждая N-битовая программа, которая останавливается, добавляет единицу к N-ному биту двоичного представления числа Ω. Сложив все биты, соответствующие остановившимся программам, мы можем получить точное значение Ω. Создается впечатление, что Ω можно вычислить точно, как или π. Однако это не так: число Ω строго определено и имеет вполне конкретное значение, но рассчитать его невозможно, поскольку это позволило бы решить проблему останова, у которой действительно нет решения. Если говорить конкретнее, знание первых N битов числа Ω позволяет определить, остановится ли когда-нибудь любая программа длиной до N битов (стр. 80), из чего следует, что для нахождения N битов числа Ω требуется программа длиной не менее N битов. Заметьте, я не утверждаю, что нельзя определить некоторое число битов числа Ω. Например, зная, что компьютерные программы 0, 10 и 110 останавливаются, мы можем говорить, что с точностью до первых трех битов Ω имеет вид 0,111. Дело в том, что первые N битов Ω нельзя вычислить с помощью программы, которая была бы существенно короче N битов.

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

Из неприводимости числа Ω следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов Ω составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория «всего на свете» характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин. Из сказанного отнюдь не следует, что от доказательств нет никакого толка, и я ни в коем случае не против логических рассуждений. На самом деле, неприводимые принципы (аксиомы) всегда составляли часть математики. Просто число Ω показывает, что их гораздо больше, чем предполагалось ранее.

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

Математика и физика

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

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

Имре Лакатош (Imre Lakatos), бежавший в 1956 г. из Венгрии и впоследствии занимавшийся философией науки в Англии, тоже считал, что математика похожа на физику. Он ввел понятие квазиэмпиричности, чтобы показать, что и математике не чужды эксперименты. Например, еще в 1742 г. Кристиан Гольдбах опытным путем пришел к предположению, что любое четное число больше двух можно представить в виде суммы двух простых чисел. Предположение Гольдбаха успешно проверено для чисел до 1014, но строго не доказано. Мне кажется, что математика квазиэмпирична. Иными словами, она отличается от физики (которая истинно эмпирична), но, вероятно, не так сильно, как полагает большинство людей.

Новые аксиомы

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

Другой очень интересной аксиомой может стать утверждение «P не равно NP», где P и NP – названия классов задач. К классу NP относятся задачи, для которых предлагаемое решение можно проверить очень быстро. Например, для задачи «найти множители числа 8 633» предлагаемое решение «97 и 89» быстро проверяется простым перемножением. (Существует строгое определение понятия «быстро», но подробности здесь не имеют значения.) Класс P составляют задачи, которые можно быстро решить, не имея предварительного предположения. Вопрос, ответа на который не знает никто, состоит в том, можно ли быстро решить любую задачу класса NP. (Есть ли способ быстро найти множители числа 8 633?) Иначе говоря, тождественны ли классы P и NP? Это один из пунктов списка «Проблем тысячелетия» Математического института Клэя (Clay Millennium Prize Problem), за решение каждой из которых назначена награда в $1 млн.

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

Экспериментальная математика

На стыке физики и математики возникла экспериментальная математика: открытие новых математических закономерностей путем компьютерной обработки большого числа примеров. Такой подход не столь убедителен, как короткое доказательство, но может быть убедительнее длинного, сложного доказательства и в некоторых случаях вполне приемлем. В прошлом данную концепцию отстаивали и Дьердь Пойа (George Pólya), и Лакатош, убежденные сторонники эвристических методов и квазиэмпирической природы математики. Он применяется и обосновывается в книге «Новый вид науки» (A New Kind of Science) Стивена Вольфрама (Stephen Wolfram), вышедшей в 2002 г.

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

Рассмотренные вопросы чрезвычайно интересны, но далеки от решения. Со времени публикации статьи о доказательстве Геделя прошло 50 лет, а сейчас, в 2006 г., мы все еще не знаем, насколько серьезна неполнота, и не следует ли из-за нее пересмотреть математические методы. Возможно, через 50 лет ответ будет найден.

СУЩЕСТВОВАНИЕ СПЕЦИФИЧЕСКОГО строго определенного числа Ω, которое невозможно вычислить с помощью конечной компьютерной программы, разбивает надежду на создание всеобъемлющей математической системы, в рамках которой можно строго доказать любое истинное утверждение.

ОБЗОР: НЕПРИВОДИМАЯ СЛОЖНОСТЬ

* Курт Гедель показал неизбежную неполноту математики: в ней существуют истинные положения, которые невозможно строго доказать. Особое число Ω выявляет еще бóльшую неполноту и свидетельствует о существовании бесконечного множества теорем, которые нельзя вывести из конечного набора аксиом.

* Число Ω строго определено и имеет вполне конкретное значение, но вычислить его с помощью конечной компьютерной программы невозможно.

* Анализ свойств числа Ω показывает, что математикам иногда следует постулировать новые аксиомы. Именно так поступают физики, которые обобщают результаты экспериментов и выводят фундаментальные законы, недоказуемые с помощью логики.

КОЛИЧЕСТВО АЛГОРИТМИЧЕСКОЙ информации определяется размером компьютерной программы, необходимой для генерации данных. Например, число π содержит мало алгоритмической информации, поскольку его можно вычислить с помощью короткой программы. Алгоритмическая информация случайного числа велика: его проще ввести непосредственно. Это справедливо и для числа Ω.

КАК ОПРЕДЕЛЯЕТСЯ ЧИСЛО Ω

Чтобы понять, как определяется число Ω, рассмотрим упрощенный пример. Допустим, что из всех программ некоего компьютера останавливаются всего три, которые представляют собой 110, 11100 и 11110, длиной 3, 5 и 5 битов соответственно. Если для выбора программ мы будем бросать монету, чтобы определять значение каждого очередного бита случайным образом, вероятности получения каждой из них будут равны соответственно ½3, ½5 и ½5, поскольку вероятность получения единицы или нуля для каждого бита равна ½. Тогда вероятность останова программы для такого компьютера будет определяться выражением:

Ω = ½3 + ½5 + ½5 = 0,001 + 0,00001 + 0,00001 = 0,00110.

Здесь двоичные числа выражают вероятность случайного выбора одной из трех останавливающихся программ. Поскольку программа 110 останавливается, мы не рассматриваем программы длиной больше трех битов, начинающиеся с 110, например, 1100 и 1101, т. е. мы не добавляем к сумме 0,0001 для каждой из них. Мы считаем все более длинные программы (1100 и т. д.) с таким началом включенными в программу 110, которая останавливается. Другими словами, данные программы являются самоограничивающимися, поскольку после их остановки последующие биты не запрашиваются.

ПОЧЕМУ ЧИСЛО Ω НЕСЖИМАЕМО?

Попробуем доказать, что число несжимаемо, т. е. его первые N битов невозможно определить с помощью программы длиной существенно меньше N битов. Проанализируем свойства Ω в свете поставленной Тьюрингом проблемы останова. Используем утверждение, что для программ длиной до N битов задача не может быть решена с помощью программы меньшей длины (см.: www.sciam.com/ontheweb).

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

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

Итак, зная первые N битов Ω, можно решить задачу останова для всех программ длиной до N битов. Предположим теперь, что первые N битов Ω можно определить с помощью программы длиной существенно меньше N битов. Тогда ее можно объединить с программой вычисления ΩK и получить в итоге программу длиной меньше N битов для решения проблемы останова для всех программ длиной до N битов. Однако, как сказано выше, такой программы существовать не может. Следовательно, для вычисления первых N битов Ω требуется программа длиной почти N битов. Этого достаточно, чтобы признать число Ω несжимаемым, т.е. неприводимым. (Для больших N сокращение длины с N битов до почти N битов несущественно.)

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

* Главу о Лейбнице см. в книге: Men of Mathematics. E. T. Bell. Reissue. Touchstone, 1986.

* Более полные сведения о квазиэмпирическом взгляде на математику см.: New Directions in the Philosophy of Mathematics. Edited by Thomas Tymoczko. Princeton University Press, 1998.

* Gödel’s Proof. Revised edition. E. Nagel, J. R. Newman and D. R. Hofstadter. New York University Press, 2002.

* Mathematics by Experiment: Plausible Reasoning in the 21st Century. J. Borwein and D. Bailey. A. K. Peters, 2004.

* О философии Геделя и связи его работ с трудами Лейбница см.: Incompleteness: The Proof and Paradox of Kurt Gödel. Rebecca Goldstein. W. W. Norton 2005.

* Meta Math!: The Quest for Omega. Gregory Chaitin. Pantheon Books, 2005.

* Краткие биографии математиков доступны на: www-history.mcs.st-andrews.ac.uk/BiogIndex.html

* Домашняя станица Чейтина: www.umcs.maine.edu/~chaitin/

Обсудите в соцсетях

Система Orphus

Главные новости

14.12 23:20 В Москве пройдет обсуждение книги Павла Уварова о Франции XVI в.
14.12 22:53 Минобороны РФ изложило свою версию «перехвата» Су-25 над Сирией
14.12 22:43 Россияне обыграли шведов на домашнем этапе Еврохоккейтура
14.12 21:35 «Современник» отложил спектакль из-за госпитализации Гафта
14.12 21:26 Захарова назвала ответственных за гибель людей в Донбассе
14.12 21:16 CNN сообщил о перехвате российских истребителей над Сирией
14.12 21:07 Четверо детей погибли при столкновении автобуса с поездом во Франции
14.12 20:04 Россельхознадзор запретил ввоз чая из Шри-Ланки из-за вредного жука
14.12 19:52 Apple начала продажи самого дорогого компьютера
14.12 19:30 Минтранс попросил Медведева уволить главу Росавиации
14.12 19:17 Дисквалифицированный лыжник Легков вошел в Putin Team
14.12 19:13 Биатлонистка из РФ выиграла спринтерскую гонку для Словакии
14.12 18:47 ЦИК насчитал 13-15 желающих баллотироваться в президенты
14.12 18:35 В московском воздухе зафиксировали тройное превышение сероводорода
14.12 18:19 КНДР пообещала США жесткие контрмеры за морскую блокаду
14.12 18:18 ЕЦБ и Банк Англии не стали менять ключевые ставки
14.12 18:12 Роскомнадзор пригрозил блокировать СМИ за «нежелательные» ссылки
14.12 17:44 WADA объявило о новом расследовании в отношении россиян
14.12 17:33 Прокурор напомнил Яшину о последствиях несанкционированной акции
14.12 17:25 Роскомнадзор пообещал постараться избежать блокировки YouTube
14.12 17:04 СКР открестился от дела в отношении Родченкова 2011 года
14.12 17:00 Сбербанк посулил акционерам триллион рублей дивидендов
14.12 16:48 Disney покупает кинокомпанию Twentieth Century Fox
14.12 16:27 Саакашвили отреагировал на критику Путина
14.12 16:17 Госдума отказалась сокращать новогодние каникулы
14.12 15:58 Тараканы меняют аллюр в зависимости от скорости движения
14.12 15:58 Греф признал наличие двух преемников
14.12 15:40 В употреблении допинга заподозрили 300 российских спортсменов
14.12 15:39 Суд в Бельгии закрыл дело об экстрадиции Пучдемона
14.12 15:37 Путин высказался о проблеме абортов
14.12 15:23 Сатурн обзавелся кольцами сравнительно недавно
14.12 15:16 Суд приговорил вербовщика террористов в Петербурге
14.12 15:15 Путин ответил Собчак на вопрос о страхе перед оппозицией
14.12 15:13 Рособрнадзор нашел нарушения на сайтах 95% вузов
14.12 15:03 Президент России назвал способ победить мировой терроризм
14.12 15:00 Британский суд признал WikiLeaks средством массовой информации
14.12 14:51 Парламент Британии получил право наложить вето на решение о Brexit
14.12 14:41 Путин обвинил Польшу в провокации конфликта из-за крушения самолета Качиньского
14.12 14:39 Путин отказался отвечать на вопрос о новом составе правительства
14.12 14:34 Путин назвал Китай основным стратегическим партнером
14.12 14:33 Роскомнадзор пригрозил YouTube блокировкой из-за «Открытой России»
14.12 14:26 Президент РФ назвал ЕАЭС выгодным для всех участников
14.12 14:17 В Думе обвинили Канаду в нежелании мира на Украине
14.12 14:11 Путин призвал к обмену заключенными и пленными с Украиной
14.12 14:08 Путин обвинил США в провокации по отношению к КНДР
14.12 14:00 Дума приняла закон о наказании за воровство на гособоронзаказе
14.12 13:53 Путин предложил ограничить кредиты коммерческих банков для регионов
14.12 13:42 Путин ответил на вопрос о Трампе и «российском следе» в президентских выборах в США
14.12 13:41 В Пхеньяне впервые собралась российско-корейская военная комиссия
14.12 13:34 СМИ назвали неполадки причиной взрыва на газовом хабе в Австрии
Apple Boeing Facebook Google iPhone IT NATO PRO SCIENCE видео ProScience Театр Pussy Riot Twitter Абхазия аварии на железной дороге авиакатастрофа Австралия Австрия автопром администрация президента Азербайджан акции протеста Александр Лукашенко Алексей Кудрин Алексей Навальный Алексей Улюкаев алкоголь амнистия Анатолий Сердюков Ангела Меркель Антимайдан Аргентина Аркадий Дворкович Арктика Армения армия Арсений Яценюк археология астрономия атомная энергия аукционы Афганистан Аэрофлот баллистические ракеты банковский сектор банкротство Барак Обама Башар Асад Башкирия беженцы Белоруссия Белый дом Бельгия беспорядки биатлон бизнес биология ближневосточный конфликт бокс болельщики «болотное дело» большой теннис Борис Немцов борьба с курением Бразилия Валентина Матвиенко вандализм Ватикан ВВП Великая Отечественная война Великобритания Венесуэла Верховная Рада Верховный суд взрыв взятка видеозаписи публичных лекций «Полит.ру» видео «Полит.ру» визовый режим Виктор Янукович вирусы Виталий Мутко «ВКонтакте» ВКС Владивосток Владимир Жириновский Владимир Маркин Владимир Мединский Владимир Путин ВМФ военная авиация Волгоград ВТБ Вторая мировая война вузы ВЦИОМ выборы выборы губернаторов выборы мэра Москвы Вячеслав Володин гаджеты газовая промышленность «Газпром» генетика Генпрокуратура Германия ГИБДД ГЛОНАСС Голливуд гомосексуализм госбюджет Госдеп Госдума госзакупки гражданская авиация Греция Гринпис Грузия гуманитарная помощь гуманитарные и социальные науки Дагестан Дальний Восток декларации чиновников деньги День Победы дети Дмитрий Медведев Дмитрий Песков Дмитрий Рогозин доллар Домодедово Дональд Трамп Донецк допинг дороги России драка ДТП Евгения Васильева евро Евровидение Еврокомиссия Евромайдан Евросоюз Египет ЕГЭ «Единая Россия» Екатеринбург ЕСПЧ естественные и точные науки ЖКХ журналисты Забайкальский край закон об «иностранных агентах» законотворчество здравоохранение в России землетрясение «Зенит» Израиль Ингушетия Индия Индонезия инновации Интервью ученых интернет инфляция Ирак Ирак после войны Иран Иркутская область искусство ислам «Исламское государство» Испания история История человечества Италия Йемен Казань Казахстан казнь Калининград Камчатка Канада Киев кино Киргизия Китай климат Земли КНДР Книга. Знание Компьютеры, программное обеспечение Конституционный суд Конституция кораблекрушение коррупция космодром Восточный космос КПРФ кража Краснодарский край Красноярский край кредиты Кремль крушение вертолета Крым крымский кризис Куба культура Латвия ЛГБТ ЛДПР Левада-Центр легкая атлетика Ленинградская область лесные пожары Ливия лингвистика Литва литература Лондон Луганск Малайзия Мария Захарова МВД МВФ медиа медицина междисциплинарные исследования Мексика Мемория метро мигранты МИД России Минздрав Минкомсвязи Минкульт Минобороны Минобрнауки Минсельхоз Минтранспорта Минтруд Минфин Минэкономразвития Минэнерго Минюст «Мистраль» Михаил Саакашвили Михаил Ходорковский МКС мобильные приложения МОК Молдавия Мосгорсуд Москва Московская область мошенничество музыка Мурманская область МЧС наводнение Надежда Савченко налоги нанотехнологии наркотики НАСА наука Наука в современной России «Нафтогаз Украины» недвижимость некоммерческие организации некролог Нерусский бунт нефть Нигерия Нидерланды Нобелевская премия Новосибирск Новые технологии, инновации Новый год Норвегия Нью-Йорк «Оборонсервис» образование обрушение ОБСЕ общественный транспорт общество ограбление Одесса Олимпийские игры ООН ОПЕК оппозиция опросы оружие отставки-назначения офшор Пакистан палеонтология Палестинская автономия Папа Римский Париж ПДД педофилия пенсионная реформа Пентагон Петр Порошенко пищевая промышленность погранвойска пожар полиция Польша похищение Почта России права человека правительство Право правозащитное движение православие «Правый сектор» преступления полицейских преступность Приморский край Продовольствие происшествия публичные лекции Рамзан Кадыров РАН Революция в Киргизии Реджеп Эрдоган рейтинги религия Республика Карелия Реформа армии РЖД ритейл Роскомнадзор Роскосмос «Роснефть» Роспотребнадзор Россельхознадзор Российская академия наук Россия Ростов-на-Дону Ростовская область РПЦ рубль русские националисты РФС Санкт-Петербург санкции Саудовская Аравия Сахалин Сбербанк Свердловская область связь связь и телекоммуникации Севастополь сельское хозяйство сепаратизм Сербия Сергей Лавров Сергей Полонский Сергей Собянин Сергей Шойгу Сирия Сколково Славянск Следственный комитет следствие смартфоны СМИ Совбез ООН Совет по правам человека Совет Федерации сотовая связь социальные сети социология Социология в России Сочи Сочи 2014 «Спартак» спецслужбы «Справедливая Россия» спутники СССР Ставропольский край стихийные бедствия Стихотворения на случай страхование стрельба строительство суды суицид Счетная палата США Таджикистан Таиланд Татарстан театр телевидение телефонный терроризм теракт терроризм технологии Трансаэро транспорт туризм Турция тюрьмы и колонии убийство уголовный кодекс УЕФА Узбекистан Украина Условия труда фармакология ФАС ФБР Федеральная миграционная служба физика Филиппины Финляндия ФИФА фондовая биржа фоторепортаж Франсуа Олланд Франция ФСБ ФСИН ФСКН футбол Хабаровский край хакеры Харьков Хиллари Клинтон химическое оружие химия хоккей хулиганство цензура Центробанк ЦИК Цикл бесед "Взрослые люди" ЦРУ ЦСКА Челябинская область Чехия Чечня ЧМ-2018 шахты Швейцария Швеция школа шоу-бизнес шпионаж Эбола эволюция Эдвард Сноуден экология экономика экономический кризис экстремизм Эстония Южная Корея ЮКОС Юлия Тимошенко ядерное оружие Якутия Яндекс Япония

Редакция

Электронная почта: politru.edit1@gmail.com
Адрес: 129090, г. Москва, Проспект Мира, дом 19, стр.1, пом.1, ком.5
Телефон: +7 495 980 1894.
Яндекс.Метрика
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003г. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2014.