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!

  • $\begingroup$ Move left, put $, move right. If you cannot, rewrite the entire string by one to the right. $\endgroup$ – Evil Jun 4 '17 at 18:00
  • $\begingroup$ What do you mean by rewriting the entire string by one to the right? $\endgroup$ – Lola Jun 4 '17 at 18:08
  • $\begingroup$ And how can I move left at the beginning? I don't think that it's allowed..(at least from what I understand) $\endgroup$ – Lola Jun 4 '17 at 18:18
  • $\begingroup$ If you have one-way infinite TM, then you cannot move to the left, if it is two-way infinite, it is not a problem. The data on tape is surrounded by blank symbols. If you really need to move all data to the right, just keep the current symbol in the state, move right, put the read to state, write previous one and move until blank is encountered. This way you have data moved by one symbol to the right, the head is over last symbol and now you can start your increment going left. $\endgroup$ – Evil Jun 4 '17 at 20:19

Hint: First write an informal description of the machine, then give a precise description as a transition diagram. Use the state of the Turing machine to hold the carry bit.

  • $\begingroup$ Thanks! I solved it by using a None deterministic TM. Is it also a possible way of solving it? $\endgroup$ – Lola Jun 4 '17 at 19:52
  • 1
    $\begingroup$ No. A Turing machine that computes a function $f$ has to be deterministic – given input $x$, it must always terminate with $f(x)$ on the tape. Think about it: How could a nondeterministic Turing machine compute a function? It does not make sense. $\endgroup$ – Hans Hüttel Jun 4 '17 at 19:54

This is my solution:

Turing Machine Note: B is for Blank.

I drew the Machine in this website: http://madebyevan.com/fsm


  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)

Any improvements will be appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.