0
$\begingroup$

Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language?

A turing machine "decides" the language if it "accepts" the language and enters a rejecting state for any input not in the language.

Don't really know what the difference is

$\endgroup$
1
  • $\begingroup$ There is no real difference. $\endgroup$
    – nir shahar
    Apr 26, 2021 at 18:24

1 Answer 1

1
$\begingroup$

Depending on the problem, there might not be any difference.

If the problem's goal is to answer a yes/no question, then there is no difference; accepting the input is equivalent to answering yes, and rejecting is equivalent to answering no.

However, if the goal of your problem is to output something else (e.g., output a number), then it is not identical to deciding a language. There are still ways to formulate a corresponding language, but the correspondence is not quite as direct.

To learn more, see https://en.wikipedia.org/wiki/Decision_problem, https://en.wikipedia.org/wiki/Function_problem, https://en.wikipedia.org/wiki/Optimization_problem, https://en.wikipedia.org/wiki/Formal_language.

$\endgroup$

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.