View source for Machine that always halts

{{short description|Turing machine that halts for any input}}
In [[Computability theory|computability theory]], a '''machine that always halts''', also called a '''decider'''<ref>Sipser, 1996{{cn|date=March 2019}}</ref> or a '''total Turing machine''',<ref>Kozen, 1997{{page needed|date=March 2019}}</ref> is a [[Turing machine]] that eventually halts for every input.

Because it always halts, such a machine is able to ''decide'' whether a given string is a member of a [[Formal language|formal language]].  The class of languages which can be decided by such machines is exactly the set of [[Recursive language|recursive language]]s. However, the [[Halting problem|halting problem]], determining whether an arbitrary [[Turing machine]] halts on a given input, is itself an [[Undecidable problem|undecidable problem]].

== Functions computable by total Turing machines ==
{{main article|Computable function}}
In practice, many functions of interest are computable by machines that always halt.   A machine that uses only finite memory on any particular input can be forced to halt for every input by restricting its [[Control flow|flow control]] capabilities so that no input will ever cause the machine to enter an [[Infinite loop|infinite loop]].  As a trivial example, a machine implementing a finitary [[Decision tree|decision tree]] will always halt.

It is not required that the machine be entirely free of looping capabilities, however, to guarantee halting.  If we restrict loops to be of a predictably finite size (like the FOR loop in [[BASIC]]), we can express all of the primitive recursive functions (Meyer and Ritchie, 1967). An example of such a machine is provided by the [[Toy programming language|toy programming language]] PL-<nowiki/>{GOTO} of Brainerd and Landweber (1974).

We can further define a programming language in which we can ensure that even more sophisticated functions always halt.  For example, the [[Ackermann function]], which is not primitive recursive, nevertheless is a total computable function computable by a term rewriting system with a [[Well-order|reduction ordering]] on its arguments (Ohlebusch, 2002, pp.&nbsp;67).

Despite the above examples of programming languages which guarantee termination of the programs, there exists no programming language which captures exactly the total recursive functions, i.e. the functions which can be computed by a Turing machine that always halts. This is because existence of such a programming language would be a contradiction to the non-semi-decidability of the problem whether a Turing machine halts on every input.

== Relationship to partial Turing machines ==

A general Turing machine will compute a partial function.  Two questions can be asked about the relationship between partial Turing machines and total Turing machines:
# Can every partial function computable by a partial Turing machine be 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|halting problem]].

{{math theorem|1= There are Turing computable partial functions that have no extension to a total Turing computable function.  In particular, the partial function ''f'' defined so that ''f''(''n'') = ''m'' if and only if the Turing machine with index ''n'' halts on input {{val|0}} with output ''m'' has no extension to a total computable function.}}

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 {{val|0}} simulates the machine with index ''e'' running on an index ''n<sub>M</sub>'' 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. {{clarify span|Define ''M''|reason=The machine M has just been constructed, so it can't be defined again here.|date=July 2021}} so that if ''g''(''n<sub>M</sub>'') = ''m'' then the return value of ''M'' is {{tmath|m + 1}}.  Thus ''f''(''n<sub>M</sub>''), the true return value of ''M'' on input {{val|0}}, will not equal ''g''(''n<sub>M</sub>'').  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 <math>M_1,M_2,\ldots</math> of machines, there would be a recursively enumerable sequence <math>T_1,\ldots T_2,\ldots</math> of Turing machines that compute total functions and so that every total computable function is computable by one of the machines ''T<sub>i</sub>''.  This is impossible, because a machine {{mvar|T}} could be constructed such that on input ''i'' the machine ''T'' returns <math>T_i(i)+1\,</math>.  This machine cannot be equivalent to any machine {{mvar|T}} on the list: suppose it were on the list at index ''j''.  Then <math>T_j(j)=T_j(j)+1\,</math>, 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|decision problem]] of whether the Turing machine with index ''e'' will halt on every input is not decidable.  In fact, this problem is at level <math>\Pi^0_2</math> of the [[Arithmetical hierarchy|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 logic|first order]] Peano arithmetic.

In a [[Soundness|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 ==
<references />
* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley.
* Meyer, A.R., Ritchie, D.M. (1967), ''[https://www.researchgate.net/profile/Albert_Meyer/publication/234810406_The_complexity_of_loop_programs/links/00b49517fb0c8b6a2a000000.pdf The complexity of loop programs]'', Proc. of the ACM National Meetings, 465.
* Sipser, M. (2006), ''[https://www.academia.edu/download/35002661/_Sipser__2006__Introduction_to_the_Theory_of_Computation__Second_Edition.pdf 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.

{{Formal languages and grammars}}

[[Category:Turing machine]]

{{Sourceattribution|Machine that always halts|1}}