[Solved]: Can a solvable problem be encoded in a recursively enumerable language?

Problem Detail: 

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?

Asked By : revisingcomplexity

Answered By : Dave Clarke

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33435

3.2K people like this

 Download Related Notes/Documents