Alonzo Church

Alonzo Church
Nascimento	14 de junho de 1903 ; Washington, D.C. , Estados Unidos
Morte	8 de novembro de 1995 (92 anos) ; Hudson , Ohio
Sepultamento	Cemiterio de Princeton
Nacionalidade	estadunidense
Cidadania	Estados Unidos
Alma mater	Universidade de Princeton
Ocupacao	matematico , filosofo , professor universitario , cientista de computacao
Empregador(a)	Universidade de Princeton , Universidade da California em Los Angeles
Orientador(a)(es/s)	Oswald Veblen
Orientado(a)(s)	Curtis Anthony Anderson , Peter Andrews , George Alfred Barnard , Martin Davis , Alfred Leon Foster , Leon Henkin , David Kaplan , John George Kemeny , Stephen Kleene , Michael Rabin , Hartley Rogers, Jr , John Barkley Rosser , Nathan Salmon , Dana Scott , Raymond Smullyan , Alan Turing
Instituicoes	Universidade de Princeton (1929?1967) ; University of California, Los Angeles (1967?1995)
Campo(s)	matematica e logica
Tese	1927: Alternatives to Zermelo's Assumption
Obras destacadas	Tese de Church-Turing , Principio de Church-Turing-Deutsch , Frege?Church ontology, Teorema de Church-Rosser , Church?Turing theorem, calculo lambda
Religiao	presbiterianismo
	[ edite no Wikidata ]

Alonzo Church ( Washington, DC , 14 de junho de 1903 ? Hudson (Ohio) , 8 de novembro de 1995 ) foi um matematico estadunidense .

Atuou principalmente nas areas de logica matematica , teoria da recursao e teoria da computacao . Entre suas maiores contribuicoes, estao o calculo lambda , um sistema matematico formal que investiga funcoes, aplicacao de funcoes. Influenciou as linguagens de programacao, principalmente as linguagens funcionais, como o LISP (LISP 'puro' pode ser chamada de uma linguagem funcional verdadeira).

A Tese de Church-Turing [ editar | editar codigo-fonte ]

Partindo em busca do que seria um procedimento efetivo ou mecanico (o que pode ser feito seguindo-se diretamente um algoritmo ou conjunto de regras ), surgiram a sistematizacao e desenvolvimento das "funcoes recursivas". O calculo-lambda (componente caracteristico fundamental da linguagem de programacao LISP) de Alonzo Church, tornou publica a possibilidade da definicao bem elaborada de processo efetivo.

O teorema de Church n.º1 consiste fundamentalmente na demonstracao de que nao existe algoritmo capaz de enumerar as expressoes nao validas, de maneira que fica excluido a priori todo procedimento de decisao para as expressoes do "Calculo de predicados".

Church tambem era interessado no problema da indecibilidade de Hilbert ( Entscheidungsproblem ). Church tinha alcancado resultados, empregando o conceito de lambda-definibilidade (ao inves do computavel por uma maquina de Turing definido por Turing), mostrando assim que lambda-definibilidade e equivalente ao conceito de recursividade de Godel-Herbrand. O calculo-lambda, como sistema elaborado por Church para ajudar a fundamentar a Matematica era inconsistente, mas a parte do calculo-lambda que tratava de funcoes recursivas estava correta e teve sucesso. Usando sua teoria, Church propos uma formalizacao da nocao de "efetivamente computavel", atraves do conceito de lambda-definibilidade. Desta forma mostrou que o sistema de procedimentos de Turing eram equivalente a lambda-definibilidade. O trabalho de Church e Turing fundamentalmente liga os computadores com as maquinas de Turing. Os limites das Maquinas de Turing, de acordo com a tese de Church-Turing, tambem descreve os limites de todos os computadores.

Como foi observado, a maquina de Turing pode ser interpretada como um algoritmo. Efetivamente toda acao de uma maquina algoritmica, como o computador pode ser considerada, se resume a calcular o valor de uma funcao §2 com determinados argumentos. Este fato e interessante, pois da uma maneira de se medir a capacidade computacional de uma maquina. Uma maquina que compute mais funcoes que outra e mais poderosa. A partir dos resultados de Kurt Godel , Alan Turing e Church, pode-se dizer que existem funcoes para as quais nao existe uma sequencia de passos que determinem o seu valor, com base nos seus argumentos. Dizendo-se de outra maneira, "nao existem algoritmos para a solucao de determinadas funcoes". Sao as chamadas "funcoes nao computaveis". Isto significa que para tais funcoes nao ha nem havera capacidade computacional suficiente para resolve-las. Logo, descobrir as fronteiras entre funcoes computaveis e nao computaveis e equivalente a descobrir os limites do computador em geral. A tese de Church-Turing representa um importante passo nesse sentido. Eles perceberam que o poder computacional das Maquinas de Turing se resumia a qualquer processo algoritmico, ou seja, todas as funcoes computaveis que pudessem ser descritas por algoritmos. Isto foi a contribuicao dada pelo trabalho de Turing e Church. As funcoes computaveis sao as mesmas funcoes Turing-computaveis. A importancia disso esta na possibilidade de se verificar o alcance e limites de um computador.

Um celebre teorema de Alonzo Church (1903-1995) demonstrou em 1936 que nao pode existir um procedimento geral de decisao para todas as expressoes do Calculo de Predicados de 1a ordem , ainda que exista tal procedimento para classes especiais de expressoes de tal calculo.
O processo que determina o valor de uma funcao atraves dos argumentos dessa funcao e chamado de calculo da funcao (ou computar uma funcao).