Случайность в арифметике

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