Alans Früstücksvergnügen Mystery Cache

Ja da nehmen wir doch ein dem Fachgebiet ureigenes Thema: die Turingmaschine -- ab jetzt abgekürzt mit TM. Wie typisch für Informatiker, sind TMs sowohl ziemlich nutzlos, als auch ziemlich praktisch. Eine TM kann nämlich so gut wie nichts und das macht sie so praktisch. Wenn man nachweisen kann, dass etwas mit einer TM lösbar ist oder nicht, erlaubt dies Aussagen über das Problem auf welche IT-Forscher scharf sind wie Nachbars Lumpi. Soweit wollen wir hier nicht gehen. Wir benutzen eine TM um uns die Koordinaten eines Caches erzeugen zu lassen.

Wie funktioniert jetzt so eine TM? Man kann sich eine TM als langes Band vorstellen, auf welchem etwas gespeichert werden kann, sowie einen Schreib/Lesekopf, der etwas vom Band liest und wieder darauf schreibt und anschliessend den Schreib/Lesekopf bewegen kann. Das Ganze wird vervollständigt durch ein Programm, bzw. eine Zustandstabelle, welche abgearbeitet wird.

Wir brauchen hierzu keinen Computer, sondern können selbst die TM spielen, indem wir einen langen Streifen kariertes Papier nehmen und eine Kombination von Bleistift und Radierer als Schreibkopf benutzen. Bitte fangt hier nicht ganz links an, sondern lasst ca. 6 Felder frei. Insgesamt brauchen wir um die 100 Felder. Ihr müßt also ein bißchen kleben.

Wir verwenden hier die einfachste TM, die es gibt. Die TM kennt genau zwei verschiedene Symbole: ein leeres Feld [] und einen Strich |.
Wie wird jetzt ein TM-Programm abgearbeitet? Hierzu hat die TM einen aktuellen Zustand, ganz am Anfang des Programmes nimmt man hierfür einfach den ersten Zustand in der Tabelle (hier S01). Man hat also einen aktuellen Zustand und der Schreib/Lesekopf steht an einer bestimmten Stelle. Auf dieser Stelle ist jetzt ein Symbol, entweder ist das Feld leer, oder da steht ein Strich. Wir schauen jetzt beim aktuellen Zustand in der Tabelle nach: hier gibt es zwei Einträge für das, was zu tun ist, abhängig vom Symbol an der aktuellen Bandpostion. Steht an der aktuellen Bandposition ein Strich, dann nehmen wir den Eintrag der Spalte "Input  |", andernfalls nehmen wir den Eintrag der Spalte "Input  []". Z.b. bei leerer Bandposition und aktuellem Zustand S01 bedeutet dies: "write |", also mache einen Strich in das leere Feld, "move R", bewege dich eine Bandstelle nach rechts, "=> S44" und mache mit Zustand S44 weiter.

Entsprechend bedeuten die Anweisungen "write []": lösche bzw. radiere das Feld, "move .": bleibe an der Stelle, "move L": bewege dich eine Position nach links.

Dieses wird solange fortgeführt, bis man den Zustand HALT erreicht. Damit ist die Aufgabe eigentlich erklärt. Doch halt: bei nur zwei Symbolen, wovon eines einfach ein leeres Feld ist, wie kann ich da Koordinaten erkennen? Die werden einfach durch die Anzahl an Strichen vermerkt. Da wir kein unterschiedliches Zeichen für 0 und einen Abstand zwischen zwei Zahlen haben, müßt ihr wissen, wie Koordinaten aussehen, um das Ergebnis korrekt zu interpretiern.
Ein []||||[]||||||||[][]|[] kann sowohl 48 1 bedeuten, als auch 4801. Es ist also darauf zu achten, wo die Nullstellen zu erwarten sind.
Jetzt viel Spass beim Abarbeiten eines Turing-Programmes.

Nach der Turingberechnung gibt es noch eine Verschiebeung, die durch das Neuauslegen des Caches zustande kommt:
Final Nord= Turingresultat - 00 00.026, Final Ost: Turingresultat + 0 00.001.
Der Hint gilt fuer das Turingresultat, nicht fuer die Finalkoordinaten.