Example Turing Machine

Turing Machine (TM) for the language L = {0ⁿ1ⁿ | n ≥ 1}, which accepts strings of equal 0s followed by equal 1s.

Components:

• Q = {q₀, q₁, q₂, q₃} (q₀ is the initial state)
• T = {0,1,X,Y,B} (B represents blank, X and Y mark processed symbols)
• Σ = {0,1} (input symbols)
• F = {q₃} (final state)

Transition Table:

Let us see how this turing machine works for 0011. Initially head points to 0 which is underlined and state is q0 as:  

The move will be δ(q0, 0) = (q1, X, R). It means, it will go to state q1, replace 0 by X and head will move to right as:  

The move will be δ(q1, 0) = (q1, 0, R) which means it will remain in same state and without changing any symbol, it will move to right as:  

The move will be δ(q1, 1) = (q2, Y, L) which means it will move to q2 state and changing 1 to Y, it will move to left as:  

Working on it in the same way, the machine will reach state q3 and head will point to B as shown:  

Using move δ(q3, B) = halt, it will stop and accepted. 

Note: 

• In non-deterministic turing machine, there can be more than one possible move for a given state and tape symbol, but non-deterministic TM does not add any power.
• Every non-deterministic TM can be converted into deterministic TM.
• In multi-tape turing machine, there can be more than one tape and corresponding head pointers, but it does not add any power to turing machine.
• Every multi-tape TM can be converted into single tape TM.

Design a TM that acts as an binary incrementer. That is, if the TM starts with the integer n (in binary) on its tape, it should halt with n + 1 (in binary) on the tape

Operation:

• The TM starts in state q0 at the leftmost digit of the binary number.
• It moves right, scanning the tape, until it encounters a blank symbol, indicating the end of the binary number.
• Upon finding the blank, it transitions to state q1 and moves left, starting the incrementing process from the least significant bit.
• In state q1, if it encounters a '0', it changes it to a '1' and halts (qf).
• If it encounters a '1', it changes it to a '0', continues in state q1 (indicating a carry), and moves left to process the next bit.
• If it encounters a blank in state q1, it means a carry propagated beyond the original number's length (e.g., 11 + 1 = 100). It writes a '1' and halts.

Transitions:

1. Move to the rightmost bit

q0, 0 → R, q0
q0, 1 → R, q0
q0, □ → L, q1   # blank found; move left to start increment

2. Add 1 / propagate carry

q1, 0 → write 1, stay, q_accept   # 0 + 1 = 1, done
q1, 1 → write 0, move L, q1       # 1 + 1 = 0, carry over
q1, □ → write 1, stay, q_accept   # carry reached left of MSB, prepend 1