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.
Der Satz versteht sich als Rekursion, darum ist er in zwei Teilen gegeben:
Eine Menge A ⊂ ℕ ist rekursiv aufzählbare Menge, wenn sie Wertebereich einer berechenbaren Funktion ist.
Eine Menge A ⊂ ℕk ist rekursiv aufzählbare Menge, genau dann wenn A= { x∈ℕk|∃t : (x,t)∈B } für ein B⊂ℕk+1, das rekursiv ist.
