Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: Mar 27, 2024

Automata Turing Machine

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Theory of Computation


Theory of computation(TOC) is the branch of computer science that deals with problems that can be solved using abstract or straightforward machines called Automata.

The theory of computation field is divided into three concepts, which are as follows −

  • Automated theory and language.
  • Computability theory.
  • Complexity theory.

We will be heading towards the details of the Turing Machine and how it is used for grammar or languages.

Read About - Moore Machine

Turing Machine

A Turing machine is an accepting device used to accept recursive Enumerable Language generated by type 0 grammar.

First of all, what do you mean by type 0 grammar?
Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phrase structure grammar, including all formal grammar.


S → ACaB 

Bc → acB 

CB → DB 

aD → Db

Turing Machine was invented by a mathematician, and scientist named Alang Turing. It consists of a tape of infinite length on which read and write operations can be performed. The tape includes unlimited cells on which each cell either contains an input symbol or a special symbol called a blank. It also consists of a head pointer that points to the cell currently being read, and it can move in both directions, just as shown in the picture below.

Turing Machine

Let's throw some light on the various features of this machine.

  1. It has an infinite amount of memory capability.
  2. The model has a facility where the input at the left or right side of the tape can be read easily.
  3. The machine tape has an unlimited length.
  4. The machine tape has an unlimited length.
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

Formal Definition

A Turing machine can be bounded as a collection of 7 tuples:

Q= finite set of states

∑= finite set of input symbols

T= tape symbol

q0= the initial state

F= a set of final states

B= a blank symbol used as an end marker for input

δ= a transition or mapping function.

Let's construct a Turing machine for some Language L.

Also read,  Arden's theorem


TM for subtracting two unary numbers f(a-b) = c where a is always greater than b.

For subtraction, the first number is greater than the second number. Let us assume that a = 3, b = 2, so the input will be:


will move right to - symbol


Move right up to '-' as:


Move right and convert '1' to '*' as follows:


Now move towards the left.


Again move towards the left.


Convert '1' to '*' and move towards the right-hand side


Now move right till 1


Convert '1' to * and move towards left


Convert '1' to '*' and move



Move right till Δ is found as follows:


Now we are in the 'HALT state' (computation is ended).

Thus we get '1' on the input tape as the answer for f(3-2), where a=3 and b=2.

The Turing machine will look like this:


Also see, Turing Machine in TOC.

Frequently Asked Questions

What is the use of a Turing machine?

The Turing machine is the most powerful computation model that reads and writes to an infinite tape.

What do you mean by halting?

The halting is a decision problem about the properties of computer programs on a fixed Turing model of computation, i.e., all programs written in some specified programming language that is enough to be equivalent to a Turing machine.


This article has covered the topic of Turing machines with examples in detail to clear your thoughts about this topic.

For more information regarding the Turing machine, you can visit here.
Also, for details regarding the theory of computation, you can look here.

Recommended Readings:

You can also consider our Online Coding Courses such as the Machine Learning Course to give your career an edge over others.

Happy Learning!!!


Topics covered
Turing Machine
Formal Definition
Frequently Asked Questions
What is the use of a Turing machine?
What do you mean by halting?