Theory of Automata

Turing Machine in Automata



Turing Machine is used to accept Recursive Enumerable Languages (ERL) in Automata.

Elements of Turing Machine

Input Tape:  It has infinite length on which read and writes operation can be performed.

Input Symbols: The input tape consists of infinite cells on which each cell either contains input symbol or a special symbol.  Special symbol is also called blank symbol.

  • Input Symbols (∑) an be in the form of {0,1,a,b, ε, Z0}
  • Special Symbols (B) an be in the form of {&, $,],[, #, etc. }

Head pointer:  it is a read/write head pointer which points to cell currently being read and it can move in both (left and right) directions.

Descriptive diagram of Turing Machine is given below

Turing Machine in Automata

Operation on Input Tape in Turing Machine

The basic operation on Input Tape are explained below



  • Read/scan symbol below the tap Head
  • Update / Write a symbol below the Tap Head
  • Move the Tap Head one step LEFT or RIGHT

Descriptive Diagram is given below

Operation on Input Tape in Turing Machine

Important:

  •  If we are at the left end of the tape, and trying to move LEFT, then do not move. Stay at the left end.
  • If you do not want to update the Cell, Just WRITE the same symbol in that Cell.

Computation Result in Turing Machine

The all possible results after performing all operation on input tape are given below

  • HALT and ACCEPT: It means we reach at accepted state when all operations are done.
  • HALT and REJECT: It means we reach at rejected state when all operations are done.
  • LOOP: it means machine fails to HALT

Note: HALT is also called STOP

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest