Problem-1

Draw a Turing machine to find 1’s complement of a binary number. 

1’s complement of a binary number is another binary number obtained by toggling all bits in it, i.e., transforming the 0 bit to 1 and the 1 bit to 0. 

Example:

Approach: 

1. Scanning input string from left to right
2. Converting 1’s into 0’s
3. Converting 0’s into 1’s
4. Move the head to the start when BLANK is reached.

Steps: 

• Step-1. Convert all 0’s into 1’s and all 1’s into 0’s and go right if B is found go to left. 
• Step-2. Then ignore 0’s and 1’s and go left & if B found go to right
• Step-3. Stop the machine.
   

Here, q0 shows the initial state and q1 shows the transition state and q2 shows the final state. 
And 0, 1 are the variables used and R, L shows right and left. 

Explanation: 

• State q0 replace ‘1’ with ‘0’ and ‘0’ with ‘1’ and move to right.
• When BLANK is reached move towards left.
• Using state ‘q2’ we reach start of the string.
• When BLANK is reached move towards right and reaches the final state q2. 

Prerequisite – Turing Machine, 1’s and 2’s complement of a Binary Number