Define Turing Machine and explain its different variations.

This answer is restricted. Please login to view the answer of this question.

Login Now

A Turing Matchine can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −

  • Q is a finite set of states
  • X is the tape alphabet
  •  is the input alphabet
  • δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
  • q0 is the initial state
  • B is the blank symbol
  • F is the set of final states

Turing machines (TM) can also be deterministic or non-deterministic, but this does not make them any more or less powerful. However, if the tape is restricted so that you can only see the use of the part of the tape with the input, the TM becomes less powerful (linear bounded automata) and can only recognize context-sensitive languages.

1. Multiple-track Turing Machine:

  • A k-track Turing machine(for some k>0) has k-tracks and one R/W head that reads and writes all of them one by one.
  • A k-track Turing Machine can be simulated by a single-track Turing machine

2. Two-way infinite Tape Turing Machine:

  • Infinite tape of two-way infinite tape Turing machine is unbounded in both directions left and right.
  • A two-way infinite tape Turing machine can be simulated by a one-way infinite Turing machine(standard Turing machine).

3. Multi-tape Turing Machine:

  • It has multiple tapes and is controlled by a single head.
  • The Multi-tape Turing machine is different from the k-track Turing machine but expressive power is the same.
  • Multi-tape Turing machine can be simulated by a single-tape Turing machine.

4. Multi-tape Multi-head Turing Machine:

  • The multi-tape Turing machine has multiple tapes and multiple heads
  • Each tape is controlled by a separate head
  • A multi-Tape Multi-head Turing machine can be simulated by a standard Turing machine.

5. Multi-dimensional Tape Turing Machine:

  • It has multi-dimensional tape where the head can move in any direction that is left, right, up or down.
  • Multi-dimensional tape Turing machine can be simulated by a one-dimensional Turing machine

6. Multi-head Turing Machine:

  • A multi-head Turing machine contains two or more heads to read the symbols on the same tape.
  • In one step all the heads since the scanned symbols and move or write independently.
  • Multi-head Turing machines can be simulated by a single-head Turing machine.

7. Non-deterministic Turing Machine:

  • A non-deterministic Turing machine has a single, one-way infinite tape.
  • A given state and input symbol has at least one choice to move (a finite number of choices for the next move), and each choice has several choices of the path that it might follow for a given input string.
  • A non-deterministic Turing machine is equivalent to a deterministic Turing machine.
If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

  Loading . . .