smn theorem stephen kleene

elise

hallo

ich komme von der utm, der universellen Turing Maschine, und begreife diese "umgangsprachlich" als "Interpreter-satz".
denn für eine Modellprogrammiersprache existiert ein Interpreter, der den Programmcode (in codierter Form) und darüberhinaus als zweites Argument einen Wert als Eingabe erhält und mit diesen Eingaben die Ausgabe des genannten Programms mit der genannten Eingabe ermittelt.

Nun gibt es darüber hinaus ein Übersetzungslemma, dass ich leider nur in ein paar wenigen links (und nur sehr speziell) bei google finde: das smn Theorem von Stephen Kleene. Im Grunde geht es darum, andere universelle Programmiersprachen in unsere Modellprogrammiersprache zu übersetzen. Denn unsere Modellprogrammiersprache kann keineswegs als die einzig vernünftige betrachtet werden, es existieren Willkürlichkeiten in ihrer Definition, die auch anders definiert werden könnten.
Und nun kommt das smn Theorem ins Spiel.

Zu jeder berechenbaren Funktion $f : \subseteq N^{2} \rightarrow N$
gibt es eine total-berechenbare Funktion
$r : \subseteq N \rightarrow N$ , so dass für alle $i, n\in N$ gilt
$f(i,n) = \vartheta_{r(i)} (n).$

Ich verstehe den Beweis dazu halbwegs. Das Problem liegt hier in der Abstraktion.
Ich konnte mir die Idee hinter der universellen Maschine noch erklären, nur hier wäre es toll, wenn jemand in seinen eigenen Worten, vielleicht auch "formelfrei" das smn Theorem erläutern könnte.

Vielleicht habe ich Glück

Danke.

<neue>elise benutzt gross und klein schreibung *g*</neu>

elise

ich habe es, denke ich.

man sollte immer threads formulieren, dann kommt man übers schreiben auf neue ideen

im grunde ist es alleine der fakt, dass nun nicht nur die universelle maschine als einzigartige "übersetzersprache" gesehen werden kann, sondern eben als nur eine von vielen.

diese "vielen anderen" zu finden.. darum kümmert sich das smn theorem. kleene behauptet einfach, dass es eine totale funktion r gibt, über die die modellsprachen "zusammenhängen". also kann man die eine in die andere "übersetzen" über diese funktion.

nun schau ich mir daraufhin nochmal den beweis an.

danke fürs zuhörn

Hallo elise.

im grunde ist es alleine der fakt, dass nun nicht nur die universelle maschine als einzigartige "übersetzersprache" gesehen werden kann, sondern eben als nur eine von vielen.

Bei uns wurde das S-m-n Theorem als Grundeigenschaft von Familien von Algorithmen eingeführt. Die Absicht war dabei, eine grundlegende Möglichkeit zu Programmtransformation zur Verfügung zu stellen.

Also erstmal unsere Form des "Theorems":

Eine Familie von Algorithmen besitzt die S-m-n-Eigenschaft, wenn sie für jede Kombination von positiven natürlichen Zahlen m,n einen Algorithmus enthält, der eine totale (m+1)-stellige Funktion s_{m,n} berechnet, derart dass

$F^{(n)}_{s_{m,n}(u\_1,...,u\_m,i)}(x\_1,...,x\_n) = F^{(n+m)}\_i(x\_1,...,x\_n,u\_1,...,u_m)$

Diese Form der Programmtransformation reicht aus, um alle anderen daraus abzuleiten.

Und jetzt mal eine weniger formale Erklärung:
In der Praxis sind häufig Programme notwendig, die andere Programme erzeugen oder modifizieren. Betrachte dazu ein Programm P, dass zwei Eingabevariablen x und u benötigt: P(x,u). Nun wollen wir die zweite Variable u mit einem festen Wert belegen und das Programm derart modifizieren, dass nur noch x erwartet wird. Jeder Zugriff auf u innerhalb des Programms muss also durch den Konstanten Wert ersetzt werden.
Nun erwartet man aber, dass eine solche Modifikation automatisch durchgeführt und durch ein geeignetes Transformationsprogramm realisiert werden kann.
Auf der abstrakten Ebene von Familien von Algorithmen entspricht das aber gerade einer Indextransformation durch einen anderen Algorithmus in dieser Familie.

Hat also unser Programm P den Index i
$P(x,u) = F^{(2)}_i(x,u)$

so soll es eine 2-stellige totale und in der betrachteten Familie berechenbare Funktion s geben, so dass
$F^{(2)}\_i(x,u) = F^{(1)}\_{s(u,i)}(x)$

Für die "automatisierte Indexumrechnung" ist also s zuständig, und s kennt den Wert u den wir festhalten wollen und den Index der ursprünglichen Funktion.

Obiges Theorem ist nur eine Verallgemeinerung.

Ich finde die Smn-Eigenschaft auch nicht besonders schön bzw ist es schwer nachzuvollziehen, warum sich gerade sie und nichts anderes durchgesetzt hat.

Als ganz pragmatischer Grund für sie kann man noch sagen, dass sie bei Reduktionsbeweisen fast immer benötigt wird. D.h. wenn man zeigen will, dass eine bestimmte Funktion in einer Algorithmenfamilie unberechenbar ist und dabei die Reduktionsmethode anwendet.

Gruß, space

elise

danke

das ist für mich der absolut spannendste themenbereich, den ich bisher im studium hatte. (abgesehen, dass bei der klausur am ende rund 90% regelmäßig durchfallen, aber was interessiert mich eine klausur, ich will es verstehen)

vielleicht wär dein beitrag noch was für die faq, falls irgendwann jemand anderes mal in dieser richtung sucht.

Jester

Ja, finde die Erklärung auch schön... das ruft Erinnerungen wach