En la década de 1930, uno de los problemas más estudiados por los matemáticos era el Entscheidungsproblem propuesto por David Hilbert: dada una proposición en un sistema formal, ¿existe un algoritmo tal que pueda decidir si la proposición es cierta (y por tanto es un teorema del sistema) o por el contrario es falsa? En 1936 Alonzo Church y Alan Turing probaron, de forma independiente, la imposibilidad de la existencia de tal algoritmo, usando el cálculo lambda en el caso de Church y la máquina de Turing en el caso de Turing.