World's most popular travel blog for travel bloggers.

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

, , No Comments
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 :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback