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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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?

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

Your Answer

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

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