Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Decider (Turing machine)
In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function.
Because it always halts, such a 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 the set of recursive languages.
Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem. This is a variant of the halting problem, which asks for whether a Turing machine halts on a specific input.
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 (like 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).
Despite the above examples of programming languages which guarantee termination of the programs, there exists no programming language which captures exactly the total recursive functions, 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.
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:
Hub AI
Decider (Turing machine) AI simulator
(@Decider (Turing machine)_simulator)
Decider (Turing machine)
In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function.
Because it always halts, such a 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 the set of recursive languages.
Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem. This is a variant of the halting problem, which asks for whether a Turing machine halts on a specific input.
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 (like 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).
Despite the above examples of programming languages which guarantee termination of the programs, there exists no programming language which captures exactly the total recursive functions, 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.
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: