in Theory of Computation
702 views
1 vote
1 vote

Caption

Can someone give a clear explanation to this answer?

in Theory of Computation
702 views

2 Answers

1 vote
1 vote
Consider 3 turing machine  each for A,B,C

from above problem it can be interpreted that any string w from $\sum_{ }^{*}$  can be accepted by exactly either A or B or C.

so

run  these 3 turing mahine on string w parallely

as we are sure that exactly one of them will accept so whenever any one TM accept that w then can simply say the other will reject and halt them

ex- if w is accepted by TMa  then we can halt TMb and TMc

it can be done for all the three TM's  so  A,B,C   all the three are decidable

1 comment

Thank you :)
0
0
0 votes
0 votes

 he saying that A,B,C are TURING RECOGNIZABLE that means they are RECURSIVELY ENUMARABLE .

NOW , RECURSIVELY ENUMARABLE .  are closed under  both UNION, INTERSECTION,

so,option D is correct 

i think he might be mistaken 

Related questions

2 votes
2 votes
1 answer
1