O ano de 1936 é fundamental na história da computação, pois nesse ano  importantes trabalhos foram divulgados. Dentre esses trabalhos, destacam-se “On Computable Numbers with an aplication to the Entscheidungsproblem”, de Alan Turing, e “An Unsolvable problem of Number Theory”, de Alonso Church, ambos no âmbito da computabilidade. Church e Turing definiram em seus trabalhos – produzidos de maneira independente, por incrível que pareça – os limites da computação, na medida em que especificaram modelos matemáticos que podem computar tudo que for computável (de uma forma simplificada, este é o conceito de modelos universais de computação).

Para quem conhece o modelo de Turing,  que é bem mais difundido que o de Church, a asserção acima é bem impressionante, dada a simplicidade desse modelo. Realmente, é muito intrigante a idéia de que uma simples máquina que, resumidamente, é apenas composta de um conjunto de estados, uma função de transição, um alfabeto de entrada e uma fita infinita, possa realizar um processamento digital de imagens (ela pode, só vai demorar um pouquinho!) , por exemplo. Ainda mais intrigante é o fato provado por Alex Smith, estudante britânico de computação, em 2007: pode-se construir uma máquina Turing universal que contenha apenas dois estados e três símbolos no alfabeto de entrada. A prova continha quarenta páginas.

Mas falar de máquina de Turing não traz muitas novidades, devido a sua grande difusão. Vamos falar um pouco (bem pouco, leia mais a respeito) sobre o modelo de Church, o cálculo lambda, que infelizmente não é muito conhecido. O cálculo lambda é um sistema formal baseado em funções e recursividade, que pode ser resumido a duas operações: definição de funções e transformações (substituições de variáveis). Em cálculo lambda, tudo é representado como funções, inclusive constantes (leia sobre os numerais de church). Turing, em 1937, divulgou um trabalho onde ele provou a equivalência entre o cálculo lambda e a máquina de Turing.

Os modelos universais, porém, não pararam no ano de 1936. Outro modelos, definidos posteriormente, também são tão poderosos quanto “os pioneiros”. Dentre eles, temos a máquina de Post, a máquina norma e a máquina de registradores. Todos esses modelos, apesar de serem tão importantes, parecem condenados ao ostracismo. Uma consequência disso é a falta de compreensão dos alunos de computação a respeito da computabilidade, que muitas vezes é associada apenas à máquina de Turing.