TESE DE CHURCH
A tese de Church, enunciada em 1936, afirma que uma função é computável no sentido intuitivo se ela for computável por uma máquina matemática de Turing (na realidade, Church referiu-se a um modelo de computabilidade equivalente ao modelo de Turing). A tese de Church não é um teorema; é antes, a afirmativa de que um dado modelo formal (a máquina de Turing) corresponde à ideia que fazemos intuitivamente do que seja realizar-se mecanicamente cálculos matemáticos.
Os dois teoremas que Alonzo Church demonstrou em 1936 a respeito da computabilidade de funções aritméticas mostram que há importantes limitações formais na noção de máquina de Turing. Church construiu uma função e mostrou que essa função não é computável; associando um predicado a esta função, mostrou que existem predicados (isto é, propriedades que associamos a certos objetos) não decidíveis mecanicamente. Como computadores eletrônicos são estruturalmente menos “poderosos” ainda que as máquinas de Turing, os teoremas de Church representam importante limitação ao funcionamento dos - computadores.