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.

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

Eine Menge A ⊂ ℕ ist rekursiv aufzählbar, wenn sie Wertebereich einer berechenbaren Funktion ist.
Eine Menge A ⊂ ℕ^k ist rekursiv aufzählbar, genau dann wenn A= { x∈ℕ^k|∃t : (x,t)∈B } für ein B⊂ℕ^k+1, das rekursiv ist.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.