Alonzo Church

Imagem: Catedrales e Iglesias · BY · Openverse

Partindo em busca do que seria um procedimento efetivo ou mecânico (o que pode ser feito seguindo-se diretamente um algoritmo ou conjunto de regras ), surgiram a sistematização e desenvolvimento das "funções recursivas". O cálculo-lambda (componente característico fundamental da linguagem de programação LISP) de Alonzo Church, tornou pública a possibilidade da definição bem elaborada de processo efetivo. O teorema de Church n.º1 consiste fundamentalmente na demonstração de que não existe algoritmo capaz de enumerar as expressões não válidas, de maneira que fica excluído a priori todo procedimento de decisão para as expressões do "Cálculo de predicados". Church também era interessado no problema da indecibilidade de Hilbert (Entscheidungsproblem). Church tinha alcançado resultados, empregando o conceito de lambda-definibilidade (ao invés do computável por uma máquina de Turing definido por Turing), mostrando assim que lambda-definibilidade é equivalente ao conceito de recursividade de Gödel-Herbrand. O cálculo-lambda, como sistema elaborado por Church para ajudar a fundamentar a Matemática era inconsistente, mas a parte do cálculo-lambda que tratava de funções recursivas estava correta e teve sucesso. Usando sua teoria, Church propôs uma formalização da noção de "efetivamente computável", através do conceito de lambda-definibilidade. Desta forma mostrou que o sistema de procedimentos de Turing eram equivalente à lambda-definibilidade. O trabalho de Church e Turing fundamentalmente liga os computadores com as máquinas de Turing. Os limites das Maquinas de Turing, de acordo com a tese de Church-Turing, também descreve os limites de todos os computadores.