Математическая энциклопедия - чёрча тезис

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

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985