Im Jahr 1936 formulierte der amerikanische Logiker Alonzo Church einen allgemeinen Satz, der genau ausdrückt, was Berechnung bedeutet. Church hatte lange Zeit mit diesem Begriff gekämpft, den er effektive Berechenbarkeit nannte. Darunter sollte man jeden Prozeß oder jede Prozedur verstehen, die schrittweise nach wohldefinierten Regeln ausgeführt werden. Church glaubte, daß er den Begriff mittels eines formalen Systems, das λ-Kalkül genannt wird, eingefangen hatte. Genau formuliert behauptet sein Satz, daß alles, was man zu Recht als effektiv berechenbar bezeichnen kann, innerhalb des λ-Kalküls ausgedrückt werden kann.