recategorized by
3,494 views
14 votes
14 votes
State whether the following statement are TRUE or FALSE.

$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
recategorized by

4 Answers

Best answer
27 votes
27 votes
Yes if $A$ and its complement are accepted by Turing machines.then $A$ is recursive.

Suppose a language $A$ is recursively enumerable. That means there exists a Turing machine $T1$ that, given any string of the language, halts and accepts that string.

Now let's also suppose that the complement of $A$, $A'= \{w: w \mid A\}$, is recursively enumerable. That means there is some other Turing machine $T2$ that, given any string of $A'$ halts and accepts that string. So  any string belongs to either $A$ or $A'$. Hence, any string will cause either $T1$ or $T2$ (or both) to halt. We construct a new Turing machine that emulates both $T1$ and $T2$, alternating moves between them. When either one stops, we can tell (by whether it accepted or rejected the string) to which language the string belongs.

Thus, we have constructed a Turing machine that, for each input, halts with an answer whether or not the string belongs to $A'$. Therefore $A$ and $A'$ are recursive languages.
edited by
7 votes
7 votes

TRUE,

if A is decidable , then A and A' are accepted by Turing machine . it's proove is given as follows-

when the input srting W is given to the Turing machine TM then ---

  • if W belongs to A  then TM1 halts
  • if W does not belongs to A' then TM2 halts

it is clear that from both the Turing machines TM1 and TM2 , that at least one of Turing machine will be halts , then TM will be halt .

And when TM will be halt then language A and A' are accepted by the Turing machine.

2 votes
2 votes

Lets use logic and try to generate case T - > F.

A is recursive if both A and its complement are accepted by Turing machines. (q if p == p -> q)

 (A and its complement are accepted by Turing machines) -> A is recursive

Given LHS is true can RHS be false? A and its compliment is accepted by TM 

Case 1: If A is REL then complement of REL is not closed. i.e there does not exists TM for such languages which accept it making our LHS false. But it is already given to be true.

Case 2: If A is recursive then its complement is recursive and hence REL which is accepted by TM making our implication True

Hence A recursive is true.

1 votes
1 votes

$\text{Case 1}:$  is RE language then

 

But it is not possible because we can complement for Yes to No and No to Yes. But what to do for loop So case 1 is not possible

$\text{Case 2}\space: $IF we assume Total Turing Machine A Turing  machine in which only accept or reject, looping is not there

So statement is true

edited by
Answer:

Related questions

14 votes
14 votes
2 answers
1
makhdoom ghaya asked Nov 9, 2016
3,882 views
State whether the following statements are TRUE or FALSE:The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
21 votes
21 votes
4 answers
2
makhdoom ghaya asked Nov 9, 2016
3,286 views
State whether the following statements are TRUE or FALSE:The intersection of two CFL's is also a CFL.
13 votes
13 votes
2 answers
3
makhdoom ghaya asked Nov 9, 2016
2,465 views
State whether the following statements are TRUE or FALSE:All subsets of regular sets are regular.
17 votes
17 votes
5 answers
4
makhdoom ghaya asked Nov 9, 2016
3,617 views
State whether the following statements are TRUE or FALSE:Regularity is preserved under the operation of string reversal.