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

Automata Turing Machine

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

Introduction

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.

Example

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
Bootcamp

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

Example 

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:

illustration

will move right to - symbol

illustration

Move right up to '-' as:

illustration

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

illustration

Now move towards the left.

illustration

Again move towards the left.

illustration

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

illustration

Now move right till 1

illustration

Convert '1' to * and move towards left

illustration

Convert '1' to '*' and move

illustration

illustration

Move right till Δ is found as follows:

illustration

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:

illustration

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.

Conclusion

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!!!

TOC

Topics covered
1.
Introduction
2.
Turing Machine
3.
Formal Definition
3.1.
Example 
4.
Frequently Asked Questions
4.1.
What is the use of a Turing machine?
4.2.
What do you mean by halting?
5.
Conclusion