As I remember:

  • A decision problem is a problem that has the answer yes or no.
  • An algorithm (in the context of automata theory) answers yes or no; it halts on all inputs, accepted or not.
  • A TM represents an algorithm. The TM accepts an input string and executes with that input. If the machine ends up in an accept state, the answer is yes, otherwise no.

How does a yes/no problem relate to general algorithms we are doing that have more than yes/no problems? Or is that every problem can be thought as a yes/no problem, i.e. is this a function f produce 5 (or whatever input) with input 2 (or whatever output)?

  • 2
    $\begingroup$ You are lucky to be receiving these answers in finite time. Some people wait for ever. $\endgroup$ – babou Jun 20 '13 at 13:49
  • 1
    $\begingroup$ @babou: after reading your (sincere (and nice)) comment I'm tempted to delete both my comments and my (converted) answer :-))) $\endgroup$ – Vor Jun 20 '13 at 16:13
  • $\begingroup$ Well ... I would like it better it there was more (hopefully technical) humor on the site. Science is not supposed to be sad. But I see so little that I try to refrain. It is also true that humor can be perceived as rude, if one is not very careful. Also, I sometimes read the context more than the question. Fortunately we are all different. $\endgroup$ – babou Jun 21 '13 at 14:29

Don't forget that the final content of the tape can be treated like the output of the algorithm that the TM computes; in other words, a TM is able to compute a function: there is no "reject state" but only an "accept state" and the function result is the content of the tape at the end of the computation.

But if you want to learn more on the relation between decision problems and function problems , (quickly) read the Decision Problem - Equivalence with functions problems entry on Wikipedia, and then search some lectures online on the subject.

| cite | improve this answer | |

you can just convert you general algorithm into one comparing correct answer with the additional input

| cite | improve this answer | |

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.