imported>Georg Hügler am 15. November 2019 um 23:10 Uhr

2019-11-15T23:10:23Z

Neue Seite

Das '''<math>s_{n}^m</math>-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 Kleene|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 <math>\{\varphi_i \}_{i \in \N}</math> eine [[Nummerierung (Informatik)|effektive Nummerierung]] aller [[Partielle Funktion|partiell]] [[Berechenbare Funktion|berechenbaren Funktionen]] (bspw. die [[Gödel-Nummerierung]] aller [[Determinismus (Algorithmus)|deterministischen]] [[Turingmaschine|Turing-Maschinen]]).

Angenommen für einen festen Index <math>i</math> sei die entsprechende Funktion vom Typ <math>\varphi_i \colon \N^{m+n} \to \N</math>, dann gibt es eine [[Totale Funktion|totale]] und [[berechenbare Funktion| berechenbare]] Funktion <math>s_{n}^m\colon \mathbb{N}^{m+1} \to \mathbb{N}</math> mit
:<math>\varphi_{s_{n}^m(i, y_1,..., y_m)}(z_1,..., z_n) = \varphi_{i}(y_1,..., y_m, z_1,..., z_n)</math> für alle <math>(y_1,..., y_m, z_1,...,z_n) \in \mathbb{N}^{m+n}</math>.

== Nichtformale Erklärung ==
Die <math>s^m_n</math>Eigenschaft besagt, dass es zu einem Code <math>w</math>, der mit den Parametern <math>x</math> und <math>v</math> ausgeführt wird (bzw. ausgeführt werden kann), ein Transformationsprogramm <math>U</math> gibt, das aus <math>w</math>, <math>x</math> und <math>v</math> ein Programm <math>w_x</math> berechnet, welches bei der Eingabe von <math>v</math> das Gleiche berechnet, wie <math>w</math> bei der Eingabe von <math>x</math> und <math>v</math>.

== Beispiele ==
Das <math>s^m_n</math>-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 <math>g\colon \mathbb{N}^2 \to \mathbb{N}</math> existiert, so dass für <math>i, j, x \in \mathbb{N}</math> gilt: <math>\varphi_{g(i, j)}(x) = \varphi_{i}(x) + \varphi_{j}(x)</math>.

Definiere dazu <math>\psi(i, j, x) = \varphi_{i}(x) + \varphi_{j}(x)</math>.
Die Funktion <math>\psi</math> ist berechenbar, es existiert also ein Index <math>k \in \mathbb{N}</math>, so dass gilt: <math>\psi = \varphi_{k}</math>.
Aus dem <math>s_{n}^m</math>-Theorem folgt nun die Existenz einer total berechenbaren Funktion <math>s_{1}^2\colon \mathbb{N}^3 \to \mathbb{N}</math> mit <math>\varphi_{s_{1}^2(k, i, j)}(x) = \varphi_{k}(i, j, x) = \psi(i, j, x)</math> für alle <math>i, j, x \in \mathbb{N}</math>.
Nun definieren wir <math>g(i, j) := s_{1}^2(k, i, j)</math>, <math>g</math> ist dann offenbar ebenfalls total berechenbar und es gilt:
:<math>\varphi_{g(i, j)}(x) = \varphi_{s_{1}^2(k, i, j)}(x) = \psi(i, j, x) = \varphi_{i}(x) + \varphi_{j}(x)</math>

Insbesondere wird das <math>s_n^m</math>-Theorem oft verwendet, um [[Reduktion (Theoretische Informatik)|Reduktionsfunktionen]] zu konstruieren:

Als Beispiel soll das [[Halteproblem|allgemeine Halteproblem]] <math>H = \{(i,x) \in \N^2 \mid \varphi_i(x){\downarrow}\}</math> auf das Epsilon-Halteproblem <math>H_0 = \{e \in \N \mid \varphi_e(0){\downarrow}\}</math> reduziert werden. Genauer ist also die Existenz einer total berechenbaren Funktion <math>f \colon \N^2 \to \N</math> zu zeigen, so dass für alle <math>i,x \in \N</math> gilt <math>\varphi_i(x){\downarrow} \Leftrightarrow \varphi_{f(i,x)}(0){\downarrow}</math>.

Analog zu oben definiert man <math>\psi(i,x,y) = \varphi_i(x)</math>, die Funktion <math>\psi</math> ist offensichtlich berechenbar und ihr Wert hängt nicht von <math>y</math> ab.
Es sei also <math>k</math> ein Index, so dass <math>\psi = \varphi_k</math>. Das <math>s^m_n</math>-Theorem liefert jetzt die Existenz einer total berechenbaren Funktion <math>s^2_1</math>, so dass <math>\varphi_{s^2_1(k,i,x)}(y) = \varphi_k(i,x,y)</math>. Setzt man <math>f(i,x) = s^2_1(k,i,x)</math> und wählt <math>y = 0</math>, ergibt sich
:<math>\varphi_{f(i,x)}(0) = \varphi_k(i,x,0) = \psi(i,x,0) = \varphi_i(x).</math>

[[Kategorie:Berechenbarkeitstheorie]]

Smn-Theorem - Versionsgeschichte

imported>Georg Hügler am 15. November 2019 um 23:10 Uhr