Turing Machine (TM)

Introduction

• The Turing Machine (TM) was proposed by Alan Turing (1936).

Definition

• A Turing Machine is an abstract machine or theoretical computational model that manipulates symbols on an infinite tape according to a set of rules.
• A Turing Machine is defined in a 7-tuple form:
      M=(Q,Σ,Γ,δ,q₀,B,F)
  where, 
  Q = Finite set of states
  Σ =  Input alphabet (does not include blank symbol)
  Γ(Gamma) =  Tape alphabet (includes Σ and blank symbol B)
  δ(Delta) =  Transition function
  q₀ = Initial (start) state
  B =  Blank symbol
  F =  Set of final (accepting) states
  [ Also, δ(Delta) =  Transition function = Q×Γ→Q×Γ×{L,R} means that 

  Current State + Read Symbol → New State, Write Symbol, Move Direction ]
  

Characteristics

• A Turing Machine defines the limits of algorithmic computation by manipulating symbols on an infinite tape according to a set of rules.
• TM is more powerful than Finite Automata and Pushdown Automata, and it can simulate the logic of any modern computer.
• Any problem that can be solved algorithmically can also be solved by a Turing Machine(=Church–Turing Thesis).

Structure/Components of a Turing Machine

There are the following components of a Turing Machine –

• Infinite Tape
  • This structure is divided into several cells.
  • Each cell holds one symbol from Γ.
  • The tape is of infinite length and on both sides.
• Tape Head
  • This structure reads and writes symbols on the tape.
  • The process is done by moving Left (L) or Right (R).
• Finite Control
  • This structure contains states and transition rules.
  • This structure decides the action based on the current state and symbol.

Types of Turing Machines

• Deterministic Turing Machine (DTM)
  • In this TM, only one move occurs for each state and symbol.
  • It is a standard type of TM.
• Non-Deterministic Turing Machine (NTM)
  • It has multiple possible moves.
  • It is equivalent in power to DTM.
• Multi-Tape Turing Machine
  • It has multiple tapes and heads.
  • It is more efficient, but has the same power as a single-tape TM.
• Universal Turing Machine (UTM)
  • This TM can simulate any other Turing Machine.
  • This is the foundation of stored-program computers.

Working Mechanism of the Turing Machine

Advantages

• TM is the most powerful computational model.
• The TM Model can simulate any computer.

Limitations

• It is only a theoretical model.
• It is not practical to implement physically.
• No Turing Machine can solve the halting problem for all inputs, i.e., some problems are undecidable for a TM.

Use/Applications

• TM is the foundation of computer science.
• TM gives an understanding of the limits of computation.
• The concept of TM is used in Compiler theory.
• The concept of TM is used in Artificial intelligence theory.
• The concept of TM is used in decidability and complexity theory.