Тезис Чёрча
Те́зис Чёрча, принцип, согласно которому класс функций, вычислимых с помощью алгоритмов в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Тезис Чёрча – это естественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю её историю. Все известные в математике примеры алгоритмов удовлетворяют ему. Тезис Чёрча впервые высказан А. Чёрчем (1936). Различным уточнениям интуитивного понятия алгоритма соответствуют свои формулировки тезиса Чёрча. Тезис Тьюринга заключается в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью некоторой машины Тьюринга, а принцип нормализации Маркова – в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью некоторого нормального алгорифма. Из эквивалентности известных уточнений понятия алгоритма следует эквивалентность соответствующих вариантов тезиса Чёрча. Этот факт является ещё одним подтверждением тезиса Чёрча. Тезис Чёрча не может быть строго доказан, т. к. в его формулировке участвует неточное понятие «алгоритм в интуитивном смысле». Были попытки опровергнуть тезис Чёрча, однако они к успеху не привели. Принятие тезиса Чёрча полезно в теории алгоритмов и её приложениях. Во-первых, при доказательстве существования тех или иных конкретных алгоритмов – машин Тьюринга, рекурсивных функций, нормальных алгорифмов и др. – можно, опираясь на тезис Чёрча, ограничиваться интуитивно ясными построениями и не выписывать соответствующие формальные схемы.
Кроме того, тезис Чёрча является основанием для вывода о неразрешимости данной алгоритмической проблемы, после того как строго доказано, что эта проблема не может быть решена в рамках того или иного уточнения понятия алгоритма.