Difference between revisions of "Machine that always halts"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) (→See also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 14: | Line 14: | ||
* [[Computability theory]] | * [[Computability theory]] | ||
* [[Decision problem]] | * [[Decision problem]] | ||
| + | * [[Halting problem]] | ||
* [[Recursive language]] | * [[Recursive language]] | ||
* [[Total functional programming]] | * [[Total functional programming]] | ||
* [[Turing machine]] | * [[Turing machine]] | ||
| + | * [[Undecidable problem]] | ||
== External links == | == External links == | ||
Latest revision as of 06:51, 20 September 2016
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.
Description
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 every input is itself an undecidable decision problem.
See also
- BlooP and FlooP
- Computability theory
- Decision problem
- Halting problem
- Recursive language
- Total functional programming
- Turing machine
- Undecidable problem
External links
- Machine that always halts @ Wikipedia
