Im Rahmen meiner Vorbereitungen auf die Klausur habe ich mich etwas länger als gewünscht mit der Berechnung des Hamming-Codes und des Hamming-Abstands herumschlagen müssen. Der Hamming-Code kann dazu benutzt werden, einfache Fehler in Worten zu finden und zu korrigieren. Wir definieren hier mal zunächst den Hamming-Abstand wie im Skript:

Hamming-Abstand (hd) zwischen zwei Worten ist die Anzahl der der Bitstellen, an denen sich zwei Worte unterscheiden.

Hamming-Abstand (HD) des gesamten Codes ist der Mindestabstand zwischen den einzelnen Worten. D. h. haben wir Worte $w_1$, $w_2$ und $w_1$, so berechnen wir zunächst die Abstände $hd(w_1, w_2)$, $hd(w_1, w_3)$, $hd(w_2, w_3)$ und wählen davon den kleinsten.

Beispiel: $w_1=10110$, $w_2=11010$ und $w_1=01010$. Unser Codewort $C$ ist:

$w_1=10110$
$w_2=11010$
$w_3=01010$

$hd(w_1, w_2)=2$, da sich $w_1$ und $w_2$ an Stellen 2 und 3 unterscheiden.

$hd(w_1, w_3)=3$, da sich $w_1$ und $w_3$ an Stellen 1, 2 und 3 unterscheiden.

$hd(w_2, w_3)=1$, da sich $w_3$ und $w_4$ nur an Stelle 1 unterscheidet.

Damit ist der Hamming-Abstand des gesamten Codes $HD(C)=1$

Berechnung des Hamming-Codes

Wie berechnen wir nun den Hamming-Code eines gegebenen Datenworts? Das ist ebenfalls nicht schwer, lädt aber dazu ein, sich zu verrechnen.

Beispiel: Hamming-Code für $01001101$

1. Festlegeung wie viele Prüfbits benötigt werden: Jedes Bit an Stelle einer Zweierpotenz $(1,2,4,8,16,32, ...)$ wird ein Prüfbit. Wir haben 8 Stellen in unserem Datenwort und brauchen daher 4 Prüfbits. Macht also insg. 12 Bits in unserem neuen Codewort.

2. Damit sieht unser "Platzhalter-Codewort" wie folgt aus:

_ _ 0 _ 1 0 0 _ 1  1  0  1

mit Platzhaltern für Prüfbits $C_1, C_2, C_4$ und $C_8$.

3. Nun schauen wir, was der Inhalt der Prüfbits wird, denn nicht jedes Datenbit geht in die Berechnung eines jeden Prüfbits ein. Wir legen folgendes fest (und das wird nun ein komischer Satz, aber keine Sorge, er wird gleich erklärt): Ein Bit aus dem Datenwort auf Postion $k$ wird nur dann in die Berechnung des Prüfbits $C_i$ einbezogen, wenn die binäre Darstellung von $k$ an Position $log_2(i)$ eine $1$ hat. Puh!

Aber keine Sorge, das entschlüsseln wir gleich. Frage ist: Welche Datenbits aus unserem Datenwort gehen in die Berechnung von $C_1, C_2, C4$ und $C8$ ein? Dazu gehen wir wie folgt vor:

3a. Wir nummerieren die 12 Bits / Stellen unseres "Platzhalter-Codeworts" von links nach rechts:

1 2 3 4 5 6 7 8 9 10 11 12
_ _ 0 _ 1 0 0 _ 1  1  0  1

Z. B. Für Prüfbit $C_1$ muss lt. Definition an Stelle $log_2(1)=0$ der binären Darstellung der Position $k$ im "Platzhalter-Codeworts" eine $1$ stehen, wenn der Wert von der Position $k$ aus dem "Platzhalter-Codeworts" in die Berechnung von $C_1$ einfließen darf. Die Werte für $k$ sind die Positionen der Datenbits (die Prüfbits gehen ja nicht in die Berechnung ein), d. h. $3,5,6,7,9,10,11$ und $12$. Wir stellen also Positionen 3, 5, 6, 7, 9, 10, 11, 12 zunächst in binär dar.

Da wir nun für alle Codeworte $C_i$ prüfen müssen, ob an der betreffenden Stelle $log_2(i)$ eine $1$ steht, nummerieren wir diese Auflistung der Übersichtlichkeit halber (nicht vergessen: hier gilt von rechts nach links):

Binär        8 4 2 1
-------------------- 
Position 03: 0 0 1 1
Position 05: 0 1 0 1
Position 06: 0 1 1 0
Position 07: 0 1 1 1
Position 09: 1 0 0 1
Position 10: 1 0 1 0
Position 11: 1 0 1 1
Position 12: 1 1 0 0
--------------------
Stelle       3 2 1 0

• Wir prüfen für alle Positionen nun für $C_1$, ob an Stelle $log_2(1) = 0$ eine $1$ steht: bei Position 3, 5, 7, 9, 11 steht das. Also gehen Positionen 3, 5, 7, 9 und 11 des "Platzhalter-Codeworts" in die Berechnung von $C_1$ ein.
• Nun ist $C_2$ dran. Die zu prüfende Stelle ist $log_2(2) = 1$. Positiv für Position: 3,6,7,10,11.
• Für $C_4$: Die zu prüfende Stelle ist $log_2(4) = 2$. Positiv für Position: 5,6,7,12.
• $C_8$: Die zu prüfende Stelle ist $log_2(4) = 3$. Positiv für Position: 9,10,11,12.

Ist die Summer der Positionen gerade, so ist $C_i=0$. Ist sie ungerade, so ist $C_i=1$. Hier noch einmal unser "Platzhalter-Codewort" mit nummerierten Stellen:

1 2 3 4 5 6 7 8 9 10 11 12
_ _ 0 _ 1 0 0 _ 1  1  0  1

Wir berechnen nun die Prüfbits.

• $C_1=0$, da $P_3+P_5+P_7+P_9+P_{11}=0+1+0+1+0=2$ (gerade)
• $C_2=1$, da $P_3+P_6+P_7+P_{10}+P_{11}=0+0+0+1+0=1$ (ungerade)
• $C_4=0$, da $P_5+P_6+P_7+P_{12}=1+0+0+1=2$ (gerade)
• $C_8=1$, da $P_9+P_10+P_{11}+P_{12}=1+1+0+1=3$ (ungerade)

4. Nun haben wir unsere Prüfbits berechnet uns setzen sie an entsprechender Stelle in unser "Platzhalter-Codewort" (Prüfbits sind fett):

1 2 3 4 5 6 7 8 9 10 11 12
0 1 0 0 1 0 0 1 1  1  0  1

Damit ist unser gesuchtes Hamming-Codewort: $010010011101$

Beispiel 2: Versucht es mal selbst mit $10011010$

Lösung zeigen

0 1 1 1 0 0 1 0 1 0 1 0

Und wieder zurück

Stellt sich die Frage, wie wir eingeschlichene Fehler wieder beseitigt bekommen. Wir bleiben bei unserem ersten Beispiel und nehmen an, das obige Codewort sei falsch übertragen worden:

1 2 3 4 5 6 7 8 9 10 11 12
0 1 0 0 1 0 0 1 1  1  0  1 (korrektes Codewort)
0 1 0 0 1 0 0 1 0  1  0  1 (falsch übertragenes Codewort, Fehler rot markiert)

1. Wir empfangen das fehlerhafte Codewort und schreiben uns zunächst die Prüfbits $C_i$ und die zugehörigen Bitpositionen zum Prüfbit raus:

• $C_1=0$, es ist aber $P_3+P_5+P_7+P_9+P_{11}=0+1+0+0+0=1$ (ungerade) - Fehler!
• $C_2=1$, es ist $P_3+P_6+P_7+P_{10}+P_{11}=0+0+0+1+0=1$ (ungerade) - OK!
• $C_4=0$, es ist $P_5+P_6+P_7+P_{12}=1+0+0+1=2$ (gerade) - OK!
• $C_8=1$, es ist aber $P_9+P_10+P_{11}+P_{12}=0+1+0+1=2$ (gerade) - Fehler!

2. Wir haben damit in $C_8$ und $C_1$ einen Fehler. $8+1=9$. Der Fehler im Codewort ist also auf in Bit 9!

Gar nicht so schwer, oder?

Okay, schon wieder ein Kurs, man vom Namen her leicht unterschätzen könnte (im Vergleich zu TheoInf ist der Kurs aber wirklich nicht so schwer). Ich zitiere aus Seite 3 des Kursskripts zum Kurs

"Auch die Einsendeaufgaben zum Kurs werden sich nicht immer streng an den Text und Inhalt der Kurskapitel halten. Hier werden weitere Bezüge zu anderen Kursen auftreten und "Transferleistungen" von Ihnen verlangt, d. h. Sie müssen sich selbstständig mit neuen Themen befassen und dazu auch auf weitere Sekundärliteratur zurückgreifen"

Und das ist - nach Bearbeitung der EA1 - wörtlich zu nehmen. Während Aufgabe 1 und 2 mich schmunzeln ließen (Werte aus Screenshots herausschreiben), geht es bei Aufgabe 3 und 4 um Dinge, die nicht im Skript zu finden sind. Man bekommt eine USB-Übertragungsrate genannt und muss berechnen, wie viele Daten im 1-ms-Timeframe übertragen werden können. Anschließend bekommt man Abtastrate von Audiodaten, die Auflösung, die Kanäle und muss berechnen, ob man mit der Bandbreite für isochrone Daten (zzgl. Interrupt und Steuerdaten pro Frame) auskommt oder nicht. In diesem Stil geht es weiter.

Zum Abschluss darf man sich dann wieder mit Assembler befassen und Hex-Werte addieren. Mal mit Über- oder Unterlauf (Sättigung), mal mit Wrap Around und jeweils mit und ohne Vorzeichen (wer erinnert sich noch an das Zweierkomplement? Hand hoch!). Das letzte Mal hatte ich so etwas im Kurs Computersysteme I und II, d. h. alte Skripte rauskramen. Im 01744-Skript ist zu dem Thema kein Sterbenswörtchen und kein Beispiel. Das ist auch der Grund, warum ich demnächst auch für PC-Technologie ein paar Beiträge erstellen werde. Quasi eine Rekapitulation für mich selbst, evtl. als Auffrischung auch für euch.

Aber: Die Zusammenfassungen gibt es leider für das neue Semester. Ich würde zwar gerne behaupten, dass ich beide Kurse aus beruflichen Gründen schieben musste. Aber wenn ich ehrlich bin, bin ich wohl eher durch die dreimonatige Pause zwischen der Abgabe der Bachelor-Thesis und dem Anfang des Master-Studiums etwas bequem geworden und habe die Füße hochgelegt (und noch einmal Firefly geschaut)

Da ich euch aus Prinzip nicht mit privatem langweilen möchte, sondern sich die Beiträge vorwiegend nur um die Uni drehen, wird es die nächste Zeit etwas ruhiger. Ich denke aber, dass ich demnächst auch die ersten Zusammenfassungen veröffentlichen werde können. Bis dahin: Viel Erfolg bei eurem Studium. Durchhalten!

4.5 Jahre Arbeit münden in ein blau-weißes 180g/m²-Papier, unterschrieben vom Vorsitzenden des Prüfungsausschusses (derzeit Prof. Güting) und dem Dekan (Prof. Hackstein) der FernUni. Zusammen mit zwei beglaubigten Kopien per Einschreiben. So wie das Bachelor-Studium angefangen hat, so endet es auch: Mit dem Gang zum Briefkasten.

Zwei Gutachter prüfen die Thesis und machen sich doch so einige Gedanken darüber, wie ich den schriftlichen Gutachten entnehmen konnte. Setzt daher nicht drauf, dass nur der Anfang und der Schluss gelesen werden. Ihr solltet euch bei beiden Kapiteln daher große Mühe geben, denn es ist wie mit einem guten Buch: Der Anfang bringt einen dazu, das Buch nicht aus der Hand zu legen und der Schluss entscheidet darüber, welches Gefühl der Leser nach der Lektüre hat.

In jedem Fall gilt mein Dank dem Team der FernUni, die meiner Meinung nach einen großartigen Service bietet und sich auch nicht zu bequemt ist, auf Sonderwünsche der Studenten einzugehen. Alle Professoren sind sich nicht zu schade auf Mails von Studenten zu antworten, das Sekretariat der Professoren bemüht sich sehr, Termine für mündliche Prüfungen zu finden, die auch dem Studenten passen, das Prüfungsamt steht einem mit Rat und Tat (Mails werden häufig innerhalb von 24h beantwortet) zur Seite und die Studienberatung hilft zügig bei Fragen zur Belegung. Ohne diesen Service hätte ich wohl das Studium nicht nebenberuflich abschließen können. Ohne die FernUni hätte ich wahrscheinlich nicht einmal studiert.

Ich halte den Beitrag gerade aufgrund von Zeitmangel etwas kurz, werde aber noch ein paar Dinge zur Thesis selbst, der Themenauswahl, dem Kolloquium und der Bewertung schreiben. Ach ja: Und die selbst gebastelte TeX-Vorlage für die Thesis lade ich selbstverständlich auch hoch.

PS, zur Info: Als Abschlussdatum wird der Abgabezeitpunkt der Thesis gewertet und nicht der der Zeugnisausstellung oder der Kolloquiums.

Update: Hier der Beitrag zur Thesis und zum Kolloquium.

In diesem Sinne: Danke für das Lesen des Blogs. Hoffentlich habe euch meine Notizen zur theoretischen Informatik etwas helfen können. Ich werde versuchen das Blog auch im Master fortzuführen, weiß natürlich aber noch nicht, ob das Sinn macht im Stil der Beiträge zur theoretischen Informatik weiterzumachen. Das werde ich wohl von Fach zu Fach entscheiden.

Kursbeschreibungen des Inhalts wird es aber selbstverständlich weiterhin geben.

Da mich nun mittlerweile die gefühlte 100. Mail erreicht hat, die nach meinem Spickzettel für Algorithmische Mathematik (01142) fragt, habe ich beschlossen meinen Widerstand aufzugeben. Widerstand? Ja, Widerstand. Euch ist bewusst, warum Spickzettel sinnvoll sind? Durch die Anfertigung eines Spickzettels konzentriert man sich über einen längeren Zeitraum auf den Inhalt und seine Aufarbeitung und braucht - oh Wunder! - ihn in der Klausur dann nicht mehr. Das ist der Grund, warum im Wintersemester 09 dieser Spickzettel zu der 150% Klausur von Prof. Dr. Hochstättler zugelassen war (und es wohl noch ist, wie ich den Mails bzgl. meines Spickzettels implizit entnehmen kann).

Durch diesen didaktischen Kniff (und das tolle Skript, Prof. Dr. Hochstättler ist sehr engagiert und nimmt seinen Lehrauftrag äußerst ernst) konnte ich die bisher beste Note in einem mathematischen Fach holen. Daher: Auch wenn Ihr euch meinen Spickzettel herunterlädt, eine kleine Bitte: fertigt zunächst euren eigenen an und schaut euch erst dann meinen an um evtl. fehlende Themen noch aufzunehmen.

Lange Rede, kurzer Sinn: Das war damals meiner.

Und noch ein paar Tipps, die ich bereits an anderer Stelle gegeben habe:

Ihr habt 150% in der Klausur, die auf zwei Stunden ausgelegt ist. Der Schlüssel ist also auch hier: schnell sein. Es gibt sehr schreibintensive Themen, wo Flüchtigkeitsfehler euch Punkte kosten können. Dazu gehören die LU Zerlegung, Chokesly, Dijsktra, Simplex und Optimierung. Hier heißt es: Üben, üben, üben!

Die folgenden Beschreibungen sind ohne Gewähr. Sie sind aus dem WS09, d.h. es ist mittlerweile 3 Jahre her und ich habe mich mit dem Stoff nicht mehr beschäftigt. Sollten sich also Fehler eingeschlichen haben, bitte sofort melden.

SIMPLEX

Der absolute Punktebringer. Aber wehe man verrechnet sich. Daher habe ich mir irgendwann alles haarklein aufgedröselt und ein kleines Howto geschrieben. Alle, die im Stoff bisschen drin sind, sollten das nachvollziehen können. Wie gesagt: ohne Gewähr... ist alles lange her

- Das kleine HowTo zu SIMPLEX gibt es auch als PDF.

- Um nicht immer die Klammern usw. in den Rechnungen zu schreiben, habe ich mir auch eine Simplex Vorlage gebastelt.

Beispiel 

1. Das Problem wird in Normalform gebracht

A) Zielfunktion

Das Problem wird immer in Maximierungsform dargestellt. Ein Problem in Minimierungsform wird einfach mit (-1) multipliziert. 

B) Nebenbedingungen

Die Nebenbedingungen werden in Gleichungsform überführt. Generell ist die Vorgehensweise wie folgt:

Dabei ist zu beachten, dass als Ergebnis keine negativen Zahlen stehen dürfen. Ist hinter dem Gleichheitszeichen/Ungleichheitszeichen ein negativer Wert, so wird die Un-/Gleichung mit (-1) multipliziert. Dabei dreht sich das $\leq$ oder $\geq$ entsprechend, das $=$ bleibt. Dann wird eine Schlupfvariable ($yA$) und eine Hilfsvariable ($s1$) eben addiert oder subtrahiert um aus der Ungleichung eine Gleichung zu machen. 

Beispiel:

C) Duales Problem (wenn nötig). Beispiel:

2. SIMPLEX Starttableu aufstellen

A) Anhand der Normalform wird das Starttableu aufgestellt. Beispiel: 

B) Die Auswahl der Pivotspalte geschieht nach folgenden Regeln. Zunächst die Spalte, wo bei einer Zelle in $\delta_2$ (Hilfsfunktion) der erste positive Wert steht ($\delta_2$, Spalte 2 mit dem Wert "1"). Dann sucht man sich die Zeile mit einem positiven Wert und teilt den x-Wert in dieser Zeile durch den positiven Wert und trägt die Werte in Spalte x/f ein. Die Zeile mit dem niedrigsten Wert beinhaltet den Pivotwert (1). 

C) Nun wird das 2. Tableu aufgestellt indem man zunächst die Pivotzeile durch das Pivotelement (1) dividiert. Diese bildet die neue Pivotzeile im nächsten Tableu. Für die anderen Zeilen geht man wie folgt vor: man subtrahiert vom alten Zeilenwert (altes Spaltenpivot*neues Zeilenpivot). Ergebnis ist die gleiche Zeile in der neuen Tabelle. Rechnung:

Die Ergebniswerte sind die neuen Zeilen im neuen Tableau. Dabei werden dann $yB$ und $y$ "im Kopf" vertauscht.

Das ganze geht so lange, bis in der Zeiler der Hilfsfunktion $\delta_2$ 

keine positiven Werte mehr sind. In diesem Fall ist es bereits jetzt soweit. Somit ist es das Endtableau für Phase 1. Wir beginnen mit

D) dem Aufstellen des Starttableaus für Phase 2

Hier werden nun die Hilfsfunktions-Zeile $\delta_2$ und die Hilfsvariablenspalte (s1) gelöscht. Das bringt uns zu folgendem Starttableau für Phase 2.

Wir wählen die Pivotspalte und Zeile wieder wie gehabt und führen wieder die übliche Rechnung durch. 

Die Rechnung führt uns zu folgender, 1. Tabelle von Phase 2:

Nun stehen nur negative Werte in der Zielfunktionszeile $\delta_1$. 

Wir können also die Lösung

 $x=1$

$y=15$

mit einem Funktionswert von

$f(x,y) = 17$

ablesen. Wäre es eine Minimierungsaufgabe, so müsste man den Funktionswert -17 nicht mit (-1) multiplizieren. Der Funktionswert wäre dann -17. 

Hier findet Ihr noch ein kleines, handschriftliches Simplex Beispiel von mir.

CHOLESKY-Zerlegung

Auch hier gilt: je schneller, desto besser. In den Übungsaufgaben und in der Klausur kommen meist nur 2x2 oder 3x3 Matritzen vor. Dafür habe ich mir damals ganz einfach für jedes Feld eine Formel gebastelt:

3x3 Matrix

That's it. Die 2x2 Matrix ist - das wollte ich schon immer mal sagen - doch trivial

... 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