recursively enumerable (original) (raw)

For a language L, TFAE:

• •
  There exists a Turing machine f such that ∀x.(x∈L)⇔the computation f⁢(x) terminates.
• •
• •
  There exists a total recursive function f:ℕ→L which is one-to-one and onto.

A language L fulfilling any (and therefore all) of the above conditions is called recursively enumerable.

Examples

2. 1. The set of encodings of Turing machines which halt when given no input.
4. 1. The set of integers n for which the hailstone sequence starting at n reaches 1. (We don’t know if this set is recursive, or even if it is N; but a trivial program shows it is recursively enumerable.)