**Problem Detail:**

I am having problems knowing how to prove a language is recursive or not. Is there a particular general strategy is used for such a problem, or possibly some principle which is often used?

Thanks very much in advance.

###### Asked By : thesilverscientist

#### Answered By : D.W.

To prove a language is recursive (decidable), use the definition! Show that there exists a Turing machine that always halts and decides the language. Or, use closure properties.

To prove a language is not recursive (not decidable), use a reduction, or use closure properties, or use Rice's theorem. See our reference questions, How to show that a function is not computable? and What are common techniques for reducing problems to each other?.

###### Best Answer from StackOverflow

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

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback