Variations of Turing machine: The variants of Turing machine are:

1. Turing machines with two-way infinite tapes

   • A two way infinite tape Turing machine is a Turing machine with its input tape infinite in both directions, the other components being the same as that of the basic model.

   • That a one-way TM $M_0$ can be simulated by a two-way TM. $M_{D}can$ be seen easily. $M_{D}Puts$ a ≠ to the left of the leftmost nonblank and moves its head right and simulates $M_0$. If $M_{D}reads$ ≠ again, it halts rejecting the input as its means $M_{0}$ tries to move off the left end of the tape.

1. Multi-tape Turing machine

A multi-tape TM can be simulated by a single by a single tape TM.

1. Multi-head Turing machines

   • A multi-head TM is a single tape TM having k heads reading symbols on the same tape.

   • In one step all the heads sense the scanned symbols and move or write independently.

1. Non-deterministic Turing machines

Every NTM can be simulated by a deterministic TM.

1. Turing machines with two-dimensional tapes

   • The Turing machine can have two dimensional tapes. When the head is scanning a symbol, it can move left, right, up or down.

   • The smallest rectangle containing the non-blank portion is m x n then it has m rows and n columns.

   • A one dimensional TM which tries to simulate this two dimensional TM will have 2 tapes. On one tape these m rows of n symbols of n symbols each will be represented by m block of size n each separated by markers. The second tape is used as scratch tape.

   • When the two dimensional TM’s head moves left or right, it is simulated in a block of the one dimensional TM.

   • When the two dimensional TM’s head moves up or down, the one dimensional TM’s head moves to the previous block or the next block. To move to the correct position in that blocks or the size of the blocks is increased.