O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8

Turing Machine

Introduction

Around 1936, when there were no computers, Alen Turing proposed a model of an abstract machine called the Turing machine which could perform any computational process carried out by the present day’s computer. The machine was named after Turing, and it is called the Turing machine. The Turing machine is the machine format of unrestricted language, i.e., all types of languages are accepted by the Turing machine.

Based on the Turing machine, a new theory called the ‘theory of undecidable problems’ is developed. These types of problems cannot be solved by any computer.

8.1  Basics of Turing Machine

The Turing machine, in short TM, is defined by 7 touples

 

(Q, Σ, Γ, δ, q0, B, F)

 

where

    Q : Finite set of states ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required