 Definition 5.1 A computable or recursive function on the naturals is one that can be computed by a Turing machine. The program of a Turing machine M can be assigned a Gödel number \({\Corner{M}}\). For natural numbers \(e,n\), to convey that the Turing machine with Gödel number e computes a number m on input n, we use the notation \(\{e\}(n)\) for m.