Класс алгоритмически вычислимых частичных числовых функций

Этот тезис дает алгоритмическое толкование понятие отчасти рекурсивной функции. Его нельзя обосновать, так как он связывает нестрогое математическое понятие интуитивно вычислимой функции со серьезным математическим понятием отчасти рекурсивной функции. Но исследования, проводившиеся очень многими математиками в течение нескольких десятилетий, выявили полную необходимость считать понятие отчасти рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.

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