Smn-Theorem

Das $s_n^m$-Theorem ist ein zentrales Resultat der Berechenbarkeitstheorie. Es stellt ein Hilfsmittel in der Informatik dar, mit dem man den Code eines Programms in Abhängigkeit von Parametern berechnen kann, und wurde erstmals durch Stephen C. Kleene bewiesen (vgl. Rekursionssatz). Ein Resultat daraus ist, dass eine Programmiersprache, die zur Laufzeit generierten Code ausführen kann, Currying unterstützen kann.

Formale Definition

Sei $\{{\phi }_i{\}}_{i\in \mathbb{N}}$ eine effektive Nummerierung aller partiell berechenbaren Funktionen (bspw. die Gödel-Nummerierung aller deterministischen Turing-Maschinen).

Angenommen für einen festen Index $i$ sei die entsprechende Funktion vom Typ ${\phi }_i:{\mathbb{N}}^{m+n}\to \mathbb{N}$, dann gibt es eine totale und berechenbare Funktion $s_n^m:{\mathbb{N}}^{m+1}\to \mathbb{N}$ mit

${\phi }_{s_n^m(i,y_1,...,y_m)}(z_1,...,z_n)={\phi }_i(y_1,...,y_m,z_1,...,z_n)$ für alle $(y_1,...,y_m,z_1,...,z_n)\in {\mathbb{N}}^{m+n}$.

Nichtformale Erklärung

Die $s_n^m$Eigenschaft besagt, dass es zu einem Code $w$, der mit den Parametern $x$ und $v$ ausgeführt wird (bzw. ausgeführt werden kann), ein Transformationsprogramm $U$ gibt, das aus $w$, $x$ und $v$ ein Programm $w_x$ berechnet, welches bei der Eingabe von $v$ das Gleiche berechnet, wie $w$ bei der Eingabe von $x$ und $v$.

Beispiele

Das $s_n^m$-Theorem ist eine Möglichkeit aus Funktionen, deren Berechenbarkeit bereits bekannt ist, neue zu konstruieren.

Es sei beispielsweise zu zeigen, dass eine totale und berechenbare Funktion $g:{\mathbb{N}}^2\to \mathbb{N}$ existiert, so dass für $i,j,x\in \mathbb{N}$ gilt: ${\phi }_{g(i,j)}(x)={\phi }_i(x)+{\phi }_j(x)$.

Definiere dazu $\psi (i,j,x)={\phi }_i(x)+{\phi }_j(x)$. Die Funktion $\psi$ ist berechenbar, es existiert also ein Index $k\in \mathbb{N}$, so dass gilt: $\psi ={\phi }_k$. Aus dem $s_n^m$-Theorem folgt nun die Existenz einer total berechenbaren Funktion $s_1^2:{\mathbb{N}}^3\to \mathbb{N}$ mit ${\phi }_{s_1^2(k,i,j)}(x)={\phi }_k(i,j,x)=\psi (i,j,x)$ für alle $i,j,x\in \mathbb{N}$. Nun definieren wir $g(i,j):=s_1^2(k,i,j)$, $g$ ist dann offenbar ebenfalls total berechenbar und es gilt:

${\phi }_{g(i,j)}(x)={\phi }_{s_1^2(k,i,j)}(x)=\psi (i,j,x)={\phi }_i(x)+{\phi }_j(x)$

Insbesondere wird das $s_n^m$-Theorem oft verwendet, um Reduktionsfunktionen zu konstruieren:

Als Beispiel soll das allgemeine Halteproblem $H=\{(i,x)\in {\mathbb{N}}^2\mid {\phi }_i(x)\downarrow \}$ auf das Epsilon-Halteproblem $H_0=\{e\in \mathbb{N}\mid {\phi }_e(0)\downarrow \}$ reduziert werden. Genauer ist also die Existenz einer total berechenbaren Funktion $f:{\mathbb{N}}^2\to \mathbb{N}$ zu zeigen, so dass für alle $i,x\in \mathbb{N}$ gilt ${\phi }_i(x)\downarrow \iff {\phi }_{f(i,x)}(0)\downarrow$.

Analog zu oben definiert man $\psi (i,x,y)={\phi }_i(x)$, die Funktion $\psi$ ist offensichtlich berechenbar und ihr Wert hängt nicht von $y$ ab. Es sei also $k$ ein Index, so dass $\psi ={\phi }_k$. Das $s_n^m$-Theorem liefert jetzt die Existenz einer total berechenbaren Funktion $s_1^2$, so dass ${\phi }_{s_1^2(k,i,x)}(y)={\phi }_k(i,x,y)$. Setzt man $f(i,x)=s_1^2(k,i,x)$ und wählt $y=0$, ergibt sich

${\phi }_{f(i,x)}(0)={\phi }_k(i,x,0)=\psi (i,x,0)={\phi }_i(x).$