Turing Machine Basics In Theory Of Automata

By Prof. Fazal Rehman Shamil
Last modified on January 25th, 2021

Turing Machine Basics:

The Turing machine is an invention of a mathematician Alan Turing. 

Turing machine is a very powerful machine. Any computer problem can be solved through Turing Machine.

Just like FA, Turing machine also has some states and some transition. Starting and ending states are also the part of Turing Machine.

Every transition on the states have 3 parts;

  1. Read
  2. Write
  3. Move

Read:

By read operation, machine can read any alphabet from the input tape; e.g, a,b,c,….x,y,z, 0,1 etc.

Write:

By Write operation, machine can write any alphabet; e.g, a,b,c,….x,y,z, 0,1 etc.

Move:

The move represents direction. Move tells where to move on input tape. e.g, if we say that move right, then it means that we need to move from one cell to the right cell on the input tape.

There are two types of the move;

Move left

Move right

 

how to turing machine
Figure: Turing Machine Basics

Explanation of diagram:

There is in one little part of a Turing machine in the last figure. Let’s explain it;

Start state: 

To start the machine

a,a,R:

Read a from input tape, Write a and then move one cell right on input tape.

b,b,R: 

Read b from input tape, Write b, and then move one cell right on input tape.

Accept:

Machine successfully accept the string and Halts(Finish/complete).

Turing Machine Comparison with Regular Expression , CFG, PDA and Deterministic Finite Automata
Turing Machine Comparison with Regular Expression , CFG, PDA and Deterministic Finite Automata

 

Read More Examples of Turing Machine

  1. Turing Machine to copy a string: with animations
  2. Turing Machine of numbers divisible by 3: with animations
  3. Turing machine for anbncn: with animations
  4. Turing machine of two equal binary strings: with animations

  5. Turing Machine to Accepts palindromes: with animations

  6. Turing machine for a’s followed by b’s then c’s where the number of a’s multiplied by the number of b’s and equals to the number of c’s: with animations

  7. Turing machine to Add two binary numbers: with animations

  8. Turing machine to  Multiply two unary numbers: with animations
  9. Turing machine to Multiply two binary numbers: with animations
  10. Turing Machine for the complement of a string
  11. Turing Machine for the language of anbn where a=b.
  12. Turing Machine for a is less than b, ambn where a=b or m=n.
  13. Turing machine for the language of all those string in which a is less than b

     

Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.