1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ no, you want to imply that there is no decider for the halting problem? $\endgroup$ – simplesystems Jun 24 '18 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$ – Yuval Filmus Jun 24 '18 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$ – simplesystems Jun 24 '18 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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