imported>A.Abdel-Rahim: QS-Baustein modif.

2024-09-10T00:53:54Z

QS-Baustein modif.

Neue Seite

{{QS-Informatik|Knacknüsse=ja}}
{{Belege}}

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 [[Berechenbarkeit|berechenbaren]] Funktion ist.

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

* Eine Menge <math>A \subset \mathbb N</math> ist eine [[rekursiv aufzählbare Menge]], wenn sie Wertebereich einer berechenbaren Funktion ist.
* Eine Menge <math>A \subset \mathbb N^k</math> ist eine rekursiv aufzählbare Menge, genau dann wenn<math>A=\{\forall x\in \mathbb N \, \exists y\in \mathbb N: \langle x,y \rangle \in B\}</math>für ein <math>B \subset \mathbb N^{k+1}</math>, das rekursiv ([[Entscheidbarkeit|entscheidbar]]) ist.<ref>{{Internetquelle |url=https://www.cs.uni-potsdam.de/ti/lehre/downloads/TI-II/slides-5.4.pdf |titel=Elementare Berechenbarkeitstheorie I: Grundkonzepte und ihre Eigenschaften |werk=Universität Potsdam |sprache=de |abruf=2024-08-26}}</ref>
Letztere Folgerung ist eine direkte Implikation aus der Definition der aufzählbaren Menge, welche besagt, dass auf einer aufzählbaren Menge ein [[Algorithmus]] <math>f(n)</math> definiert werden kann, welcher folgende Werte ausgibt:

<math>f(n)=
\begin{cases}
1 & n \in B \\
0 & \text{sonst} \\
\end{cases}.
</math>

Dieser Algorithmus ist per Definition für <math>\forall n\in B</math> 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.

== Einzelnachweise ==
<references />

[[Kategorie:Theorie formaler Sprachen]]

Projektionssatz (Informatik) - Versionsgeschichte

imported>A.Abdel-Rahim: QS-Baustein modif.