'Coding has over 700 languages', '67% of programming jobs arenâ€™t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Turing machines are simple abstract computational devices first described by Alan Turing in 1936â€“7. They are intended to help investigate the extent and limitations of what may be calculated. In this blog, we will learn about the Turing Machine in TOC. Let's start with the definition of Turning Machine.

What is Turing Machine in TOC?

In theoretical computer science, a Turing machine is a hypothetical computing machine that can read, write, and erase symbols on a tape-based on a set of rules. It serves as a model for understanding the limits of computation and the concept of algorithmic computation. In simpler terms, it is a machine that can perform a series of tasks based on specific rules and input data.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Basic Model of Turing machine

A Turing machine(TM) is a computer model that reads and writes to an infinite tape to perform computations. The tape is divided into cells into which input is given. It contains a reading head that reads the input tape.

A state register is used to store the state of the Turing machine. The cell in the tape is replaced with another symbol, its internal state is changed, and it travels from one cell to the right or left after reading an input symbol.

The input string is accepted if the TM reaches the end state; else, it is denied.

Formal definition of Turing machine

A TM is defined as a 7-tuple (Q, X, âˆ‘, Î´, q0, B, F) where âˆ’

Q represents a finite set of states

X is a tape alphabet

âˆ‘ is the input alphabet

Î´ is the transition function; Î´ : Q Ã— X â†’ Q Ã— X Ã— {Left_shift, Right_shift}.

q0 is the initial state

B represents the blank symbol

F is the set of final states

The following representation can be used to model the turning machine.

The input tape has an infinite number of cells, each containing one input symbol, allowing the input string to be taped. The empty tape is filled with blank characters as shown below:

The tape head and the finite control are responsible for reading the current input symbol. The tape head moves from left to right.

It consists of a finite set of states that a machine must pass through.

External symbols are a finite set of symbols used to build the logic of a Turing machine.

Language accepted by Turing machine

All languages, even if they are recursively enumerable, the Turing machine accepts them all. The terms recursive enumerable refer to the same set of rules being repeated an infinite number of times. Computable functions, such as addition, multiplication, subtraction, division, power function, and many others, are accepted by the TM.

Example

Q: Construct a Turing machine that accepts the language of aba over âˆ‘ = {a, b}.

Solution:

We'll assume the string 'aba' is placed on the input tape as follows:

IMAGE

The tape head will read out the sequence up to the Î” characters. Now, we'll see how this Turing machine works for the string 'aba.'

We'll see how this Turing machine works for the string 'aba' now.

The initial state is q0, and the head points to an as follows:

2. The move will be Î´(q0, a) = Î´(q1, A, R), implying that it will proceed to state q1, with a replaced by A and the head moving to the right as follows:

3. The move will be Î´(q1, b) = Î´(q2, B, R), implying that it will proceed to state q2, with b replaced by B and the head moving to the right as follows:

4. The move will be Î´(q2, a) = Î´(q3, A, R), meaning it will proceed to state q3, replace a with A, and move the head to the right as follows:

5. The move Î´(q3, Î”) = (q4, Î”, S) indicates that it will go to state q4, the HALT state, which is always an accepted state for any TM.

What are the three main components of a Turing machine?

A Turing machine consists of three main parts:

1)Tape: A long tape for storing symbols. 2)Head: A device that reads and writes symbols on the tape.3)State Register: A control unit guiding the machine's actions based on symbols and its internal state.

Does the Turing machine accept recursively enumerable languages?

Yes, The Turing machine accepts all the languages even if they are recursively enumerable.

What are the applications of Turing machine?

Turing machines are used to model and analyze algorithms and computation and serve as the basis for the design of modern computers. They also have applications in artificial intelligence, cryptography, and complexity theory.

What are the advantages of Turing machine in TOC?

The are many advantages to Turing Machines in TOC. The main advantage among them is that Turing Machines can read any language and compute the model functions for which the algorithm is possible.

Conclusion

In this article, we learned about the Turing Machine in TOC.

We learned that a Turing Machine (TM) is a mathematical model consisting of an infinitely long tape separated into cells into which input is delivered. It has a reading head that reads the input tape. A state register is used to store the state of the Turing machine.

A Turing machine accepts all languages, even if they are recursively enumerable.