Question

Construct a Turing achine with on tape thai rcccivs as input an integer x 〉 1 and returns as output the integer x-1 . Integers are represented in binary. Start of the computation: The tape contains the binary representation of the input r. The tape head is on the rightmost symbol of r and the Turing machine is in the start state o End of the computation: The tape contains the binary representation of the integer r - 1. The tape head is on the rightmost bit of x 1 and the Turing machine is in the final state q

Answer 1

Design is very simple. Since input x is in binary, so if the rightmost bit is 1, then simply we have to replace rightmost 1 by 0 and we are done. If the rightmost bit is 0 then we have to replace 0 by 1 and keep on moving left and replace 0 by 1, and when 1 is encountered then replace that 1 by 0 and we are done.

Once we are done, we simply have to move to rightmost input position with ending state being q₁.

$\delta (q_0, 1 ) \rightarrow (q_2, 0, R)$ //Replace 1 by 0 and we are done

$\delta (q_0, 0) \rightarrow (q_0, 1, L)$ //Replace 0 by 1 and move left

$\delta (q_2, 0) \rightarrow (q_2, 0, R)$ //Simply go to right end

$\delta (q_2, 1) \rightarrow (q_2, 1, R)$ //simply move right

$\delta (q_2, \phi) \rightarrow (q_1, \phi, L)$ //Once input is end, move one position left and go to q₁ and finished

Please comment for any clarification.