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
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
Important:
|
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