Construct a Turing Machine which multiplies two binary numbers.
Example 9 * 5:
1. Number (half) |
2. Number (double) |
Result | |||
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] |
To double a binary number, the bits can be shifted to the left. Dividing a binary number by two can be done by shifting it to the right, erasing the least significant bit.