Binäre Addition mit einer Turing Machine

Die von Alan Turing (1912-1954) erdachte Turing Machine ist ein Modell für eine universelle Rechenmaschine. Die üblicherweise diskutierten Beispiele von Turing Maschinen Programmen sind jedoch selten wirklich geeignet Zweifel daran auszuräumen, dass eine Turing Machine jede beliebige andere Maschine simulieren können soll. Die meisten Beispiele sind eher trivial, etwa wird die Addition oder Subtraktion häufig mit unär codierten Zahlen implementiert, man bewegt sich hier etwa auf dem Niveau eines Kindergartenschülers, der mit den Fingern zu Rechnen lernt.

Einen interessanteren Algorithmus wie die binäre Addition von Zahlen sieht man dagegen kaum je durchdiskutiert. Dabei ist der Algorithmus mit seinen Regeln für die Behandlung des Übertrags ein schönes Beispiel für etwas, was man lernen und mit Hilfe vieler Übungen meistern muss.

Ein möglicher Grund für die beschränkte Leistungsfähigkeit üblicher Turing Maschinen Programm dürfte sein, dass es kaum wirkliche Turing Maschinen gibt, die Beispiel beschränken sich daher auf Algorithmen, die einfach genug sind, dass man sie von Hand durchspielen, oder bestenfalls auf einem Simulator durchspielen kann. Daher ist die Turing Maschine von Mike Davey besonders interessant: eine Maschine, die sich so eng wie möglich an das Konzept hält, welches Turing in seiner Arbeit von 1937 beschrieben hat.

Der folgende Film zeigt Mike Davey's Turing Maschine, wie sie ein Programm ausführt, welches zwei binäre auf dem Band codierte Zahlen addiert. Die Maschine beginnt damit, die Summanden auf das Band zu schreiben, erst dann wird das Programm gestartet. Es beginnt damit, den zweiten Summanden ein Feld nach rechts zu kopieren, um zwischen den beiden Summanden Platz für die Summe zu schaffen. Dann beginnt die eigentliche Addition: die jeweils letzten Ziffern beider Summanden werden gelesen, gelöscht und deren Summe vor den bereits geschriebenen Teil der Summe geschrieben. Der Übertrag wird in einem separaten Satz von Zuständen bespeichert, so dass er bei der nächsten Summe berücksichtigt werden kann.

Im Film wird die Summe 1291 + 719 = 2010 berechnet. Das Programm nimmt an, dass beide Summanden gleiche Stellenzahl haben, daher ist der initiale Bandinhalt

10100001011 01011001111

Nach 368 Schritten und gut 14 Minuten bleibt das Resultat 11111011010 auf dem Band stehen. Damit man nicht so lange warten muss, ist der Film 4 mal schneller als das Original.