Brief about Turing Machine in TOC

In 1936, Alan Turing has developed a hypothetical automaton(machine) that can simulate any algorithm which can be implemented on computers, that hypothetical automata is populated as Turing Machine.

Compared to other hypothetical automata like FA or PDA, the turing machine has neither limit on its memory nor any restriction to perform any operation.  That's why this machine produces a much more accurate model of a general-purpose computer.

Mechanism and a hypothetical component of Turing Machine:

The Turing machine model uses an infinite tape (known as Turing tape) having unlimited memory. That tape has a head called a tape-head to read & write symbols and move around on the tape in any direction. With this observation, he proposed his Computing Machine called a Turing machine.

Turing tape is divided into n number of cells. As you see in the diagram.

Each cell contains only one symbol and the tape head reads that symbol at a time.

To read the information that it has written, the machine can move its head over it.

Movement is continued till the result is not obtained. The result will be in form of whether the string is accepted or rejected. If it doesn’t accept or reject then it will be considered the machine is in a never halting state.

Turing model can be defined as

A Turing machine M is a 7 Tuple, namely (Q,Σ, Γ, δ, q_acc , q₀ , q_rej)

·         Q is a finite and nonempty set of states

·         Σ is an alphabet called the input alphabet, which may not include the blank symbol,

·         Γ is an alphabet called the tape alphabet, which must satisfy Σ ∪ { } ⊆ Γ

·         δ is a transition function having the form δ : Q\{ q_acc , q_rej } × Γ → Q × Γ × {←, →}

·         q₀ ∈ Q is the initial state              

·         q_acc, q_rej ∈ Q are the accept and reject states, which must satisfy q_acc ≠ q_rej.

We can observe the transition function as, Suppose the deterministic TM is currently in a state p ∈ Q, the symbol stored in the tape cell being scanned by the tape head is a ∈ Γ, and it is the case that

δ(p, a) = (q, b, D)

for D ∈ {←, →}. The action performed by the DTM is then to

1. change state to q,

2. overwrite the contents of the tape square being scanned by the tape head with b,

3. move the tape head in direction D (either left or right)

In the case that the state is q_acc or q_rej, the transition function does not specify an action, because we assume that the DTM halts once it reaches one of these two states.

Before we study further, let's first summarize the differences between finite automata and Turing machines.

1. Turing machine has the capability to read and write on the provided tape.

2. Direction to move the head to left or right is not bounded.

3. The length of the tape is infinite.

4. The special states for rejecting and accepting take effect immediately.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.