Projection set (computer science)

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

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.