'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'
Last Updated: Jan 2, 2024
Hard

Turing Machine in TOC

Author GAZAL ARORA
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
turing machine in toc

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

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 −

  1. Q represents a finite set of states
  2. X is a tape alphabet
  3. ∑ is the input alphabet
  4. δ is the transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
  5. q0 is the initial state
  6. B represents the blank symbol
  7. F is the set of final states

 

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

  1. 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:

turing machine

  1. The tape head and the finite control are responsible for reading the current input symbol. The tape head moves from left to right.
  2. It consists of a finite set of states that a machine must pass through.
  3. External symbols are a finite set of symbols used to build the logic of a Turing machine.

input tape

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:

example of turing machine

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. 

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

initial state in turing machine

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:

turing machine example

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:

toc turing machine

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:

turing machine

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.

The Transition Table for the above TM is:

States

a

b

Δ

q0

(q1, A, R)

-

-

q1

-

(q2, B, R)

-

q2

(q3, A, R)

-

-

q3

-

-

(q4, Δ, S)

q4

-

-

-

 

The Transition Diagram for the above TM is:

Transition Diagram

Also read,  Arden's theorem

Frequently Asked Questions

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.

Recommended Readings:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogle, etc. on Coding Ninjas Studio.

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

Previous article
Automata Turing Machine
Next article
Turing Machine in TOC
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass