in Theory of Computation
2,065 views
0 votes
0 votes
A is recursive if both A and its complement are accepted by turing machine

True or false
in Theory of Computation
2.1k views

2 Answers

2 votes
2 votes
It Should be TRUE, as Recursive languages are closed under complementation.

A is recursive means we have TM for that.

A' is also Recursive, hence This can also be accepted/decided by TM.

Hence Statement is TRUE.
1 vote
1 vote
True. For a recursive language, we have a TM which says for any string "w", "yes" if it belongs to the language and "no" if it does not. For the complement of a recursive language we just have to reverses 'yes' and 'no' conditions and this is possible with a slight modification to the original TM.

Related questions