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

Алонзо Чёрч родился 14 июня 1903 г. в Вашингтоне, США. Получил степень бакалавра в  Принстонском университете  в 1924 году,  и защитил  кандидатскую в 1927 г.  под  руководством  Освальда  Веблена.  В 1926 г. Черч  становится  профессором  математики  в  Принстоне.

Слава пришла к Черчу после разработки теории лямбда-исчислений. Эта теория последовала за его знаменитой статьей 1936 г., в которой он показал существование так называемых "неразрешимых задач". Статья предшествовала знаменитому исследованию Алана Тьюринга  на тему проблемы остановки, в котором также было продемонстрировано существование задач, неразрешимых механическими способами.

Впоследствии Черч и Тьюринг показали, что лямбда-исчисления и машина Тьюринга имели одинаковые свойства, таким образом доказывая, что различные "механические процессы вычислений" могли иметь одинаковые возможности. Эта работа была оформлена как тезис Черча - Тьюринга.

В терминах теории рекурсии, это утверждение формулируется как совпадение классов вычислимых и частично рекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча.

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

Используемые источники
1. matem.uspu.ru
2. calend.ru
3. ru.wikipedia.org