Semi-decidable (recursively enumerable)

Parent: logic

The "confirm-yes, but maybe loop on no" level — the most important shape of computability, and the one the halting-problem lives at.

Semi-decidable / r.e.

A set S is semi-decidable (recursively enumerable) if some program halts-and-accepts exactly on the members of S, and on non-members may run forever. Four equivalent views:

• the domain of a partial computable function (where it halts);
• the range of a computable function ("enumerable": a machine that lists exactly S);
• definable as ∃y. R(x,y) with R decidable (one unbounded search over a checkable witness) — the Σ₁ class.

The asymmetry that matters

You can verify membership — search for the witness / run until it accepts — but you can never confirm non-membership (the search might just not have finished). That one-sidedness is undecidability: a set is decidable iff both it and its complement are r.e.

• r.e. but not co-r.e.: the halting set (confirm halting by waiting; can't confirm non-halting).
• Other r.e. non-decidable sets: FOL validity/provability (enumerate proofs), solvable Diophantine equations (MRDP/Hilbert's 10th), word problems.

Why it's the practical level

The whole engineering trick is that verifying a witness is easy even when finding/deciding is not — which is exactly certificates (a proof you can check), the ∃-witness of Σ₁, and why the harness's gates check consistency rather than decide truth. It's also the Type-0 r.e. tier of the Chomsky hierarchy.