When we say a TM solves a problem, what does this mean?

  • 3
    $\begingroup$ Have you checked any standard resource on computability? $\endgroup$ – Raphael Jul 4 at 5:32
  • $\begingroup$ Or even a dictionary? $\endgroup$ – David Richerby Jul 4 at 10:24

To simplify, let’s only speak about decision problems.

Decision problems have yes or no answers.

For example; Is X prime? Is a decision problem.

We can re-formulate the following question to be a set membership problem.

We define a language L to be the set of all prime numbers, ie the set of all strings that would make the decision problem return yes. To clarify, if X is a prime number, then the answer to the above would be yes.

We now change our question from “is X prime” to “is X in L”.

Since L is a language, we can associate a TM which decides L. This means a Turing machine which will accept on all strings in L and reject on all strings not in L.

This TM can now answer the problem of “is X prime” , if it accepts then X is prime, if it rejects then X is not prime.

We can say a TM solves a problem, if it decides the corresponding language L to that problem.

minor note: WLOG I did not mention the encoding of X for simplicity. This however does not change the overall message


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.