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?

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 23 '14 at 15:55
  • $\begingroup$ 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 $\endgroup$ – revisingcomplexity Nov 23 '14 at 16:01

Almost immediately from definitions, one has:

  • A solvable (decidable) problem can be encoded as (not in) a recursive language.

  • A semi-decidable problem can be encoded as (not in) a recursively enumerable language.


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.