سوال ۴۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳

A language is recursively enumerable (RE) — also called Turing-recognizable — by definition exactly when some Turing machine accepts it. So whatever a TM accepts is RE, which makes option 3 correct. Let us refute the others.

Option 1 — RE languages closed under complement? FALSE. A language $L$ is recursive (decidable) if and only if both $L$ and its complement $\overline{L}$ are RE. The halting language $A_{TM}=\{\langle M,w\rangle : M \text{ accepts } w\}$ is RE but undecidable, so its complement $\overline{A_{TM}}$ is not RE. Hence RE is not closed under complement.

Option 2 — number of TMs $=$ number of languages? FALSE. Every Turing machine has a finite description over a finite alphabet, so the set of (non-equivalent) Turing machines is countably infinite, $|\text{TMs}|=\aleph_0$. The set of all languages over a non-empty alphabet $\Sigma$ is the power set $2^{\Sigma^{*}}$, which is uncountable: $|\{\text{languages}\}| = 2^{\aleph_0} > \aleph_0.$ The two cardinalities differ — indeed this is exactly why non-RE languages must exist.

Option 3 — every TM-accepted language is RE? TRUE. This is the definition of recursively enumerable / Turing-recognizable.

Option 4 — a membership algorithm for every TM-accepted language? FALSE. Having an accepting TM only guarantees recognition: on a member the machine halts and accepts, but on a non-member it may loop forever, so it is a recognizer, not a decider. A membership algorithm (always halts with yes/no) exists only for recursive (decidable) languages. Since some RE languages (e.g. $A_{TM}$) are undecidable, no such algorithm exists for them.

The single correct statement is option 3.

Pitfall: "Accepted by a TM" means recognizable (RE), not decidable. A recognizer may run forever on rejects; only a decider (recursive language) gives a halting membership algorithm. Also remember: TMs are countable but languages are uncountable, so most languages are not even RE.