Question

Draw a Turing Machine that increments a ternary number by 1. Also, explain your approach in brief.

Note: For example, if the input is 22 (representing the decimal number 8), then the output should be 100 (representing the decimal number 9). For this task, consider a two-sided infinite tape

Show the computation (sequence of configurations) of the above Turing Machine for input “22”.

Answer 1

Note: B is for Blank.

0->0, L 4o 4i 0 1-1, L B->0, R 0, L 1>1, L 0->0,L 0->0, R B-> B, R 09B, R 95 qs 97

Algorithm:

1. Add a 0 at the beginning of the string (To be able to handle overflow).
2. Traverse through the string to get to the LSB.
3. Traversing backwards (LSB to MSB); use NOT operator on every 1 until you reach a 0 (Since we added a 0 at the beginning, we are certain that we will eventually reach a 0)
4. use NOT operator on said 0.
5. Traverse backwards until you reach the beginning of string.
6. If the first bit is equal to 0, you have to remove it with blank.
7. If the first bit is equal to 1, it means that overflow has occurred. (Nothing needs to be done in if you reach this step)