Decidable, semi-decidable, undecidable

Parent: logic

The vocabulary for "can an algorithm settle this?"

The three levels

A set / predicate S (say of natural numbers, or strings) is:

• decidable (recursive) — some algorithm halts on every input and answers "x ∈ S?" yes/no;
• semi-decidable (recursively enumerable, r.e.) — some algorithm halts and says yes exactly on members, and may run forever on non-members;
• undecidable — not decidable.

The bridge

S is decidable ⟺ both S and its complement are semi-decidable. (Run both semi-deciders in parallel; one must halt. Conversely a decider semi-decides both sides.)

So undecidability is a one-sidedness: the halting-problem is semi-decidable (wait and see it halt) but not co-semi-decidable (you can't confirm non-halting) — hence undecidable. Almost every "does program P have semantic property Q?" is undecidable by Rice's theorem, and new undecidable problems are minted by reduction from halting (generalized-collatz, FOL validity, Post correspondence…).

This is the property behind the r.e. tier, the reason you relax to get usable answers, and the exact ceiling on "does this agent/loop terminate?" (recursion-is-a-phase-transition).