Machine that always halts

From Freepedia

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).

The set of problems which can be solved by such machines are exactly the decision problems.

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.

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	(unrestricted)	Recursively enumerable	Turing machine
	(unrestricted)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
Type-2	Context-free	Context-free	Pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper superset of the category directly beneath it.