Исчислимые функции, как и машины Тьюринга, имеются в счетном количестве, то есть они как иголки в стоге сена всех функций.
Наконец, рассмотрев проблему остановки, он предложил отрицательный ответ на вопрос Гильберта — Entscheidungsproblem: если бы существовала эта процедура, она также была бы способна определить за конечное время, останавливается любая машина Тьюринга через конечное число шагов или входит в бесконечную петлю, когда на входе вводятся некоторые данные. Но последнее, как он доказал, невозможно. Не существует алгоритма, способного получить на входе логическое или математическое высказывание и выдать на выходе: «теорема» или «не теорема» (хотя свойство выводимости действительно разрешимо в ограниченной логике пропозиций).
Сланцевая статуя и портрет Алана Тьюринга в музее Блетчли-Парка.
Это означает, что теории первого порядка не могут контролировать кардинальное число своих моделей. Так, например, если сформулировать аксиомы арифметики Пеано в логике второго порядка (неполной), то они категориальны (то есть все их возможные модели изоморфны, имеют одно и то же кардинальное число), но если сформулировать их в логике первого порядка (полной), то мы расплачиваемся тем, что теряем категориальность. Появятся стандартная и нестандартная модели натуральных чисел. Скупость логика имеет свою цену.
Вскоре Гёдель предположил, что континуум-гипотеза Кантора, которую в 1925 году Гильберт считал почти доказанной на основе выведенной из его теории доказательства изящной техники, была примером неразрешимого высказывания в привычной теории множеств. В 1938 году, ограничиваясь подмножеством конструктивных множеств, Гёдель доказал: невозможно доказать, что она ложная в ZFC. И обратно, в 1963 году Пол Коэн (1934-2007), использовав метод форсинга, доказал: также невозможно доказать, что она истина в ZFC. Гёдель и Коэн построили модели, в которых гипотеза истинна и ложна соответственно. Так что ни утверждение, ни отрицание континуум-гипотезы недоказуемо. То же самое происходит с аксиомой выбора, непротиворечивость и независимость которой относительно остальных аксиом также доказали оба математика. Следовательно, статус аксиомы выбора и континуум-гипотезы в теории множеств аналогичен статусу аксиомы параллельных прямых в геометрии. Рай Кантора — не единственный доступный рай теории множеств.
Программа Гильберта выбыла с поля боя после двух ударов, полученных от Гёделя. Как первая, так и вторая проблемы знаменитого списка из 23 проблем Гильберта в итоге оказались решены, хотя и способом, который в 1900 году было трудно вообразить. В математике истинное не совпадает с доказуемым. Аксиом и правил выведения, которые Гильберт поставил во главу угла, было недостаточно, чтобы вывести все математические теоремы, при этом можно представить себе пропозиции истинные, но невыводимые в формальной системе классической математики. «Арифметика непротиворечива» — вот пример этого типа неразрешимых пропозиций. Гильберт, узнав о теоремах Гёделя спустя несколько дней (благодаря Бернайсу), попытался спасти часть своей программы, позволив использование нефинитных методов для доказательства непротиворечивости математики. Но эти методы совсем не очевидны. Гильберт и его команда походили на пастухов, которые построили убежище, чтобы защитить стадо от волков, но не могли быть уверены в том, что внутри нет ни одного волка.
Несмотря на то что скептические сомнения так и не были устранены, классическая математика все же чувствовала себя неплохо. Твердость и энтузиазм Гильберта смогли поддерживать курс большого корабля математики. С точки зрения обоснования математики формализм был отправлен в нокаут, но в отношении философии математики выиграли по очкам.
Часто говорят, что платоническая позиция лучше всего характеризует отношение математика к сути этой дисциплины. Математик верит в реальность математических объектов. Но, конечно, когда философы начинают одолевать его своими вопросами, он бежит и прячется под юбкой формализма и заявляет: «Математика — всего лишь сочетание знаков, лишенных значения, красивая игра формул, еще интереснее, чем шахматы». Но при этом ее отношение к их реальному значению скрыто сумерками: если нужна точность, надо исключить любое значение; но если нужно, чтобы математика имела смысл, нужно отказаться от точности. Для строгого формалиста любая математическая теория — всего лишь сочетание знаков, не имеющих значения, как иероглиф, лишенный смысла. Большинство математиков являются платонистами по будням, пока работают с теоремами, пропозициями и выводами, и становятся формалистами по выходным, когда оставляют работу и беседуют с философами.