# What does it mean for a TM to solve a problem?

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

• Have you checked any standard resource on computability? – Raphael Jul 4 at 5:32
• Or even a dictionary? – 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