Decider (Turing machine)

Turing machine that halts for any input / From Wikipedia, the free encyclopedia

In computability theory, a decider is a Turing machine that halts for every input.[1] A decider is also called a total Turing machine[2] 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.