Machine that always halts

Machine that always halts

In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every 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. However, due to the Halting Problem, determining whether an arbitrary Turing machine halts on an arbitrary input is itself an undecidable decision problem.

Contents

Functions computable by total Turing machines

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 flow control capabilities so that no input will ever cause the machine to enter an infinite loop. As a trivial example, a machine implementing a finitary 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 (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 is a total computable function computable by a term rewriting system with a reduction ordering on its arguments (Ohlebusch, 2002, pp.67).

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:

  1. Can every partial function computable by a partial Turing machine be extended (that is, have its domain enlarged) to become a total computable function?
  2. 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.

Theorem. 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 0 with output m has no extension to a total computable function.

The proof proceeds by contradiction. 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 0 simulates the machine with index e running on an index nM 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. Define M so that if g(nM) = m then the return value of M is m + 1. Thus f(nM), the true return value of M on input 0, will not equal g(nM). This contradicts the assumption that g extends 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 M_1,M_2,\ldots of machines, there would be a recursively enumerable sequence T_1,\ldots T_2,\ldots of Turing machines that compute total functions and so that every total computable function is computable by one of the machines Ti. This is impossible, because a machine T could be constructed such that on input i the machine T returns T_i(i)+1\,. This machine cannot be equivalent to any machine T on the list: suppose it were on the list at index j. Then T_j(j)=T_j(j)+1\,, which does not return an integer result. Therefore it can't be total, but the function by construction must be total (if total functions are recursively enumerable, then this function can be constructed), so we have a contradiction. This shows that the second question has a negative answer.

The set of indices of total Turing machines

The 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 \Pi^0_2 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.

See also

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Counter machine — A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded… …   Wikipedia

  • Primitive recursive function — The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the recursive functions (recursive functions are also known as computable functions). The term was coined by… …   Wikipedia

  • Counter machine reference model — The Counter machine s reference model is a set of choices and conventions to be used with the Counter machine and other model variants of the Register machine concept. It permits comparisons between models, and serves a didactic function with… …   Wikipedia

  • Stack machine — In computer science, a stack machine is a model of computation in which the computer s memory takes the form of one or more stacks. The term also refers to an actual computer implementing or simulating the idealized stack machine.In addition, a… …   Wikipedia

  • Turing machine examples — The following are examples to supplement the article Turing machine.Turing s very first exampleThe following table is Turing s very first example (Turing 1936):: 1. A machine can be constructed to compute the sequence 0 1 0 1 0 1... ( Undecidable …   Wikipedia

  • The Decider — may refer to: Bill Maher: The Decider, a stand up comedy special Machine that always halts, a type of Turing machine A political catch phrase said by former United States President George W. Bush The Decider, a recurring segment on The Daily Show …   Wikipedia

  • Recursive language — This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science). In mathematics,… …   Wikipedia

  • Halting problem — In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever. This is equivalent to the problem of deciding, given a… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”