ТЕЗИС ТЬЮРИНГА-ЧЕРЧА

тезис, согласно которому класс функций, вычислимых посредством алгоритмов, совпадает с классом частично рекурсивных функций, вычислимых посредством машины Тьюринга. В определении рассматриваемого тезиса содержится целый ряд интуитивных моментов, которые уточняются в теории алгоритмов. Тезис Тьюринга — Черча дает весьма конкретное истолкование взаимной сопряженности математики и техники. Пенроуз Р. Новый ум короля: о компьютерах, мышлении и законах физики. М., 2002.