Projection set (computer science)
The projection sentence is a sufficient criterion for a language to be recursively enumerable . A language can be enumerated recursively if it is the domain of a computable function.
The sentence is a recursion, which is why it is given in two parts:
- A set A ⊂ ℕ can be enumerated recursively if it is the domain of a computable function.
- A set A ⊂ ℕ k is recursively enumerable if and only if A = {x∈ℕ k | ∃t: (x, t) ∈B} for some B⊂ℕ k + 1 that is recursive.