TURNING MACHINE

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

Turing machine can be formally defined as a 7-tuple  M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle  where

  •  Q is a finite, non-empty set of states
  •  \Gamma  is a finite, non-empty set of tape alphabet symbols
  •  b\in \Gamma  is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  •  \Sigma \subseteq \Gamma \setminus \{b\} is the set of input symbols
  •  \delta :(Q\setminus F)\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\} is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows “no shift”, say N, as a third element of the latter set.) If  \delta  is not defined on the current state and the current tape symbol, then the machine halts. 
  •  q_{0}\in Q is the initial state
  •  F\subseteq Q is the set of final or accepting states. The initial tape contents is said to be accepted by  M if it eventually halts in a state from  F.

Anything that operates according to these specifications is a Turing machine.

 

TURNING MACHINES

EXTENSIONS ON TURNING MACHINES:

 

  • Multiple tapes

 

There are several tapes and a head for each tape
The configuration specifies the state, the contents of each tape and the position of the head for each tape.

 

  • Two-way infinite tape

 

The tape is infinite in both directions

 

  • Multiple heads

 

There is one tape with several heads.
The configuration specifies the state, the contents of the tape and the position of each head.

 

  • Two-dimensional tape

 

Two more directions for movement: up and down

All these extensions can be simulated on a standard Turing machine. They do not add to the power of the machine.

Non-Deterministic Turing Machine

In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.

An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.