I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, written to the left of the head . I was given the fact that the head first reads the MSB.
I thought of an Idea but I do not see how to put it into action: My idea was to:
1.First put a $ sign at the beginning of the string
2.Place the entire string right side to it
3.Starting to increment from the end, switching $1$ with $0$
4.Once I stumble upon $0$ I replace it with $1$ and then accept it or Once I stumble upon $ I replace it with 1 and accept
I can't seem to find a way to put a $ at the beginning of the string without losing any information..any help with will be very helpful!