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

True or false

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 votes
1 votes
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

2 votes
2 votes
1 answer
1
Ajit J asked Dec 25, 2018
2,040 views
What is the complement of a language which is recursively enumerable but not recursive? Is it only non rel or can be both both non rel and recursive?