Machines that always halt - Definition and Overview

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

In practice, a machine that always halts can be implemented as a programming language with restricted flow control instructions, so that no program (i.e. description) will ever cause the machine to enter an infinite loop. Note that this does not imply that the language is free of looping capabilities — all we require is that such loops be finite (Meyer and Ritchie, 1967; Brainerd and Landweber, 1974).

Machines that always halt are less powerful than Turing machines, as the following theorem shows:

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 <math>g,n \in N<math>, 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.

Despite the above theorem, it is possible to construct a machine that always halts and yet computes the majority of functions of interest (the so-called primitive recursive functions), an exception being the Ackermann function. An example of such a machine is provided by the programming language PL-{GOTO} of Brainerd and Landweber (1974).

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.