Skip to main content
deleted 171 characters in body
Source Link

I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. Intuitively you would have to check all possible words over the boolean alphabet and this fact alone should give you the feeling that the empty language is not recursive. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).

I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. Intuitively you would have to check all possible words over the boolean alphabet and this fact alone should give you the feeling that the empty language is not recursive. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).

I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).

Source Link

I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. Intuitively you would have to check all possible words over the boolean alphabet and this fact alone should give you the feeling that the empty language is not recursive. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).