Turing Machine in TOC

The Turing Machine is a mathematical computation model that accepts Recursive Enumerable Languages (ERL) in TOC (Theory of Computation). The mathematician and logician Alan Turing invented the Turing machine in 1936. Turing machine is not a physical device but a theoretical model for some computations.

Purpose of Turing Machine

Turing machines, Pushdown Automata (PDA), and Finite State Machines (FSM) are all models of computation. Turing machine is more powerful than PDA and FSM regarding computational power, memory, language recognition, and applications. Let’s explain all of these

1. Computational Power

Let’s compare the Turing machine concerning computational power with PDA and FSM.

  • The Turing Machine is the most powerful and can recognize any algorithmic process.
  • Pushdown Automata is less powerful than Turing machines because it recognizes context-free languages, which are a subset of the languages recognized by Turing machines.
  • Finite State Machine is the lowest in power. It recognizes regular languages, which are a subset of context-free languages.

2. Memory

Let’s compare the Turing machine concerning memory with PDA and FSM.

  • Turing Machine uses infinite input tape for its memory, allowing it to store unlimited information.
  • Pushdown Automaton uses a stack for its memory.
  • A Finite State Machine has a limited internal state and no explicit external memory like a Stack or input tap, so it is the least powerful in terms of memory.

3. Language Recognition

Let’s compare the Turing machine concerning language recognition with PDA and FSM.

  • Turing Machine recognizes recursively enumerable languages (REL), including all regular, context-free, and recursively enumerable languages.
  • Pushdown Automaton recognizes context-free languages that include regular languages.
  • Finite State Machine recognizes only regular languages.

4. Applications

Let’s compare the Turing machine’s applications with PDA and FSM.

  • Turing Machine is mainly used in theoretical computer science to define algorithm processes.
  • Pushdown Automaton is used to parse context-free grammars and make them relevant for analyzing programming languages and syntax.
  • Designers commonly use finite-state machines to design and model simple systems, such as control circuits.

Elements of Turing Machine

The turning machine has the essential elements given below.

Input Tape: It has an infinite length for performing read and write operations.

Input Symbols: The input tape consists of infinite cells, each containing either an input or a special symbol. A special symbol is also called a blank symbol in an automata, the Turing machine.

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

Head pointer: A read/write head pointer that points to the cell being read/write and can move in both (left and right) directions.

Following is a descriptive diagram of the Turing Machine.

Turing Machine in Automata

Operation on Input Tape in Turing Machine

Let’s explain the basic operations over Input Tape.

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

Let’s see the descriptive diagram 

Operation on Input Tape in Turing Machine

Important:

  •  If we are at the start of input tape and trying to move LEFT, then do not move.
  • If you do not want to update the cell of the input tape with any symbol, then WRITE the same symbol in that cell.

Computation Result in Turing Machine

Following are all possible results after performing all operations on input tape. 

  • HALT and ACCEPT: We reach an accepted state when we have done all operations.
  • HALT and REJECT:  We get a rejected state after doing all operations.
  • LOOP: it means the machine fails to HALT or reject

Note: HALT is also called STOP