Question bank — Decidability — decidable (recursive) and recognizable (recursively enumerable) languages

True — a decider already says YES on members, which is all a recognizer must do; halting on non-members is a bonus, strictly stronger than "may loop."

False — recognition only promises a YES on members; on non-members it may loop forever, so you never obtain the NO that deciding requires. $A_{TM}$ is the standard counterexample.

True — run the decider and swap accept/reject; because a decider always halts, you always reach the point where you can swap, so the new machine decides $\overline{L}$.

False — the swap trick needs the machine to halt to know what to swap to, but a recognizer can loop on non-members. $A_{TM}$ is recognizable while $\overline{A_{TM}}$ is not.

True — run both recognizers in parallel (dovetailing); every string is in exactly one of $L,\overline{L}$, so one recognizer must accept in finite time, giving you a definite YES/NO. See Reductions and Rice's Theorem context via Halting Problem.

False — $A_{TM}$ is undecidable yet recognizable; "undecidable" only means no total (always-halting) machine exists, not that no recognizer exists.

False — if it were, both $A_{TM}$ and $\overline{A_{TM}}$ would be recognizable, forcing $A_{TM}$ to be decidable, which it is not. So $\overline{A_{TM}}$ lies outside RE entirely.

True — build a machine with a hard-coded list; it compares the input against the finitely many members, always halts, and answers YES/NO. Finiteness removes any risk of looping.

True — take $A_{TM}$ (undecidable but recognizable) and $\overline{A_{TM}}$ (undecidable and not even recognizable); both are undecidable simultaneously.

True — a machine that always halts is exactly a decider for the language it accepts, since every non-member gets a definite reject.

False — $\varnothing$ is decidable: a machine that rejects every input (and halts) decides it. Being tiny doesn't make it hard.

True — a language is recognizable iff some TM can print all its strings (with repeats allowed, any order); to test $w$ you run the enumerator and accept when $w$ appears. See Chomsky Hierarchy.

Error: recognition is one-sided. It guarantees a YES for members but gives no verdict on non-members (possible infinite loop). Two-sided classification is deciding, a strictly stronger property.

Error: the swap only works if the machine halts. The $A_{TM}$-recognizer loops when $M$ loops on $w$, so there is nothing to swap to — the trick silently requires a decider you don't have.

Error: $M_1$ may loop forever on inputs it doesn't accept, blocking you from ever reaching $M_2$. You must dovetail — alternate one step of each — so a halting machine is always reached (see Universal Turing Machine).

Error: a DFA reads one symbol per step and cannot loop; simulation always finishes in $|w|$ steps. So $A_{DFA}$ is fully decidable, unlike the TM-simulation problem $A_{TM}$.

Error: the universal TM does accept every member of $A_{TM}$ (it's recognizable). Undecidability comes from the impossibility of a total machine — proven by Diagonalization, not from any failure to recognize members.

Error: decidable languages are closed under complement (swap-and-halt works), so $\overline{L}$ is decidable whenever $L$ is. Undecidable complements only arise from undecidable originals.

Because an infinite run yields no information — you can never distinguish "still computing" from "never stops." That one asymmetry means a recognizer's silence isn't a NO, whereas a decider's halt makes NO real.

Because either machine might loop on inputs it doesn't accept; sequential order risks getting stuck on a non-halter forever. Parallel (dovetailed) execution guarantees the one machine destined to accept is reached in finite time.

The complement construction needs the machine to halt so you know when to flip the answer. Deciders always halt (flip works); recognizers may loop on non-members (nothing to flip), so the closure breaks.

$A_{TM}$ is at least recognizable (you can confirm acceptances), but $\overline{A_{TM}}$ would require confirming non-acceptance, i.e. certifying an infinite loop in finite time — impossible, so it isn't even in RE.

Because such a language is exactly one an enumerator can list string by string; members eventually appear (giving a YES), while non-members simply never appear — which is precisely the "loop on non-members" behaviour.

If you can show both $L$ and $\overline{L}$ are recognizable, the parallel-run argument turns two half-solutions into a full decider. Showing one is not recognizable then proves the other cannot be decidable. See Closure Properties.

Yes — a machine that accepts everything and halts decides it. It's the trivial "always yes" case, the complement of $\varnothing$.

Yes — the always-reject-and-halt machine recognizes (in fact decides) $\varnothing$. Vacuously, it accepts exactly the members of $\varnothing$ (there are none).

Nothing special — $\epsilon$ is an ordinary string in ${\Sigma }^{\ast }$, so a decider must still halt with YES/NO on it, and a recognizer must accept it iff $\epsilon \in L$. Edge length changes no rule.

No — if $\overline{L}$ is decidable then $\overline{L}$ is recognizable, so both $L$ and $\overline{L}$ are recognizable, forcing $L$ to be decidable. This contradicts "undecidable."

Only that $L$ is recognizable. Without a guarantee that the machine halts on non-members, you cannot upgrade the claim to decidable — the accept-behaviour alone gives recognition.

Yes — decidability is about the machine always halting, independent of whether $L$ is finite or infinite. An infinite decidable language just means infinitely many inputs get YES, each after a finite halting run.

Yes — a language $L$ with $L\notin \text{RE}$ and $\overline{L}\notin \text{RE}$ exists (such languages are "doubly hard"); $\overline{A_{TM}}$ is not in RE, and richer diagonal constructions land fully outside both classes.