Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть[1]. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Тезис был высказан Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов[2][3][4][5]. Существенен для многих областей науки и философии науки, в том числе для математической логики, теории доказательств, информатики, кибернетики.
В терминах теории рекурсии, тезис формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча[6].
Более общая формулировка была дана Стивеном Клини, согласно которой все частичные (то есть не обязательно определённые для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными[7].
В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга[8]. Иногда в такой формулировке фигурирует как тезис Тьюринга. Ввиду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.
Одной из важных проблем для логиков в 1930-х годах была проблема разрешения: существует ли механическая процедура для отделения математических истин от математических ложностей. Эта задача требовала, чтобы понятие «алгоритм» или «эффективная вычислимость» было закреплено, по крайней мере, чтобы приступить к задаче[9] С самого начала и по сей день (по состоянию на 2007 год) продолжаются дебаты:[10]. было ли понятие «эффективной вычислимости» (i) «аксиомой или аксиомами» в аксиоматической системе или (ii) просто определением, которое «идентифицировало» два или более предложений или (iii) эмпирической гипотезой, которую следует проверить на естественных событиях или (iv) или просто предложением ради аргумента (то есть «тезиса»).