**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**

## 0 comments:

## Post a Comment

Let us know your responses and feedback