Machine that always halts

From Wiki @ Karl Jones dot com
Revision as of 06:50, 20 September 2016 by Karl Jones (Talk | contribs) (Created page with "In computability theory, a '''machine that always halts''' — also called a '''decider''' (Sipser, 1996) or a '''total Turing machine''' (Kozen, 1997) — is a Turing m...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

External links