Projektionssatz (Informatik)

Der Projektionssatz ist ein hinreichendes Kriterium für eine Sprache, rekursiv aufzählbar zu sein. Eine Sprache ist rekursiv aufzählbar, wenn sie Definitionsbereich einer berechenbaren Funktion ist.

Satz

Der Satz versteht sich als Rekursion, darum ist er in zwei Teilen gegeben:

• Eine Menge $A\subset \mathbb{N}$ ist eine rekursiv aufzählbare Menge, wenn sie Wertebereich einer berechenbaren Funktion ist.
• Eine Menge $A\subset {\mathbb{N}}^k$ ist eine rekursiv aufzählbare Menge, genau dann wenn$A=\{\mathrm{\forall }x\in \mathbb{N}\mathrm{\exists }y\in \mathbb{N}:⟨x,y⟩\in B\}$für ein $B\subset {\mathbb{N}}^{k+1}$, das rekursiv (entscheidbar) ist.

Letztere Folgerung ist eine direkte Implikation aus der Definition der aufzählbaren Menge, welche besagt, dass auf einer aufzählbaren Menge ein Algorithmus $f(n)$ definiert werden kann, welcher folgende Werte ausgibt:

$f(n)=\{\begin{array}{cc}1& n\in B\\ 0& \text{sonst}\end{array}.$

Dieser Algorithmus ist per Definition für $\mathrm{\forall }n\in B$ definiert und stellt daher eine berechenbare Funktion dar, welche als charakteristische Funktion einer Menge angesehen werden kann, die in der Folge entscheidbar bzw. rekursiv ist.