Charles Babbage foi um matemático e engenheiro inglês que nasceu em 1791. Entre 1819 e 1822 Babbage construiu um protótipo da máquina diferencial, uma calculadora mecânica utilizada para tabular funções polinomiais. O projeto, entretanto, não foi finalizado e em 1837 ele propôs a máquina analítica, um computador mecânico de propósito geral. O projeto nunca foi finalizado, mas diversos conceitos foram utilizados como base para o desenvolvimento de computadores eletrônicos como uma unidade lógico-aritmética, controle do fluxo de execução na forma de saltos e loops e uma memória integrada. A entrada e saída de dados seria realizada por meio de cartões perfurados inspirados em teares automáticos e que depois foram de fato utilizados em computadores eletrônicos.
Augusta Ada King, condessa de Lovelace, foi uma matemática e escritora inglesa. Ada conheceu Babbage em 1833 que lhe apresentou um protótipo da máquina diferencial. Ada se apaixonou pelo conceito e ajudou na tradução de trabalhos descrevendo as máquinas de Babbage. Acredita-se que Ada Lovelace foi a primeira a reconhecer o potencial de aplicação da máquina analítica em problemas além do cálculo de funções matemáticas. Ao traduzir um trabalho do engenheiro italiano Luigi Menabrea para o inglês, Ada fez extensas anotações e adições ao trabalho que foram posteriormente publicados de forma independente. Em em volume das notas Ada descreve um algoritmo para calcular números de Bernoulli na máquina analítica. Acredita-se que esta foi a primeira publicação de um algoritmo para execução em um computador e por isso Ada Lovelace é considerada a primeira programadora da história.
George Boole foi um matemático inglês autodidata, filósofo e lógico. Em seu primeiro livro de 1847 Boole introduziu o conceito que hoje conhecemos como álgebra booleana. Seu trabalho foi revolucionário pois foi o primeiro a combinar o campo da álgebra com o da lógica. Seu trabalho permitiu o desenvolvimento de algoritmos gerais para a análise de proposições lógicas, aumentando muito o poder de análise de que se dispunha a época para problemas de complexidade muito maior.
No sistema de Boole, as variáveis podem assumir somente dois valores lógicos, verdadeiro ou falso, usualmente representados por 1 e 0 respectivamente. As operações básicas sobre estes valores são a conjunção (e lógico, denotado $\wedge$), a disjunção (ou lógico, denotado $\vee$) e a negação (não lógico, denotado $\neg$). A partir dessa estrutura é possível codificar números inteiros, reais, operações aritméticas e diversas outras. Vocês vão estudar esse tema com bastante detalhe na disciplina de Sistemas Digitais.
David Hilbert foi um dos mais influentes matemáticos dos séculos 19 e 20. Hilbert desenvolveu vários conceitos fundamentais nas áreas de cálculo de variações, álgebra, teoria dos números, geometria, teoria espectral de operadores e suas aplicações para equações integrais, física matemática e fundamentos da matemática, em particular teoria de provas. Hilbert era tão influente em sua época que em 1900 ele iniciou a apresentação no Congresso Internacional de Matemáticos em Paris de uma série de 23 problemas que definiram o rumo da pesquisa em matemática durante o início do século 20.
Mais tarde, em 1928, Hilbert apresentou um desafio público que ficou conhecido como Entscheidungsproblem (problema de decisão). O problema pede por um algoritmo que considera como entrada uma proposição e decide se aquela proposição é universalmente válida, ou seja, se ela é válida em toda estrutura que satisfaz os axiomas da lógica de primeira ordem. Eu sei, parece complicado, e é mesmo, mas esse problema é o que deu origem ao que hoje chamamos de teoria da computação e foi resolvido independentemente por dois sujeitos brilhantes considerados os pais da moderna formulação de computação.
Alonzo Church foi um matemático e lógico americano. Para responder ao problema de decisão de Hilbert, Church começou formalizando a noção de algoritmo. Para isso ele inventou um sistema formal chamado de cálculo lambda que funciona como um modelo de computação. A implicação é gigantesca, pela primeira vez alguém tinha proposto uma definição precisa do significado do que seria realizar computação. Ele usou essa ferramenta para provar que o problema de decisão não poderia ser resolvido, isto é, ele provou que não existe um algoritmo tal qual pedido pelo problema. Essa foi a primeira demonstração de que existem problemas matemáticos que podem ser resolvidos por nenhum método.
Mesmo com esse resultado monumental, o cálculo lambda de Church não provia um caminho claro para a construção de computadores automáticos como o trabalho de Alan Turing. Apesar disso, o cálculo lambda tem ganhado bastante atenção pois serve de base para a construção de linguagens de programação funcionais.
O cálculo-$\lambda$ é o sistema proposto por Alonzo Church para definir a noção de computabilidade, trata-se de um modelo de computação. Um modelo de computação descreve como a saída de uma função matemática é produzida a partir dos dados de entrada.
Na sua forma mais simples, os termos do cálculo-$\lambda$ são construídos a partir de três regras:
Variáveis
$x$
Caractere ou palavra representando um parâmetro ou valor.