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
