 As usual for such a proof, "computable" means computable by any model of computation that is Turing complete.Church's proof first reduces the problem to determining whether a given lambda expression has a "normal form".A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form.