The page "Decider" re-directs here. For the controversial George W. Bush remark, see The Decider.

In computability theory, a machine that always halts — also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997) — is any model of computation that, contrary to the most general Turing machines, is guaranteed to halt for any particular input.

Because it always halts, the machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is exactly the set of recursive languages. It is important to note, however, that, due to the Halting Problem, determining whether an arbitrary Turing machine always halts is undecidable - there is no algorithm for it. The set of all machines that always halt is only recursively enumerable.

In practice, it is possible to construct a machine that always halts, and yet computes many functions of interest, by restricting its flow control capabilities so that no program will ever cause the machine to enter an infinite loop. As a trivial example, a finitary decision tree can contain no loops whatsoever, so it naturally always halts. It is not required that the machine be entirely free of looping capabilities, however. If we restrict loops to be of a predictably finite size (not unlike 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 PL-{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 always halts, and we can guarantee that property by casting it as a term rewriting system with a reduction ordering on its arguments (Ohlebusch, 2002, pp.67). This is similar to using mathematical induction to prove that a recursive function always reaches its base case.

Note, however, that there will always be programs that always halt that are not expressible in such restricted models. In fact, the following theorem shows that machines that always halt are strictly less powerful than Turing machines:

There are (Turing-)computable total functions that are not computable by any machine that always halts.

Proof: The proof parallels Theorem 2.3 of Brainerd and Landweber (1974) for the PL-{GOTO} language, and proceeds by a diagonal argument. Let F be the set of all functions computable by a machine that always halts. These functions are total since the machine halts on any input. As usual, and without loss of generality, we can take these functions to map naturals to naturals. Our goal is to find a computable total function g(n), with $g,n\; \backslash in\; N$, that is not in F.

By the definition of F, for every function f in F there is a machine description (or a program) d that computes f upon execution. We denote the execution of d by double square brackets, thus d(n) = f(n). Since any description makes the machine halt at some point, it is not hard to see that the set of machine descriptions D that lead to total functions is effectively enumerable. Let d_n = d(n) be an effective procedure for enumerating D as {d₀, d₁, d₂, ...}. It follows that F is also effectively enumerable with enumeration {d₀, d₁, d₂, ...}.

Now define the diagonal function g(n)=d_n(n) + 1 (other functions can be constructed by replacing 1 by 2, 3, etc). This function is effectively computable, since both d_n=d(n) and d_n(n) are effectively computable. It is also total since d_n(n) halts for any n. However, by construction, g is different from every member of F. Therefore, g is total and effectively computable, but not computable by a machine that always halts. Alternatively, by the Church-Turing thesis, "effectively computable" can be replaced by "Turing machine computable", q.e.d.

Bibliography

• 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. (1996), 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.

Computational models | Theory of computation

Macchina che termina sempre | Машины, которые всегда останавливаются