Основной тезис Черча.

Утверждение:

«Какова бы ни была вычислимая неотрицательная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей рекурсивная функция» - основной тезис Черча.

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

Приведенные гипотезы означают, что выполнение алгоритма в определенном смысле эквивалентно вычислению значений рекурсивной функции, а невозможность рекурсивной функции означает и невозможность алгоритма (так как для каждого алгоритма должна быть рекурсивная функция, а ее-то в данном случае и нет).

Напомним, что тезис Черча и следующие из него другие гипотезы не имеют доказательства и принципиально не могут быть доказаны, так как в них речь идет об алгоритмах в интуитивном смысле, не являющихся математическими объектами.