Тезис Чёрча-Тьюринга (часто сокращается как тезис ЧТ) утверждает следующее:

Всякая эффективно вычислимая функция — вычислима по Тьюрингу.

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

Тезис Чёрча-Тьюринга — это не четко определенное математическое утверждение, а индуктивное утверждение, которое заявляет, что каждая разумная модель вычислений, которую мы можем придумать, эквивалентна или хотя бы сводима к модели, предложенной Тьюрингом. Таким образом, мы не можем доказать его в математическом смысле, но можем собирать свидетельства в его пользу.

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

Тезис ЧТ имеет множество последствий для информатики в целом, искусственного интеллекта, эпистемологии и других областей знания.