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