Kleiner Exkurs: utm-/smn-Theorem und Programmiersprachen...

... und unsere Nummerierungen von $P^{(1)}$.

Da ich mittlerweile ein paar Mails zu diesem Thema bekommen habe, würde ich hier gerne noch etwas erläutern. Für viele ist das Theorem noch nicht greifbar. Ebensowenig die Nummerierung $\varphi$ der einstelligen, berechenbaren Funktionen $P^{(1)}$. Auch den Begriff Modellprogrammiersprache in Bezug auf $\varphi$ haben ein paar gehört, können das aber noch nicht so ganz "anfassen". Ich versuche mal mal Glück, vielleicht wird es nach meinen Ausführungen für euch etwas deutlicher.

Achtung: während wir im Skript $P^{(1)}$ direkt nummerieren, gehe ich zunächst einen etwas anderen Weg. Also nicht erschrecken. Am Ende folgt die Auflösung.

Zunächst: Warum ist $\varphi$ eine Programmiersprache?

Sicher habt Ihr schon einmal im Kurs imperative Programmierung (01613) oder Einführung in die objektorientierte Programmierung (01618) belegt. Dort programmieren wir in Java und Pascal. Was hat nun Java und Pascal mit uns und $\varphi$ zu tun?!

Zäumen wir das Pferd mal von hinten auf.

Nehmen wir zunächst eine Funktion $f(x)=x$, d.h. unsere Identitätsfunktion aus $P^{(1)}$. Im Endeffekt wollen wir diese Funktion auf unserem Computer, unserer Turingmaschine berechnen. Wir können, wie man sich leicht vorstellt, eine beliebige Funktion nehmen. Aber $f$ reicht für unsere Zwecke komplett aus.

So sieht unser Programm in PASCAL aus:

begin
writeln(ParamStr(1));
end.

Und so in Java

public static void main(String []args){
System.out.println(args[0]);
}

(Bitte nicht darauf festnageln, dass ich "public class" bei Java und "program" bei PASCAL vergessen habe, mir geht es nur um's Verständnis)

Wir sind uns einig, dass damit die Funktion $f$ berechnet wird? Gut. Und da wir $\varphi$ eine Programmiersprache genannt und gesagt haben, dass es nur eine Programmiersprache zu geben braucht (Äquivalenz und so), nennen wir die Programmiersprache Java einfach $\kappa$ (Kappa) und PASCAL $\omicron$ (Omicron). Das sind also unsere Nummerierungen von $P^{(1)}$, bzw. sollen es einmal werden.

Erinnert Ihr euch, wie $\varphi$ definiert war? Das machen wir mit $\kappa$ und $\omicron$ genauso! Wir haben nur ein anderes Alphabet. Hatten wir bei $\varphi$ das Alphabet $\Omega:=(1\mid{B}\mid{(}\mid{)}\mid{,}\mid{:}\mid{R}\mid{L})$, so sind wir bei $\kappa$ und $\omicron$ bei ein paar mehr Zeichen. Ich führe sie jetzt nicht alle auf, aber die paar sollten genügen. Wir müssen unsere Programme von oben mit Zeichen aus diesem Alphabet darstellen können:

$\Omega_\kappa:=(b\mid{e}\mid{g}\mid{i}\mid{n}\mid{(}\mid{)}\mid{;}\mid{.}, ...)$

$\Omega_\omicron:=(p\mid{u}\mid{b}\mid{l}\mid{i}\mid{(}\mid{)}\mid{[}\mid{:}\mid{]}\mid{;}, ...)$

Wie gesagt: nicht alle Zeichen drin. Hauptsache Ihr wisst, worauf ich hinaus will. Kommen wir nun zu unseren Nummerierungen $\kappa$ und $\omicron$. Diese werden genauso definiert wie unser $\varphi$.

• Ordnungsfunktion $a$ und $b$ für die Alphabete $\Omega_\kappa$ und $\Omega_\omicron$, so dass wir mit $\nu_{\Omega_\kappa}$ und $\nu_{\Omega_\omicron}$ die Nummerierung aller Worte aus $\Omega_\kappa^{*}$ und $\Omega_\omicron^{*}$ haben. Und wie bei $\nu_\Omega$ nicht nur Programme, sondern auch Kauderwelsch wie z.B. $"g(;b"$.
• $\nu_P\kappa : \mathbb{N} \rightarrow BP$, z.B. $\nu_P\kappa(i)$ als die Nummerierung des Bandprogramms $i$. Es ist definiert durch:
  $\nu_P\kappa(i)=\begin{cases}\nu_{\Omega_\kappa}(i)&\text{ wenn }\nu_{\Omega_\kappa}(i)\in{BP}\\Endlosschleife&\text {sonst}\end{cases}$
  Wir bekommen damit zur Nummer $i$ das zugehörige Bandprogramm wenn es tatsächlich ein Bandprogramm ist. Oder einfach nur eine Endlosschleife wenn die Nummer $i$ zu irgendwelchem Kauderwelsch gehört, denn mit $\nu_{\Omega_\kappa}$ haben wir (siehe oben) alle Worte über $\Omega_\kappa$, d.h. auch Unsinn, nummeriert.
•  $\nu_P\omicron: \mathbb{N} \rightarrow BP$ wird genauso definiert wie $\nu_P\kappa : \mathbb{N} \rightarrow BP$
• $\nu_{M\kappa} : \subseteq \Omega_\kappa^{*} \rightarrow BM$ und $\nu_{M\omicron} : \subseteq \Omega_\omicron^{*} \rightarrow BM$. Damit bekommen wir zum den Worten $\omega_\kappa$ und $\omega_\omicron$ (Achtung: die Worte sind nach der Definition von $\nu_P\kappa$ und $\nu_P\omicron$ immer die Worte eines echten Bandprogramms aus der Sprache PASCAL ($\Omega_\kappa$) oder Java ($\Omega_\omicron$).  Auch wenn es Endlosschleifen sind, weil die Zahl nicht zu einem Bandprogramm, sondern zu Kauderwelsch gehört hat.
• Funktion $\xi:BM \rightarrow P^{(1)}$ mit  $\xi(M) := \iota^{-1}{f{_M}}\iota$. $\xi(M)$ ist also die Funktion aus $P^{(1)}$, welche die Funktion der Bandmaschine $M$ berechnet.
  Warum haben wir kein $\xi_\kappa$ und kein $\xi_\omicron$? Sehen wir gleich!

Wir haben mit Java und Pascal also das gemacht, was wir mit $\varphi$ getan haben. Nur nutzten wir nicht $\Omega:=(1\mid{B}\mid{(}\mid{)}\mid{,}\mid{:}\mid{R}\mid{L})$ als "Programmieralphabet", sondern $\Omega_\kappa$ für unsere Zeichen der PASCAL-Programme und $\Omega_\omicron$ für Java.

Das führt uns zu ihren Kompositionen:

$\kappa = \xi\circ\nu_M\kappa\circ\nu_P\kappa$

$\omicron = \xi\circ\nu_M\omicron\circ\nu_P\omicron$

Die ebenfalls Nummerierungen von $P^{(1)}$ sind. Damit sie zu $\varphi$ äquivalent sind, müssen sie das utm- und das smt-Theorem erfüllen. Kommen wir daher zum utm-Theorem.

utm-Theorem für $\kappa$ und $\omicron$

Intuitiv wisst Ihr schon, dass beide Programmiersprachen das utm-Theorem erfüllen. Sie können interpretiert/compiliert werden und unsere Funktion berechnen. Das könnt Ihr im zugehörigen Compiler testen.

Und genau das ist unser $u$ aus der Definition des utm-Theorems:

$u_\varphi(i,x) = \varphi_i(x)$

$u_\kappa(i,x) = \kappa_i(x)$

$u_\omicron(i,x) = \omicron_i(x)$

Euch ist sicherlich auch klar, dass jeder Compiler/Interpreter für jede Programmiersprache unterschiedlich ist. Während ich für PASCAL Befehle wie "Writeln();" interpretieren und in Maschinencode für x86 (oder andere Prozessoren) übersetzen darf, muss ich für Java Zeug in Form von "System.out.println();" interpretieren. Während beide gänzlich unterschiedliche Worte über ihren Alphabeten $\Omega_\kappa$ und $\Omega_\omicron$ sind, so sind die daraus entstehenden Bandmaschinen jedoch gleich!

Und genau das ist der Grund, warum wir nur einmal $\xi$ definiert haben. Wir nutzten zwar unterschiedliche Programmiersprachen ($\kappa$ und $\omicron$) und hatten natürlich auch unterschiedliche Programme $BP$, aber immer ein Berechnungsmodell, d.h. nur eine $BM$, z.B. die gleichen Assembler Befehle für einen x86 Prozessor (oder die gleichen Befehle für eine Turingmaschine).

Ich nehme also die Programmiersprachen-Kommandos "Writeln();" und "System.out.println();"  und übersetze sie mit den zugehörigen Funktionen die gleiche Bandmaschine, die auf dem x86 Prozessor ausgeführt wird.

$\nu_{M\kappa}("Writeln();")=BM_1$

$\nu_{M\omicron}("System.out.println();")=BM_1$

Nur haben wir oben nicht einen x86 Befehlssatz als Berechnungsmodell, sondern eine Turingmaschine gewählt. D.h. die Bandmaschine $BM_1$ hat die Befehle in der Form, wie unsere Turingmaschine sie versteht. Denn die TM ist unser mathematisches, einfaches Modell für unsere Berechnungen. Und nach der Church/Turing-These ist sie genauso mächtig wie unser x86 Prozessor. Nur brauchen wir uns um die komplizierten Befehle des Prozessors nicht zu kümmern und verbleiben bei den überschaubaren Befehlen der TM 😉

Im Endeffekt hat also jede Nummerierung, d.h. jede Programmiersprache ihren eigenen Interpreter, die universelle Funktion $u$, der die Befehle der Programmiersprache in die Befehle des Berechnungsmodells (sei es TM, x86, Registermaschine oder sonstwas äquivalentes) übersetzt.

Und da wir am Ende immer auf einem Berechnungsmodell landen (landen können, dazu gleich auch noch mehr), egal welche (äquivalente) Programmiersprache/Nummerierung wir verwenden, liegt ein Schluss sehr nahe: wir können zwei Äquivalente Sprachen auch ineinander übersetzen.

Und das ist dann auch der Bezug zum Übersetzungslemma, dem smn-Theorem. Nennen wir diese Funktion einfach mal $r$, so können wir unsere Programmiersprachen Pascal und Java ineinander übersetzen, so dass mathematisch gilt:

$\kappa(i)(x) = \omicron(r(i))(x)$

Wie $r$ funktioniert, könnt Ihr euch sicher bereits im Kopf zurechtschustern. Z.B. würde $r$ uns die äquivalenten Befehle "Writeln();" und "System.out.println();" ineinander übersetzen: Tun wir mal so, als wären das Befehle funktionierender Programme, so haben sie durch die Nummerierungen $\kappa$ und $\omicron$ auch entsprechende Nummern. Seien die willkürlichen Nummer der beiden Befehle:

$\kappa(27181)="Writeln(x);"$ und

$\omicron(516322)="System.out.println();"$,

so übersetzen wir mit $r$ letztendlich:

$\kappa(27181)(x) = \omicron(r(27181))(x) = \omicron(516322)(x)$

Wie geht $r$ dazu vor? $r$ nutzt einfach die universellen Funktionen von $\kappa$ und $\omicron$. Da beide Interpreter am Ende die gleiche Bandmaschine für "Writeln();" und "System.out.println();" ausspucken, können wir das problemlos tun.

Und hier kommt das "Mehr" und die Auflösung

Wir sind sogar nicht einmal auf das gleiche Berechnungsmodell, bzw. die gleiche Bandmaschine $BM$ angewiesen. Auch wenn unsere Programmiersprachen gänzlich andere Berechnungsmodelle füttern (z.B. wir interpretieren PASCAL für x86 und Java für ARM), so haben wir dennoch eine gemeinsame Basis! Die Nummern beider Programme werden zwar auch auf anderen Berechnungsmodellen (x86 und ARM) ausgeführt, haben alle eigene Bandmaschinen $BM$, berechnen aber die gleiche Funktion aus $P^{(1)}$!

Denn hier führt am Ende alles hin: egal welche Programmiersprache und welches Berechnungsmodell. Haben wir eine Programmiersprache/Nummerierung, die eine berechenbare universelle Funktion $u$ (utm-Theorem) besitzt und das smn-Theorem erfüllt, so sind diese äquivalent und berechnen alle das Gleiche: die Funktionen aus $P^{(1)}$.

Und da das so ist, kann ich PERL weiterhin Java und PASCAL guten Gewissens vorziehen 😉

Datum: 30. August 2013
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url

Sie können zum Ende springen und ein Kommentar hinterlassen. Pingen ist im Augenblick nicht erlaubt.