===== TESE DE CHURCH =====
A [[lexico:t:tese-de-church|tese de Church]], enunciada em 1936, afirma que uma [[lexico:f:funcao|função]] é computável no [[lexico:s:sentido|sentido]] intuitivo se ela for computável por uma [[lexico:m:maquina|máquina]] [[lexico:m:matematica|matemática]] de Turing (na [[lexico:r:realidade|realidade]], Church referiu-se a um [[lexico:m:modelo|modelo]] de computabilidade equivalente ao modelo de Turing). A [[lexico:t:tese|tese]] de Church [[lexico:n:nao|não]] é um [[lexico:t:teorema|teorema]]; é antes, a afirmativa de que um [[lexico:d:dado|dado]] modelo [[lexico:f:formal|formal]] (a [[lexico:m:maquina-de-turing|máquina de Turing]]) corresponde à [[lexico:i:ideia|ideia]] que fazemos intuitivamente do que seja realizar-se mecanicamente cálculos matemáticos.

Os dois teoremas que Alonzo Church demonstrou em 1936 a [[lexico:r:respeito|respeito]] da computabilidade de funções aritméticas mostram que há importantes limitações formais na [[lexico:n:nocao|noção]] de máquina de Turing. Church construiu uma função e mostrou que essa função não é computável; associando um [[lexico:p:predicado|predicado]] a esta função, mostrou que existem [[lexico:p:predicados|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 [[lexico:l:limitacao|limitação]] ao funcionamento dos - computadores.