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

Суть тезиса заключается в следующем:

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

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