HOME

TheInfoList



OR:

In
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has sinc ...
, a decider is a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
that halts for every input. A decider is also called a total Turing machineKozen, 1997 as it represents a
total function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
. Because it always halts, such a machine is able to decide whether a given string is a member of a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sym ...
. The class of languages which can be decided by such machines is the set of
recursive language In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the ...
s. Given an arbitrary Turing machine, determining whether it is a decider is an
undecidable problem In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
. This is a variant of the
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
, which asks for whether a Turing machine halts on a specific input.


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 In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional. Overview This differs from: * ...
. As a trivial example, a machine implementing a finitary
decision tree A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains con ...
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 BASIC (Beginners' All-purpose Symbolic Instruction Code) is a family of general-purpose, high-level programming languages designed for ease of use. The original version was created by John G. Kemeny and Thomas E. Kurtz at Dartmouth College ...
), we can express all of the
primitive recursive functions In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
(Meyer and Ritchie, 1967). An example of such a machine is provided by the toy programming language PL- 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 In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
, which is not primitive recursive, nevertheless is a total computable function computable by a
term rewriting In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or r ...
system with a
reduction ordering Reduction, reduced, or reduce may refer to: Science and technology Chemistry * Reduction (chemistry), part of a reduction-oxidation (redox) reaction in which atoms have their oxidation state changed. ** Organic redox reaction, a redox react ...
on its arguments (Ohlebusch, 2002, pp. 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 function In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as ...
s, 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 In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
. 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 In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 ...
, which on input 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. so that if ''g''(''nM'') = ''m'' then the return value of ''M'' is . Thus ''f''(''nM''), the true return value of ''M'' on input , will not equal ''g''(''nM''). 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 M_1,M_2,\ldots of machines, there would be a
recursively enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
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 could be constructed such that on input ''i'' the machine ''T'' returns T_i(i)+1\,. This machine cannot be equivalent to any machine 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 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 In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
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 In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
. Thus this problem is strictly more difficult than the
Halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
, 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 In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hi ...
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearl ...
. In a
sound In physics, sound is a vibration that propagates as an acoustic wave, through a transmission medium such as a gas, liquid or solid. In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by ...
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 In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory 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 Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the phil ...
. 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 In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for ''each'' input. This means to determine whether the input program computes a ''total'' function. It is c ...


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. (2006), ''
Introduction to the Theory of Computation ''Introduction to the Theory of Computation'' () is a textbook in theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the ...
'', PWS Publishing Co. * Kozen, D.C. (1997), ''Automata and Computability'', Springer. * Ohlebusch, E. (2002), ''Advanced Topics in Term Rewriting'', Springer. {{Formal languages and grammars Turing machine