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

We label the classes: a language is decidable (recursive) if some TM halts on every input and decides membership; it is Turing-recognizable (recursively enumerable, r.e.) if some TM accepts exactly its members. We have the strict inclusion $\text{decidable} \subsetneq \text{recognizable}$.

Statement 1 — TRUE. "Turing-unrecognizable" means not recognizable (not r.e.). Since every decidable language is recognizable, the contrapositive gives: $\lnot\,\text{recognizable} \;\Longrightarrow\; \lnot\,\text{decidable}.$ So any language that is not recognizable is certainly not decidable, i.e. undecidable. Correct.

Statement 2 — FALSE. The set of all languages over a non-empty alphabet $\Sigma$ is the power set $2^{\Sigma^{*}}$ of the countably infinite set $\Sigma^{*}$, so it has the cardinality of the continuum $2^{\aleph_0}$ — it is uncountable. The regular languages are only countably infinite (each is described by a finite regular expression / DFA). Removing a countable set from an uncountable set still leaves an uncountable set: $|\{\text{non-regular languages}\}| = 2^{\aleph_0} \;(\text{uncountable}).$ The statement claims "countably infinite," which is wrong.

Statement 3 — TRUE. Every Turing machine has a finite description, so it can be encoded as a finite string over a finite alphabet. The set of all finite strings is countably infinite, and there are infinitely many distinct TMs, so the set of all Turing machines is countably infinite. Correct.

Statement 4 — TRUE. Classic theorem: every infinite r.e. language has an infinite decidable subset. Let an enumerator output the members $w_1, w_2, w_3, \ldots$ (in some order). Build a subset $S$ greedily: keep $w_i$ only if it is longer than every string already kept (break ties by lexicographic order). Then the kept strings appear in strictly increasing length, so $S$ is infinite (the source language is infinite, so arbitrarily long strings keep arriving). To decide $w \in S$, run the enumeration until a kept string of length $> |w|$ appears; by construction no later element can equal $w$, so the test halts. Hence $S$ is an infinite decidable subset. Correct.

Count: statements 1, 3, 4 are true and statement 2 is false, so exactly 3 statements are correct.

Matching the options ($1{:}\,4,\ 2{:}\,3,\ 3{:}\,2,\ 4{:}\,1$), the answer is option 2.

Pitfall: The only false claim hinges on "countably infinite" vs "uncountable." The set of all languages — and hence of all non-recognizable, non-regular, or non-decidable languages — is uncountable, while the regular languages, decidable languages, r.e. languages, and Turing machines are each only countably infinite.