Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Тезис Черча. Алгоритмически неразрешимые проблемы.

Словосочетание «решить задачу» допускает множество толкований. В математике иногда решают задачи с привлечением интуиции путем озарения: решение возникает вдруг и остается только проверить его правильность. Будем рассматривать решения с позиции алгоритмической: задача может быть решена, если построен алгоритм, приводящий к результату — решению задачи. Если сумеем для некоторой задачи построить алгоритм, ее решающий, то будем говорить, что задача алгоритмически разрешима. Но даже если не построили алгоритм, а только каким-либо математическим методом доказали, что алгоритм может быть построен, то и тогда будем считать задачу алгоритмически разрешимой. Во многих случаях алгоритм без труда или с большим трудом может быть найден. Но что означает ситуация, когда не удалось найти необходимый алгоритм?

Долгое время математики были уверены, что любая задача в конце концов может быть решена, нужно лишь приложить адекватные усилия. Составлялись перечни еще не решенных задач, чтобы обратить внимание коллег на необходимость «выровнять фронт» исследований в той или иной области математики. Наиболее известен в истории математики один из таких призывов, сделанный 8 августа 1900 г. Д. Гильбертом на Международном Конгрессе математиков в Париже.

Это убеждение в разрешимости каждой математической проблемы является для нас большим подспорьем в работе; мы слышим внутри себя постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления; ибо в математике не существует Ignorabimus (мы не будем знать)!»

Затем Гильберт перечисляет и анализирует 23 открытых,проблемы. Для  нас наиболее интересна 10-я проблема.