  Since a Turing machine might not halt on certain inputs, we have to be careful in how we define functions computable by Turing machines. Let the natural numbers, \(\mathbf{N}\), be the set \(\{0,1,2,\ldots \}\) and let us consider Turing machines as partial functions from \(\mathbf{N}\) to \(\mathbf{N}\).