extended (that is, have its domain enlarged) to become a total computable function? Is it possible to change the definition of a Turing machine so that a particular class of total Turing machines, computing all the total computable functions, can be found? The answer to each of these questions is no. The following theorem shows that the functions computable by machines that always halt do not include extensions of all partial computable functions, which implies the first question above has a negative answer. This fact is closely related to the algorithmic unsolvability of the halting problem. Indeed, if g were a total computable function extending f then g would be computable by some Turing machine; fix e as the index of such a machine. Build a Turing machine M, using Kleene's recursion theorem, which on input simulates the machine with index e running on an index nM for M (thus the machine M can produce an index of itself; this is the role of the recursion theorem). By assumption, this simulation will eventually return an answer. so that if g(nM) = m then the return value of M is . Thus f(nM), the true return value of M on input , will not equal g(nM). Hence g does not extend f. The second question asks, in essence, whether there is another reasonable model of computation which computes only total functions and computes all the total computable functions. Informally, if such a model existed then each of its computers could be simulated by a Turing machine. Thus if this new model of computation consisted of a sequence of machines, there would be a recursively enumerable sequence of Turing machines that compute total functions and so that every total computable function is computable by one of the machines Ti. This is impossible, because a machine could be constructed such that on input i the machine T returns . This machine cannot be equivalent to any machine on the list: suppose it were on the list at index j. Then , which does not return an integer result. Therefore, it cannot be total, but the function by construction must be total (if total functions are recursively enumerable, then this function can be constructed), which is a contradiction. This shows that the second question has a negative answer. The set of indices of total Turing machines The decision problem of whether the Turing machine