Exercises — Decidability — decidable (recursive) and recognizable (recursively enumerable) languages

WHAT the definition asks: a language is decidable when some machine halts on every input and answers yes/no correctly. WHY this machine qualifies: we are told $M$ never loops — it always accepts or rejects. That is exactly the "halts on every input" promise. So $M$ is a decider, and $L(M)$ is decidable. Bonus: every decidable language is also recognizable (a decider already accepts all members), so "decidable" is the strongest true label here. Answer: decidable.

Members are always accepted in both cases; the only difference is the behaviour on non-members.

• Recognizer: on a non-member it may loop forever (or reject) — no promise.
• Decider: on a non-member it must halt and reject — a real "NO". This one asymmetry is the whole theory.

WHAT we build: a decider that simulates DFA $B$ on $w$. WHY it always halts: a DFA reads exactly one symbol per step and has no way to loop — it consumes the input and stops. Each of the $n=|w|$ symbols triggers exactly one DFA transition, so the DFA-level work is exactly $n$ transitions; then we check whether the final state is accepting. WHAT COUNTS AS A "STEP" (important): we are counting DFA transitions, not the raw moves of the Turing machine that hosts the simulation. A single-tape TM must, per DFA transition, also look up the current state and input symbol in the encoded transition table $⟨B⟩$, which costs a bounded (constant, or at worst polynomial in $|⟨B⟩|$) amount of tape shuffling. That overhead does not hide any loop — it is a fixed bounded chunk of work per symbol. So the total TM running time is $O(n\cdot |⟨B⟩|)$, still finite, and the decider always halts. WHAT IT LOOKS LIKE: a marker walking left-to-right across $w$, one cell per DFA transition, never backing up (see figure below). Accept iff $B$ lands in an accept state after those $n$ transitions. Because simulation always terminates, $A_{DFA}$ is decidable. Number of DFA transitions on length $n$: exactly $n$ (e.g. $n=7\Rightarrow 7$ transitions). Total TM time: $O(n\cdot |⟨B⟩|)$ — bounded, no hidden loop.

They are right. WHY: let decider $M$ decide $L$. Build $M^{\prime }$ that runs $M$ and swaps the answers — accept where $M$ rejects, reject where $M$ accepts. WHY the swap is legal: swapping only works if the machine reaches an answer to swap. $M$ always halts, so $M^{\prime }$ always halts too. Hence $M^{\prime }$ decides $\overline{L}$. Answer: yes — decidable languages are closed under complement.

WHAT $U$ does: it faithfully simulates $M$. If $M$ loops on $w$, then $U$ loops too — it never returns an answer. WHY this is not a violation: a recognizer is only required to accept members. Here $⟨M,w⟩\notin A_{TM}$ (since $M$ never accepts), so $U$ is allowed to loop on it. Answer: $U$ loops, and that is perfectly legal for a recognizer.

Consider an input $w\notin L$, so $w\in \overline{L}$. Then $M_1$ (a recognizer for $L$) is only obligated to accept members — on this non-member it may loop forever. If our decider ran $M_1$ "to completion" first, it would get stuck in that infinite loop and never reach $M_2$, which is the machine that would have accepted $w$. WHY alternating (dovetailing) fixes it: every $w$ is in exactly one of $L,\overline{L}$, so exactly one of $M_1,M_2$ is guaranteed to accept in finite time. By taking one step of each in turn, we are guaranteed to reach that finite acceptance without being trapped by the looping machine. Answer: sequential simulation can deadlock on a looping recognizer; dovetailing guarantees we always reach the machine that halts.

Proof by contradiction. Suppose $\overline{A_{TM}}$ were recognizable. Then both $A_{TM}$ (given recognizable) and $\overline{A_{TM}}$ (assumed) are recognizable. By the iff theorem, "$L$ and $\overline{L}$ both recognizable $\Rightarrow L$ decidable", we conclude $A_{TM}$ is decidable. But $A_{TM}$ is undecidable (see Halting Problem and Diagonalization). Contradiction. Therefore our assumption was false: $\overline{A_{TM}}$ is not recognizable.

• Recognizable? No — just proved in 3.2.
• Co-recognizable? Its complement is $A_{TM}$, which is recognizable. So yes, $\overline{A_{TM}}$ is co-recognizable.
• Decidable? Decidable would require both it and its complement recognizable; but it is not recognizable. So no. Answer: co-recognizable only (not recognizable, not decidable).

Let $M_L$ decide $L$ and $M_K$ decide $K$ (both always halt). Build decider $D$ on input $w$:

1. Run $M_L$ on $w$ — it halts (both halt on every input).
2. If $M_L$ rejects, then $w\notin L$, so $w\notin L\cap K$; $D$ rejects.
3. Else run $M_K$ on $w$ — it halts.
4. $D$ accepts iff $M_K$ accepts. WHY $D$ always halts: it runs two machines that each always halt, in sequence — no loop possible. Hence $L\cap K$ is decidable. (See Closure Properties.)

Let $R_L$ recognize $L$, $R_K$ recognize $K$. Build recognizer $R$ on $w$, covering every branch:

1. Run $R_L$ on $w$.
   • If $R_L$ accepts → go to step 2.
   • If $R_L$ rejects → $w\notin L$, so $w\notin L\cap K$; $R$ rejects (halts with NO). This is a legal recognizer action — rejecting a non-member is always allowed.
   • If $R_L$ loops → $R$ loops too; but then $w\notin L$, so $w\notin L\cap K$, and looping on a non-member is permitted. No obligation is broken.
2. Run $R_K$ on $w$.
   • If $R_K$ accepts → $w\in L$ (from step 1) and $w\in K$, so $w\in L\cap K$; $R$ accepts.
   • If $R_K$ rejects → $w\notin K$, so $w\notin L\cap K$; $R$ rejects.
   • If $R_K$ loops → $R$ loops; then $w\notin K$, a non-member of $L\cap K$, so looping is permitted. WHY sequential is fine here: we only need to accept members. For $w\in L\cap K$, both $R_L$ and $R_K$ accept in finite time, so the chain reaches "accept". For every non-member, whatever $R$ does (reject or loop) is exactly what a recognizer is allowed to do. Contrast with 3.1: there we needed a decider (a real NO on all non-members), so a loop was forbidden and we had to dovetail. Here a loop on non-members is acceptable, so plain sequential simulation is correct. Hence $L\cap K$ is recognizable.

Suppose enumerator $E$ prints every string of $L$ (in some order, repeats allowed) and never prints anything outside $L$. Build recognizer $R$ on input $w$: run $E$, and each time $E$ prints a string, compare it with $w$. If it ever equals $w$, accept. WHY this recognizes $L$: if $w\in L$, $E$ will eventually print $w$ (that is what "prints all of $L$" means), so $R$ accepts in finite time. If $w\notin L$, $E$ never prints $w$, so $R$ simply keeps waiting — it loops forever, which is exactly the permitted behaviour of a recognizer on a non-member. Hence $L$ is recognizable. (This is the "enumerable" in recursively enumerable.)

No, impossible. The iff theorem says: $L$ and $\overline{L}$ both recognizable $\Rightarrow$ $L$ is decidable. That directly contradicts "$L$ undecidable." Answer: no such $L$ exists. The two conditions "both-sides recognizable" and "undecidable" are mutually exclusive.

• Recognizable but not decidable: $A_{TM}=\{⟨M,w⟩:M\text{ accepts }w\}$. The Universal Turing Machine recognizes it (accept when $M$ accepts); Diagonalization proves no decider exists.
• Not recognizable: $\overline{A_{TM}}$. If it were recognizable, $A_{TM}$ would be decidable (iff theorem) — contradiction (Problem 3.2).

$HAL{T}_{TM}$ is recognizable (run $M$ on $w$; accept the moment it halts) and undecidable (a classic result via reduction from $A_{TM}$). Now suppose $\overline{HAL{T}_{TM}}$ were recognizable. Then both $HAL{T}_{TM}$ and its complement are recognizable, so by the iff theorem $HAL{T}_{TM}$ would be decidable — contradiction. Answer: $\overline{HAL{T}_{TM}}$ is NOT recognizable.

• ${\Sigma }^{\ast }$ (all strings): decidable — a machine that accepts everything and halts immediately.
• $A_{DFA}$: decidable (Problem 2.1).
• $A_{TM}$: recognizable but not decidable — sits in the recognizable ring outside the decidable core.
• $\overline{A_{TM}}$: not recognizable — sits outside the recognizable ring entirely (only co-recognizable). WHAT THE FIGURE SHOWS (in words): the map is three nested boundaries. The outer rectangle is "All languages". Inside it sits a blue circle labelled "Recognizable (RE)". Inside that, a smaller pink circle labelled "Decidable". The two decidable languages ${\Sigma }^{\ast }$ and $A_{DFA}$ are printed inside the innermost pink circle. $A_{TM}$ (in yellow) is printed in the blue ring — inside Recognizable but outside Decidable. And $\overline{A_{TM}}$ is printed in the outer rectangle only, outside the blue circle entirely — it is not recognizable, merely co-recognizable. Reading the picture from inside out is exactly reading the strict inclusions Decidable ⊊ Recognizable ⊊ All.