Increment a number in binary representation: problem in dealing with carry

Question

I am working on the following project:

Design a Turing Machine that performs the operation of incrementing a binary number. Consider that you have a binary number 𝑛. Initially, the tape has the symbol $ followed by the binary number 𝑛. The head of the Turing Machine starts positioned on the $ symbol, while the Turing Machine is in state 𝑞₀. The Turing Machine must stop when the tape contains the $ symbol followed by the binary value of 𝑛+1, and the Turing Machine is in state 𝑞_𝑓. The Δ symbol on the tape represents an empty cell on the tape.

My model

L is Left, R is Right and N represents that the head does not move:

1. From 𝑞₀ to 𝑞₁:

   • If it reads $, it stays as $ and moves the head to the right (R).

2. In 𝑞₁ (processes the bits):

   • If it reads 0, it stays as 0 and moves to the right (R).

   • If it reads 1, it stays as 1 and moves to the right (R).

   • If it reads Δ, it moves to state 𝑞₂ and moves to the left (L).

3. In 𝑞₂ (increments):

   • If it reads 0, it changes it to 1 (no carry) and goes to 𝑞_𝑓 (end).

   • If it reads 1, it changes it to 0 (carry) and continues in 𝑞₂ moving to the left (L).

   • If it reads $, it goes to 𝑞₃ and moves to the left (L).

4. In 𝑞₃ (handling of additional carry):

   • If it reads Δ, it changes it to 1 (carry at start) and goes to 𝑞_𝑓 (end).

   • If it reads 0, it stays as 0 and moves to the left (L).

   • If it reads 1, it stays as 1 and moves to the left (L).

   • If it reads $, it stays as $ and continues in 𝑞₃ moving to the left (L).

5. In 𝑞₄ (empty, special cases):

   • If it reads Δ, it changes it to 1 and goes to 𝑞_𝑓 (end).

6. Final state 𝑞_𝑓:

   • The machine stops after completing the increment.

Problem

I was told that this model was wrong. Initially I did not have the state 𝑞₄, but I added it to consider special cases of carry. I tested this with several inputs and could not spot what the problem is. Where is my mistake?

Answer 1

The problem occurs when the input number consists of only 1 digits, for instance when the tape has $11. In that case your algorithm will correctly change all these digits to 0 and identify that there is a carry, but it writes that carry to the wrong place. For the example $11 it will end the process with 1$00 on the tape, while it should be $100.

Not a problem, but:

• In state 𝑞₃ you foresee that the current symbols could be 0, 1 or $, but none of these can actually happen, as you can only arrive in state 𝑞₃ by moving left of the $ symbol, and there is nothing else than blanks on that side of the $.

• The state 𝑞₄ is unreachable (there is no incoming transition, nor is it the starting state), so it serves no purpose.

Here is your model encoded in a transition table that is given to a runnable Turing Machine in a JavaScript snippet. You can run it here and see how it goes wrong for the input $11.

createTuring({
    transitions: [
        { state: "q0", read: "$",              move: "R", nextState: "q1" },
        { state: "q1", read: "01",             move: "R", nextState: "q1" },
        { state: "q1", read: "Δ",              move: "L", nextState: "q2" },
        { state: "q2", read: "1",  write: "0", move: "L", nextState: "q2" },
        { state: "q2", read: "0",  write: "1",            nextState: "qf" },
        { state: "q2", read: "$",              move: "L", nextState: "q3" },
        { state: "q3", read: "$01",            move: "L", nextState: "q3" },
        { state: "q3", read: "Δ",  write: "1",            nextState: "qf" },
        { state: "q4", read: "Δ",  write: "1",            nextState: "qf" },
    ],
    initState: "q0",
    blank: "Δ",
    tape: "$11" // Example input
});

<script src="https://trincot.github.io/turing.js"></script>

Fix

To fix the problem, write the extra carry at the place where you find the $ symbol (not to its left), and then use the state 𝑞₃ to write a new $ at the left of that position.

So then we get this transition table:

createTuring({
    transitions: [
        { state: "q0", read: "$",              move: "R", nextState: "q1" },
        { state: "q1", read: "01",             move: "R", nextState: "q1" },
        { state: "q1", read: "Δ",              move: "L", nextState: "q2" },
        { state: "q2", read: "1",  write: "0", move: "L", nextState: "q2" },
        { state: "q2", read: "0",  write: "1",            nextState: "qf" },
        { state: "q2", read: "$",  write: "1", move: "L", nextState: "q3" },
        { state: "q3", read: "Δ",  write: "$",            nextState: "qf" },
    ],
    initState: "q0",
    blank: "Δ",
    tape: "$11" // Example input
});

<script src="https://trincot.github.io/turing.js"></script>

You can experiment with different inputs with this implementation and ensure that it now works for all valid inputs.