We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is given here: Computational problem.

Edit: So, the comments suggest that I state more precisely what I mean. I'm not entirely sure how to do that, so I'll tell you where I'm coming from. I understand that a Turing machine can solve only decision problems (It can accept or reject a string). I am wondering if a Turing machine can solve all kinds of problems - which is why I ask, can all those types of problems be expressed as decision problems?

A better way to put it would probably be, can all those types of problems be expressed in a way that they might be solved by a Turing machine?

  • 2
    $\begingroup$ What do you mean by "convert"? How should the original and "converted" problem relate to each other? $\endgroup$ – Raphael May 29 '18 at 16:47
  • 1
    $\begingroup$ Please include your definition into post via edit. I think that a bit more strict definition of such mapping would be nice. $\endgroup$ – Evil May 29 '18 at 17:01
  • 1
    $\begingroup$ Related: Is there a generic procedure to produce hard enough decision problems? $\endgroup$ – Discrete lizard May 29 '18 at 17:24
  • 1
    $\begingroup$ "I understand that a Turing machine can solve only decision problems" That's simply not true. One can perfectly well define a TM to compute a function, where the output of the function is taken to be the contents of the non-blank portion of the tape at termination. Or a nondeterministic TM can be taken as defining a function $\Sigma^*\to\mathbb{N}$ defined as the number of accepting paths. And probably plenty of other similar definitions exist. $\endgroup$ – David Richerby Jun 1 '18 at 12:53
  • 1
    $\begingroup$ Why there is no answer or any idea for this question? I think it's a very important question to catch up with today's technology advancement. Can all problems be converted to equivalent decision problems? E.g., can artificial intelligence-related problems can be considered as decision problems? Or is there any faster way of thinking for nowadays problem, rather than thinking in yes/no (decision) problem? Does the subject of Theory of Automata needs revolution? $\endgroup$ – kate Feb 15 '19 at 12:15

Your Answer

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

Browse other questions tagged or ask your own question.