Variarst of Turning Machine

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: May2015


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.

enter image description here
enter image description here

  1. Multi-tape Turing machine

enter image description here

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

enter image description here

  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.

enter image description here

  1. Non-deterministic Turing machines

Every NTM can be simulated by a deterministic TM.

enter image description here

  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.

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more