Is it correct that the membership problem (i.e. the characteristic function) of a recursive language is a decidable i.e. computable problem?
What kind of problem is the membership problem of a recursive enumerable language, as opposed to the membership problem of a non r.e. language? Is the membership problem of a recursive enumerable language also decidable?
Thanks.
By membership problem, you mean if a word is an element of the recursive language? Then yes, by definition: A language is recursive, if there is a turing machine (TM) that halts and accepts words which are elements of the language. The difference between recursive and recursive enumerable language is that a TM for a recursive language always halts but a TM for recursive enumerable language is not guaranteed to hold for words not in the language (it might loop forever). We call the latter therefor semidecidable