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

ЧЁРЧА ТЕЗИС

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

  1. черча тезис—Чорча тэзс...Русско-белорусский математический словарь