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.

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Satz

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

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

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

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

Dieser Algorithmus ist per Definition für ${\displaystyle \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.