Answer

Correct Option: (iii) B only

Explanation

Evaluate each statement:

A. For every nondeterministic TM, an equivalent deterministic TM exists.

True. Turing Machines are deterministic simulatable: a DTM can simulate an NTM via BFS over computation tree with at most exponential slowdown. NTM does not increase power, unlike for PDA. $NTM = DTM$ in language power.

B. Turing-recognizable (RE) languages are closed under union and complementation.

False.

• RE is closed under union and intersection: if $M_1$ recognizes $L_1$ and $M_2$ recognizes $L_2$, a NTM can dovetail to recognize $L_1 \cup L_2$ and $L_1 \cap L_2$.
• RE is NOT closed under complement. If $L$ is RE but not recursive, $\overline{L}$ is not RE. Example $A_{TM}$ is RE, $\overline{A_{TM}}$ is not RE. So the conjunction “union and complementation” fails.

C. Turing-decidable (Recursive) languages are closed under intersection and complementation.

True. Recursive languages are decidable by a TM that always halts. Deciders can be complemented by swapping accept/reject, and intersected via product construction. They are closed under all Boolean operations: union, intersection, complement, difference.

D. Turing-recognizable languages are closed under union and intersection.

True. As noted in B, RE retains closure under union and intersection, only complement fails.

Summary

Statement	Truth
A	True
B	False
C	True
D	True

Only B is false.

Final Answer

B only is false → Option (iii).