Turing machine Introduction

Till now we have seen machines which can move in one direction: left to right.
But Turing machine can move in both directions and also it can read from TAPE as well as write on it.
Turing machine can accept recursive enumerable languages

---

Turing machine(Automata Machine) was proposed in 1931 by Alan Turing. Back then it was termed as "The Computer".

---

Below is how a TAPE looks like for turing machine:

TAPE is of infinite memory space dvivided into cells. Read/Write head positions over a cell and reads/writes data of cell.

---

Turing machine for aⁿbⁿ | n ≥ 1;
TAPE movement is shown below:
Now we will explain the logic step by step:

1. Input is given in the TAPE as "aabb", "B" is BLANK symbol. R/W head will point to first "a" (from left)
2. TM will mark first "a" with "X" (custom), and move to right, skipping all "a"s and will stop at first "b"
3. TM will mark "b" with "Y" (custom) and move to left till it finds "X" and then stop at one step ahead at "a"
4. TM will mark first "a" with "X", and move to right, skipping all "a"s and "Y"s and will stop at "b"
5. TM will mark "b" with "Y" and move to left till it finds "X" and then after it there is "Y" that means all "a"s are finished
6. TM will move to right to check whether all "b"s are finished. If R/W reaches "B"(BLANK) that means all "b"s are also finished.That means TM has acceted the language

---

Now we will see how to design State Transition Diagram of Turing Machine for above problem:

1. First we start designing by changing "a" to "X" and move right.
   
   
2. Now when we move right we have to pass all "a"s on the way so we will make a self loop as:
   
   
3. There could be scenario like after two three steps there are some "Y", so we have to pass them also to get to "b"
   
   
4. When we get first "b", make it "Y" and move to left:
   
   
5. When we move to left, we have to pass all the "Y" and "a":
   
   
6. When we reach "X", we will move to right:
   
   
7. And repeat these steps till all the a's are finished, to make sure it we will check whether on moving right we get "Y" and we will continue to pass all the "Y"
   
   
8. If all the b's are finished then we should get a BLANK symbol, TM can move either left or right and we reach final state: