===== TESE DE CHURCH =====
A [[lexico:t:tese-de-church:start|tese de Church]], enunciada em 1936, afirma que uma [[lexico:f:funcao:start|função]] é computável no [[lexico:s:sentido:start|sentido]] intuitivo se ela for computável por uma [[lexico:m:maquina:start|máquina]] [[lexico:m:matematica:start|matemática]] de Turing (na [[lexico:r:realidade:start|realidade]], Church referiu-se a um [[lexico:m:modelo:start|modelo]] de computabilidade equivalente ao modelo de Turing). A [[lexico:t:tese:start|tese]] de Church [[lexico:n:nao:start|não]] é um [[lexico:t:teorema:start|teorema]]; é antes, a afirmativa de que um [[lexico:d:dado:start|dado]] modelo [[lexico:f:formal:start|formal]] (a [[lexico:m:maquina-de-turing:start|máquina de Turing]]) corresponde à [[lexico:i:ideia:start|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:start|respeito]] da computabilidade de funções aritméticas mostram que há importantes limitações formais na [[lexico:n:nocao:start|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:start|predicado]] a esta função, mostrou que existem [[lexico:p:predicados:start|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:start|limitação]] ao funcionamento dos - computadores.

{{indexmenu>.#1|skipns=/^playground|^wiki/ nsonly}}