2) Discuss the variants of Turing machines Or Explain about types of

Turing Machine?

A) Here we discuss the following concepts

Introduction

1) What is a standard Turing machine? (

1. Whose tape is extensible
to the left or right?

2. Machine is supplied with

enough tape
)
A) A Turing Machine is said to be a Standard TM if its tape is assumed
to be arbitrarily extensible to the left as well as to the right and the
machine is supplied with enough tape required for computation.

2) A Turing Machine with no boundary on the right side of the

tape?
(left most cell is provided
for current computation, no
boundary on the right side of the
tape)
A) It is a machine in which leftmost cell is provided for the current
computation, but there is no boundary on the right side of the tape.

3) Diagram with boundary on the left side

1
4) What is a two way infinite tape TM? (Infinite number of
sequences of blanks on either
side of the Turing machine

A) A two way infinite tape TM is one in which there are infinite number
of sequences of blanks on either side of the tape

5) What is the advantage of having this type of TM ? (there is no

possibility off the left end of the tape)
A) The advantage of having this type of TM is that there is no possibility
off the left end of the tape

6) Diagram

7) Example for Initial Configuration of TM? (For input string 101)

A) The initial configuration of the tape for the input string 101, with
respect to a standard TM and two-way infinite tape TM as shown above.

2
8) What is a Multi-Tape Turing Machine? (
1) With more than one tape
2) Each tape is having independent
Head)
A) A Multi Tape Turing Machine is one with more than one tape and
each tape is having its own independent head.

9) What is the initial configuration of Multi tape Turing Machine? (

1) Input appears on tape 1 and
the others start out blank )

A) Initially, the input appears on tape 1 and the others start out blank.

10) What about the transition function? ( is changed to allow for

1.reading , writing and moving
the heads on all the tapes
simultaneously.)

A) The transition function is changed to allow for reading, writing and

moving the heads on all the tapes simultaneously.

11) Example

3
12) Diagrams

4
12) What are advantages of Multitape TM? (
Useful in design of functions like
5
 1) Copying
2) Reversing
3) Checking a palindrome or not)

A) With the help of multi tape Turing machine we can design some
functions like copying , reversing , verifying whether a string is a
palindrome or not etc. can be carried out in much easier way as
compared to the design of the corresponding standard TMs.

13) Is a MultiTape TM is equivalent to a single tape TM?

A) yes

14) What is a Multi Head Turing Machine? (With one tape and
several
heads)

A) A TM with one tape and several heads on it is said to be a multi-head

Turing Machine.
15) Diagram

6
A)

16) How many heads we can have in a multi head TM? ( k heads
where
k>=2)

A) In a Multi-Head TM we can have K heads where K>=2 and the heads

are numbered from 1 through k.

17) How a move can be made by a multi head TM? ( by depending on

1) On the state
2) On the symbol scanned
by each head)
A) A move of the Multi head TM depends on the state and on the
symbol scanned by each head.

18) What type of moves a Multi Head TM can make? (left or right or
stationary)
A) In one move, each head can move independently to left or right or
remain stationary.

19) What is the advantage of using a MultiHead TM? ( simplifies the

construction of Complex TM’s )

7
A) The use of multi-heads like multi tapes can sometimes simplify the
construction of complex TM’s drastically.

20) What is a K-Dimensional TM?(with its tape as an infinite k-

dimensional grid , k dimensional
array of cells , infinite in all 2-k
directions )

A) It is a TM having its tape with an infinite k-dimensional grid , is said

to be k-dimensional array of cells infinite in all 2-k directions , for some
fixed k.

21) How this machine changes its state? ( depending on present state
Depending on symbol
Scanned)
A) Depending on the state and symbol scanned, the machine changes its
states, write a new symbol and moves its tape-head in one of the 2-k
directions either positively or negatively along one of the k-axes.

22) Diagram

8
23) What the above diagram shows? ( having boundaries on the left
and bottom of the tape)

A) The above diagram shows a two-dimensional tape , having

boundaries on the left and the bottom.

24) How each cell can be addressed ? ( (x, y) , where x is row number
y is column number)

A) The above diagram shows a two dimensional tape, having boundaries

on the left and the bottom. Each cell is given an address (x, y) where x is
the number of the cell and y is the column number of the cell.

25) What is the advantage of K-dimensional TM’s? (

1) Solving Sophisticated problems
2) They can be combined with other
extensions of TM

A) The K-dimensional TM’s are much more useful than standard TM’s
for solving sophisticated problems. This type of TM can also be
combined with other extensions of TM

26) What is an off line TM? ( 1) it is a multi-tape TM

2) input tape is of type read only)

A) An off line TM is a multi-tape TM, whose input tape is of type read

only

27) How the input is end marked? ( by Ø on the left

By $ on right )
A) The input is end marked by Ø on the left and by $ on the right.

9
28) How the movement of off line TM will look like? (
it is not allowed to move the input tape head
other the region between Ø and $)
A)The TM is not allowed to move the input tape head, off the region
between Ø and $

29) What is the advantage of off line TM? ( it can simulate any TM by
using one or more tape)
It is useful in the case of
limiting the amount of
storage space )

A) An off line TM can simulate any TM , T by using one or more tape, it

is useful in the case of limiting the amount of storage space, which is
less the input length.

30) What is a Deterministic TM ? (

with current state (q) and the symbol
(s) the TM perform the unique action )

A)A Deterministic TM is one in which for the current state (q) and the
symbol (s) being scanned by the tape head, the TM performs the unique
action in terms of writing a symbol in the cell being scanned and also
repositioning the head to left or right or no move at all.

31) Diagram of Deterministic TM ?

A)

10
32) What is a Non Deterministic TM? (
for the current state (q) and symbol (s)
the TM has finite set of choices for
writing a symbol in the cell being
scanned and repositioning the head to
left or right or no move )

A) In a non-deterministic TM, for the current state (q) and symbol (s)
being scanned by the tape head , the TM has finite set of choices for
writing a symbol in the cell being scanned and repositioning the head to
left or right or no move (M).

33) How a Non Deterministic TM can be mathematically

represented?( 7-tuple notation )

A) A Non Deterministic TM can be mathematically represented by a 7-

tuple notation as given below.

11
12