Случайность в арифметике
    Невозможно доказать, конечное или бесконечное число решений имеет каждое уравнение из семейства алгебраических уравнений: ответ варьирует случайным образом, и, следовательно, не может быть найден с помощью математического рассуждения Грегори Дж.Чейтин
    Что может быть бесспорнее того факта, что 2 плюс 2 равняется 4? Со времён древних греков математики считали, что более несомненной вещи, чем доказанная теорема, не сыскать. Действительно, математические утверждения, истинность которых может быть доказана, часто считались более надёжным основанием для системы мышления, чем любой моральный или даже физический принцип. Немецкий философ и математик XVIIвека Готфрид Вильгельм Лейбниц считал возможным создать "исчисление" рассуждений, которое когда-нибудь позволит улаживать все споры с помощью слов: "Давайте вычислим, господа!". К началу нашего столетия прогресс в разработке символической логики дал основание немецкому математику Давиду Гильберту заявить, что все математические вопросы в принципе разрешимы, и провозгласить окончательную кодификацию методов математического рассуждения.
    В 30-е годы нашего столетия этот оптимизм совершенно развеялся под влиянием удивительных и глубоких открытий К.Гёделя и А.Тьюринга. Гёдель доказал, что не существует системы аксиом и методов рассуждения, охватывающей все математические свойства целых положительных чисел. Позднее Тьюринг облёк остроумные, но сложные гёделевы доказательства в более понятную форму. Как показал Тьюринг, гёделева теорема о неполноте эквивалентна утверждению, что не существует общего метода для систематического принятия решения о том, остановится ли когда-нибудь компьютерная программа, т.е. приведёт ли она когда-нибудь компьютер к остановке. Разумеется, если некоторая конкретная программа приводит к остановке компьютера, этот факт легко может быть доказан непосредственным выполнением этой программы. Трудность заключается в доказательстве того, что произвольно взятая программа не останавливается.
    Недавно мне удалось сделать ещё один шаг по пути, намеченному Гёделем и Тьюрингом. Преобразовав некоторую конкретную компьютерную программу в алгебраическое уравнение такого типа, который был знаком ещё древним грекам, я показал, что область чистой математики, известная под названием теории чисел, содержит в себе случайность. Это исследование демонстрирует, говоря словами Эйнштейна, что Бог порой использует целые числа для игры в кости.
    Полученный результат, входящий составной частью в то, что было названо алгоритмической теорией информации, не является причиной для пессимизма; он не вносит в математику анархию. (В самом деле, большинство математиков продолжают работать над своими проблемами, как и раньше.) Он означает лишь, что в некоторых ситуациях должны применяться математические законы особого рода - статистические. Подобно тому как физика не в состоянии предсказать, в какой именно момент распадётся данный атом радиоактивного вещества, математика порой бессильна дать ответ на некоторые вопросы. Однако физики могут надёжно предсказать средние значения физических величин, отнесённые к большому количеству атомов. Математики в некоторых случаях должны, вероятно, ограничиваться таким же подходом.
    Моя работа служит естественным продолжением работы Тьюринга, однако если Тьюринг анализировал, остановится или нет произвольная программа, я рассматриваю вероятность того, что универсальный компьютер прекратит работу, если его программа выбрана совершенно случайно. ............