Class of sets (languages) for which there exists a Turing machine that enumerates all members or, equivalently, accepts exactly the inputs in the set by halting and accepting on them; the machine may not halt on non-members.

Principle

Recursively enumerable (r.e.) means semi-decidable: there is an effective procedure that, for each member, eventually halts and signals membership, while non-members need not lead to halting; enumeration and recognition are equivalent characterizations in this class.

Demonstration

The set of theorems provable by a computably axiomatized formal system is recursively enumerable: a Turing machine can systematically enumerate all proofs and thus list all provable sentences.

Misapplication

Assuming an r.e. set is decidable because its members can be listed; treating non-halting on a non-member as a proof of non-membership rather than absence of evidence.

Consequence

Membership in an r.e. set can be confirmed by running the enumerator/recognizer until acceptance; however, absence of acceptance after long runs provides no definitive negative answer without extra information.

Reversal

Co-Recursively Enumerable: sets whose complements are r.e.; Decidable: sets that are both r.e. and co-r.e.

Boundary

Defined relative to a standard encoding and model (Turing machines); excludes oracle-enhanced machines unless specified; closure properties include union and intersection with decidable sets but not complement in general.

Semantic Tension

Tension exists between r.e. and decidable: both listability and recognizability capture positive information, while decidability requires symmetric positive and negative procedures.

Synthesis

Recursively enumerable captures the notion of positive algorithmic recognizability: members can be effectively produced or recognized, but their complements may remain beyond algorithmic confirmation without further structure.