## 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.

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

- It has an infinite amount of memory capability.
- The model has a facility where the input at the left or right side of the tape can be read easily.
- The machine tape has an unlimited length.
- The machine tape has an unlimited length.