Recursively Enumerable

Previous: Mathematics

A set S of natural numbers is recursively enumerable if there exists an algorithm that enumerates its elements: s₁, s₂, s₃, … (the algorithm may run forever for infinite sets).

Examples: x² generates {0, 1, 4, 9, 16, …}, the primes {2, 3, 5, 7, 11, …}

Every computable set is recursively enumerable, but not every recursively enumerable set is computable.

Recursive enumeration is the process of generating new elements from old ones by fixed rules.