with index e will halt on every input is not decidable. In fact, this problem is at level of the arithmetical hierarchy. Thus this problem is strictly more difficult than the Halting problem, which asks whether the machine with index e halts on input 0. Intuitively, this difference in unsolvability is because each instance of the "total machine" problem represents infinitely many instances of the Halting problem. Provability One may be interested not only in whether a Turing machine is total, but also in whether this can be proven in a certain logical system, such as first order Peano arithmetic. In a sound proof system, every provably total Turing machine is indeed total, but the converse is not true: informally, for every first-order proof system that is strong enough (including Peano arithmetic), there are Turing machines which are assumed to be total, but cannot be proven as such, unless the system is inconsistent (in which case one can prove anything). The proof of their totality either rests on some assumptions or require another proof system. Thus, as one can enumerate all the proofs in the proof system, one can build a Turing machine on input n that goes through the first n proofs and look for a contradiction. If it finds one, it gets into an infinite loop and never halts; otherwise, it halts. If the system is consistent, the Turing machine will halt on every input, but one cannot prove this in a strong enough proof system due to Gödel's incompleteness theorems. One can also create a Turing machine that will halt if and only if the proof system is inconsistent, and is thus non-total for a consistent system but cannot be proven such: This is a Turing machine that, regardless of input, enumerates all proofs and halts on a contradiction. A Turing machine that goes through Goodstein sequences and halts at zero is total but cannot be proven as such in Peano arithmetic. See also BlooP and FlooP Total functional programming Termination analysis References Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley. Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465. Sipser, M. (2006), Introduction to the Theory of Computation, PWS Publishing Co. Kozen, D.C. (1997), Automata and Computability, Springer. Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer. Turing machine