Turing machine as Adder
Approach for Addition
- Numbers are given in Uniary form
- Example: 3 = 111, 2 = 11, 5 = 11111 etc.
- For addition of 3 and 4, numbers will be given in TAPE as "B B 1 1 1 0 1 1 1 1 B B".
- Convert '0' to '1' and reduce '1' from right
- Hence output will be "B B 1 1 1 1 1 1 1 B B B"
- Total number of '1' in output is = 7 which is addition of 3 and 4
TAPE movement for string "110111":
Explanation of TAPE movement
- Input is given as "11011" (2 + 2)
- Scan string from left to right
- Pass all '1'SSS and convert '0' to '1'
- Reach BLANK in right
- Convert rightmost '1' to BLANK
Input String : 11011
Output String : 1111
State Transition Diagram
We have designed state transition diagram for adder as follows:- Start scanning string from left to right
- Pass all '1's and keep moving right
- Convert '0' to '1' and keep moving right
- When BLANK(in right) is reached move one step left convert '1' to BLANK
- Keep moving left after that to point start of string
- Number of '1's is reduced because number of '1' was increased by one while converting '0' to '1'