# Can a solvable problem be encoded in a recursively enumerable language?

Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new language that is recursive enumerable.

If yes, this would mean that every solvable problem can encoded in recursive language; if not, a problem can be encoded in a recursive and/or recursive enumerable L and the problem could become semi-decidable for a different language.

Any clarification on this?

• I'm not sure you understand the meaning of (decision) problem and language in this context. They have the same meaning. A decision problem or language is a subset of $\Sigma^*$. That's the definition. – Yuval Filmus Nov 23 '14 at 15:55
• Well, if I have a connected graph decision problem, then I will have to translate the decision problem with an encoding scheme into a language. This question is concerned whether I may encode a solvable problem in a recursevely enumerable language – revisingcomplexity Nov 23 '14 at 16:01