World's most popular travel blog for travel bloggers.

Given an arbitrary language, how does one go about proving that it is recursive or otherwise?

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

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback