Wiki and my classes Textbook defines a decider as:

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.

So shouldn't this decider be able to decide the Halting Problem? Because it halts always? I am a bit confused.


1 Answer 1


Here is an example of a decider:

On input $w$, accept if $|w|$ is even, and reject if $|w|$ is odd.

Does it solve the halting problem?

  • $\begingroup$ no, you want to imply that there is no decider for the halting problem? $\endgroup$ Jun 24, 2018 at 19:43
  • 1
    $\begingroup$ You claimed that a decider should be able to decide the halting problem. However, this decider doesn't decide the halting problem. In fact, Turing proved that no decider can decide the halting problem. $\endgroup$ Jun 24, 2018 at 19:57
  • $\begingroup$ ok then my understanding of a decider was wrong @Yuval Filmus very nice could I hire you? I have a lot of more questions :D $\endgroup$ Jun 24, 2018 at 20:01

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.