domain to a proof. Different versions of constructivism will diverge on this point. Kleene's realizability theory identifies the functions with the computable functions. It deals with Heyting arithmetic, where the domain of quantification is the natural numbers and the primitive propositions are of the form x = y. A proof of x = y is simply the trivial algorithm if x evaluates to the same number that y does (which is always decidable for natural numbers), otherwise there is no proof. These are then built up by induction into more complex algorithms. If one takes lambda calculus as defining the notion of a function, then the BHK interpretation describes the correspondence between natural deduction and functions. References Dependently typed programming Functional programming Constructivism (mathematics)