Гильберт. Основания математики

На IX Международном конгрессе математиков, проходившем в 1928 году в Болонье, Гильберт воспользовался случаем, чтобы предложить свой план по спасению математики и обозначить следующий вопрос: существует ли механическая процедура, которая решала бы все и каждую проблему математики, алгоритм, способный принципиально разрешить все математические вопросы, который при заданной математической пропозиции дал бы нам знать, является она теоремой или нет? Другими словами, является ли она разрешимой в математике? Как и на вопросы непротиворечивости и полноты, ответ на нее был отрицательным. После теорем Гёделя стало ясно, что ответ на эту проблему — категорическое «нет», поскольку математика является неполной: предполагаемый алгоритм в течение бесконечного времени «думал» бы над неразрешимым высказыванием, поскольку ни оно, ни его отрицание не являются теоремой. Следовательно, ответ на проблему разрешения оставалось дать только для логики первого порядка, которая, напомним, является полной. Однако в 1936 году Алан Тьюринг (1912-1954) и независимо от него Алонзо Чёрч (1903-1995) доказали, что логика первого порядка также неразрешима.

Тезис Чёрча — Тьюринга

Для начала Тьюринг сформулировал, что означает думать как машина, механически. Его первая победа заключалась в определении понятия вычислимой функции: это функция, которую способна вычислить машина Тьюринга — вид компьютера без ограничений в пространстве или времени. Одновременно, по другую сторону Атлантического океана, Чёрч пришел к аналогичным выводам, разработав формальную систему, которую назвал лямбда-исчислением. С тех пор под названием тезиса Чёрча — Тьюринга известен постулат, утверждающий, что любое альтернативное определение вычислимости равносильно определению, данному Тьюрингом в терминах его машин. Прибегнув к изобретательному варианту диагонального аргумента Кантора, Тьюринг доказал, что существует намного больше функций, чем машин Тьюринга. Другими словами, существуют невычислимые функции.

Исчислимые функции, как и машины Тьюринга, имеются в счетном количестве, то есть они как иголки в стоге сена всех функций.