Erstellen Sie eine Turing Maschine, die zwei binäre Zahlen multipliziert.

Ausgangslage

Die beiden zu multiplizierenden Zahlen sind in binärer Darstellung gegeben. Wo die beiden Zahlen in der Welt plaziert werden, kann von Ihrer Lösung abhängig gemacht werden.

Hinweis

Die beiden Zahlen können mit Hilfe der ”Zigeunermultiplikation” multipliziert werden. Bei der Zigeunermultiplikation wird die eine Zahl jeweils halbiert, während die andere verdoppelt wird. Ist die zu halbierende Zahl ungerade, so wird die zu verdoppelnde zum Resultat addiert (gelb markierte Zeilen).

Beispiel 9 * 5:
1. Zahl
(halbieren)
2. Zahl
(verdoppeln)
Resultat
        0 [0]
9 [1001] 5 [101] 5 [101]
4 [100] 10 [1010] 5 [101]
2 [10] 20 [10100] 5 [101]
1 [1] 40 [101000] 45 [101101]

Um eine binäre Zahl zu verdoppeln, können alle Bits der Zahl um eins nach links verschoben werden. Um eine binäre Zahl zu halbieren, können die Bits nach rechts verschoben werden, wobei die Stelle ganz rechts gelöscht wird.