Важнейший вариант гёделевых теорем о неполноте был открыт Аланом Тьюрингом. Их анализ очертил путь для создания первых компьютеров. В своей работе On Computable Numbers, with an application to the Entscheidungsproblem («О вычислимых числах, приложение к проблеме разрешения»), опубликованной в 1936 г., Тьюринг предложил формализацию алгоритмических вычислений – следующую заранее написанному алгоритму – в рамках так называемой машины Тьюринга. Это математическая идеализация устройства, которое пишет символы 0 и 1 на движущейся ленте, подчиняясь конкретным правилам. Он доказал, что проблема остановки машины Тьюринга – выполнится ли окончательное вычисление для данного ввода данных – неразрешима. А значит, нет такого алгоритма, который бы предсказал, остановится ли вычисление или нет.
Тьюринг доказал свой результат, предположив, что проблема остановки разрешима, и построив алгоритм, который останавливается тогда и только тогда, когда не останавливается. Вот и противоречие. Его результат показывает, что существуют ограничения для вычислимости. Некоторые философы расширили эти идеи для определения пределов рационального мышления, и было выдвинуто предположение, что сознание не может функционировать алгоритмически. Однако их аргументы пока не так уж и убедительны. Они показали, что наивно полагать, будто мозг работает как современный компьютер, хотя это не значит, что компьютер не может имитировать работу мозга.
По мере того как на основе предшествующих теорий математики постоянно строили всё новые конструкции, одна сложнее другой, сверхструктура математики начала раскалываться из-за нераспознанных предположений, которые на поверку оказались ложными. Для предотвращения коллапса требовалась серьезная работа по укреплению фундамента.
Последующие работы углубились в истинную природу чисел, двигаясь вспять от комплексных чисел к действительным, рациональным и, наконец, натуральным. Но и там процесс не закончился. Сами числовые системы подверглись пересмотру с точки зрения еще более простых составляющих – множеств.
Теория множеств принесла немало преимуществ, включая разумную, хотя и неортодоксальную систему бесконечных чисел. Она также открыла несколько фундаментальных парадоксов, связанных с понятием множества. Их решение не стало, как надеялся Гильберт, полным обоснованием аксиоматической математики и доказательством ее логической последовательности. Но оно доказало, что математика по природе своей имеет ограничения и некоторые задачи вообще не имеют решения. В результате нам пришлось кардинально изменить свое отношение к понятиям математической истины и определенности. И это прекрасно: лучше жить в осознании пределов наших возможностей, чем в обманчивом раю.
Глава 18. Насколько это вероятно?
В XX и начале ХХI в. математика развивалась взрывными темпами. За последние 100 лет в ней было сделано больше открытий, чем за всю предыдущую историю человечества. Даже для краткого их перечисления потребуются тысячи страниц, так что придется выбирать лишь некоторые примеры из обилия доступных сведений.
Одна из самых юных областей математики – теория вероятностей, изучающая возможности появления случайных событий. Это математика неопределенности. Первые робкие шаги делались на протяжении долгих веков: это и попытки вычислить с помощью комбинаторики шансы выигрыша в азартных играх, и методы повышения точности астрономических наблюдений, несмотря на ошибки наблюдателей, но только к началу XX в. теория вероятностей приобрела статус самостоятельной науки.
Вероятность и статистика
В настоящее время теория вероятностей – обширнейшая область математики, и ее прикладная ветвь, статистика, оказывает важное влияние на повседневную жизнь – возможно, более значительное, чем любой из прочих основных разделов математики. Статистика стала одним из главных аналитических методов даже в медицине. Ни одно лекарственное средство не допускается на рынок и ни один метод лечения не разрешается в больнице, пока клинические испытания не докажут их полную безопасность и эффективность. Здесь безопасность относительна: лечение может быть предложено больным, страдающим от смертельно опасного недуга, когда шансы на успех слишком малы, но не в менее тяжелых случаях.
Также теория вероятностей чаще всех прочих областей математики страдает от неверного толкования и искажений. Но ее точное и разумное применение приносит человечеству неоценимую пользу.
Игра случая
Некоторые вопросы из теории вероятностей уходят корнями в Античность. Из Средних веков до нас дошли записи дискуссий о шансе выбросить различные числа на двух игральных костях. Чтобы лучше представить себе, как это работает, начнем с одной кости. Предположим, она не доработана[8] – что очень трудно доказать – и на ней шесть чисел: 1, 2, 3, 4, 5 и 6, которые выпадают одинаково часто в конечном счете при длительной игре. В короткой игре такое равноправие невозможно: первый бросок, например, даст в результате только одно из чисел. Даже после шести бросков вы, скорее всего, не получите по одному разу каждое из чисел. Но в длинных сериях бросков, или попыток, мы вправе ожидать появления каждого числа примерно в каждом шестом броске, т. е. вероятность равна 1/6. Если этого не происходит, то у кости, вероятно, смещен центр тяжести.
Событие с вероятностью 1 достоверно, а с вероятностью 0 – невозможно. Все вероятности лежат между 0 и 1, и вероятность события обозначает долю в числе попыток, с которой происходит данное событие.
Вернемся к вопросу из Средних веков. Предположим, мы одновременно бросаем два кубика (как во многих играх – от костей до «Монополии»). Какова вероятность того, что сумма очков на них равна 5? По результатам вычислений с огромным числом аргументов и даже нескольких экспериментов получено число 1/9. Почему? Предположим, мы взяли две кости, красную и синюю. На каждой из них может независимо выпасть шесть разных чисел, итого получаем 36 возможных пар, и все с одинаковой вероятностью. Сочетания (красная + синяя), дающие 5, – 1 + 4, 2 + 3, 3 + 2, 4 + 1; это отдельные случаи, поскольку синяя кость выдает разные числа при каждом броске, как и красная. Значит, при большом количестве бросков мы ожидаем получить сумму, равную 5, в четырех случаях из 36: вероятность равна 4/36 = 1/9.
Другая давняя практическая проблема – как поделить ставки в азартной игре, если она по какой-то причине прервалась. Алгебраисты Возрождения Пачоли, Кардано и Тарталья оставили записи по этому вопросу. Позже шевалье де Мере задал тот же вопрос Паскалю, и тот обменялся с Ферма несколькими письмами на эту тему.
Из этих ранних работ следовал неявный вывод, какова вероятность и как ее подсчитать. Но всё это выглядело неопределенно и неубедительно.
Сочетания
Рабочее определение вероятности некоего события – относительное число случаев, в которых оно происходит. Если речь о кости, у которой может одинаково часто выпасть любая из шести граней, вероятность выпадения каждой грани равна 1/6. Более ранние работы по вероятности основаны на подсчете количества вариантов появления каждого события и делении его на общее число возможностей.
Главной проблемой здесь были сочетания. Скажем, если взять колоду из шести карт, сколько в ней будет разных подмножеств по четыре карты? Один из способов – перечислить все эти подмножества: если у нас карты с достоинством 1–6, получится:
т. е. их всего 15. Но такой метод слишком громоздкий для большего количества карт, и здесь нужно нечто более систематическое.
Представим, что мы выбираем по одному элементу из подмножества. Первый можно выбрать шестью способами, второй только пятью (один использован), третий – четырьмя, четвертый – тремя. Общее число выборов в этом порядке равно 6 × 5 × 4 × 3 = 360. Но каждое подмножество сосчитано здесь 24 раза: начав с 1234, далее мы найдем 1243, 2134 и т. д. и получим 24 способа (4 × 3 × 2) переставить четыре объекта. Значит, точный ответ будет 360/24, т. е. 15. Этот аргумент показывает, что количество способов выбрать m объектов из общего числа n объектов равно:
Это выражение называется биномиальным коэффициентом, потому что появляется и в алгебре. Если мы преобразуем его в таблицу, чтобы n-я строка содержала биномиальные коэффициенты
то результат будет выглядеть так.
В шестой (счет начинается с нуля) строке мы увидим числа 1, 6, 15, 20, 15, 6, 1.
Сравним с формулой
(x + 1)6 = x6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1,
и мы видим, что те же числа появляются как коэффициенты. Это не совпадение.
Треугольник чисел назван треугольником Паскаля, потому что обсуждался Паскалем в 1655 г. Однако известен он был гораздо раньше: первое упоминание в древнеиндийском шастре «Чандас шастра» датируется примерно 950 г. Также его знали персидские математики Аль-Караджи и Омар Хайям (в современном Иране его называют треугольником Хайяма).
Треугольник Паскаля
Теория вероятностей
Биномиальные коэффициенты с большим успехом были использованы в первой книге по теории вероятностей – труде под названием «Искусство предположений», написанном Якобом Бернулли в 1713 г. В книге автор поясняет столь необычное название.
Мы определяем искусство предположений, или стохастическое искусство, как искусство точной оценки вероятностей, чтобы в наших суждениях и действиях мы всегда опирались на то, что признано лучшим, наиболее приемлемым, наиболее определенным или рекомендуемым; это единственная основа для мудрости философа и благоразумия государственного мужа.