6
$\begingroup$

According to Wikipedia

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.

My understanding of decider is that a machine is a decider if it always halts with output $0$ or $1$ (or whatever you prefer meaning "YES" and "NO"). However, I am confused by the definition that decider is a Turing machine that always halts since there are machines that do always halt with different than $0$ and $1$ outputs. For example, the Turing machine with the tape alphabet $\Sigma=\{a,b,c,d,e\}$ and simply printing as output the first symbol of the input has five different outputs.

Question: Do we need to restrict the output of deciders to only two different symbols or strings denoting "YES" and "NO"?

$\endgroup$

1 Answer 1

9
$\begingroup$

The term decider doesn't really have a standard meaning. In fact, it is lamentable that Sipser chose the terms decider and recognizer, since they seem to confuse students.

Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape.

A similar concept is a total Turing machine, which is a machine that halts on every input. A total Turing machine can be understood to compute a function (the answer is given on the output tape), or it can accept a language (using any of the semantics considered in the preceding paragraph).

It's really up to you whether a decider is allowed to output anything other than 0 or 1, and more generally, whether it can compute an arbitrary function, or whether it can only compute a Boolean function. The term is simply ambiguous. Sometimes you can tell the meaning from context, and in textbooks you will hopefully find a definition.

In contrast, total Turing machines means the same for everybody. But the ambiguity hasn't disappeared – it is now not completely clear what is the language accepted by a total Turing machine. If the Turing machine has ACCEPT/REJECT annotation for its halting states, then you can define the language this way. Or you can define it via the output. You can even say that a total Turing machine accepts a language only if its output is always 0 or 1. It's really up to you.

Whatever definitions you use, as long as they are reasonable, the same basic theorems of computability theory will hold. In a sense, the exact definitions do not matter, and this is why there is such a great variety of them. Wikipedia presents one possible definition, but your course or textbook could be using another definition which is formally inequivalent but in practice completely equivalent, like two versions of C++.

Assuming you are taking a course of self-learning from a textbook, I suggest not using Wikipedia for basic definitions. Instead, use the formal definitions that are in the textbook or that were given in class.

$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Commented Jun 16, 2022 at 6:52
  • 1
    $\begingroup$ Your second paragraph is the best answer that I have seen anywhere in the world. I use it as my standard defintion and always cite you. $\endgroup$
    – polcott
    Commented Oct 18, 2023 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.