Modifications OF Turing Machines

MODIFICATIONS
OF
TURING MACHINES
The capability of turing machines is extended using the following methods.

Two way infinite tape

Multitape turing machine

Non deterministic turing machine

Multidimensional turing machine

Multihead turing machine

Off-line turing machine
Two way infinite tape:
A turing machine, M = (Q,∑, Г,δ,q0, B, F) is said to be a two-way infinite tape TM if
the input tape is infinite to the left and right.It can be viewed as a finite sequence of
input symbols with infinite sequence of blank symbols to the left and right of the
input.As with the standard TM, there is a fixed left end, the two - way infinite tape TM
has no left end. Hence it can move as far as possible towards left as well as right.This is
no “fall off” of TM towards left I.e there is no possiblity of jumping off theleft end of
the tape
Multi-tape Turing machine :
A multitape TM is finite control with more than one tape for reading/writing symbols,
storing states etc.Each tape has ‘n’ number of individual cells.The first tape is mostly
used to store the
input symbols of the string, ω.
The second and third tapes are normally used to store the states and state-
changes.Movement of
one tape head does not affect or depend on the movement of another tape.
the structure of multitape TM is shown below,

The components required to formally define a multitape turing machine is
M = (Q,∑, Г,δ,q0, B, F) where δ is defined as


δ = Q * Гk ----> Q * Гk * {L,R,N}k where k is the number of tapes.
The transition rules of a two tape TM is given as,
δ (q, a1, a2) = (q`, H1(b), M1), H2(b), M2)
where,

q is the current state to be processed

q` is the next state to be reached

a1 is the symbol read by tape 1

a2 is the symbol read by tape 2
H1(b) is the symbol to be written by tape 1
H2(b) is the symbol to be written by tape 2
M1 is the Movement by tape 1 (R / L / N)
M2 is the Movement by tape 2 (R / L / N)
Each move in a multitape TM depends on the current state and the symbol
scanned by the tape heads.Thus, on each move,
State change, Replace new symbols on each cells being processed on the
tapes. And Tape heads take right/left movement or remain unchanged.
Non deterministic turing machine:
Non determinism is a powerful feature of Turing machine with finite control and single
one way infinite tape.These NTM machines are easy to design and are equivalent to
deterministic TM.For a given state and a tape symbol the machine has the finite
number of choices for the next move.Each choice consist of a new state , tape symbol
and the direction of head motions.A NTM accepts a string, ω if there exists a least one
sequence of moves from the initial state to final state.
A NTM is defined as ,
M = (Q,∑, Г,δ,q0, B, F)
Where
Q is the Set of states including initial, having rejecting states.
∑ is the Finite set of input alphabets
Г is the Finite set of tape symbols
δ is the Transition function defined by
δ = Q * Г ----> P(Q * Г*{L, R, N}) where P is the power set
q0 is the initial state
B is the blank symbol and F is the set of final states,(F ≤ Q)
The transition function δ takes on the states tape symbols and head movement.
That is
TM = δ(q,s) = (qi,Si,Mi) for i = 1
NTM = δ(q,s) = (qi,Si,Mi) for i = 1,2…
The below transition takes on two paths for the same input, a The transition of „a‟ at q0
is defined as, δ (q0, a) = {(q0, a, R), (q1, x, R)}
Multidimensional turing machine:
Multidimensional turing machine has the usual finite control,but tape consist of k
dimensional array of the cells infinite and all 2k directions( for some fixed k).
Depending on the state and the symbol scanned the machine
Change states
Write a new symbol
Moves its head in one of the directions ( either positively or negatively ) along one of
the k axes.
Initially the input is along one axis and the head is at the left end of the input .
Two dimensional tape :
The above diagram shows the two dimensional tape having
boundaries on the left and bottom.each cell is given address by
(x,y) where
x- row number of the cell
y- coloumn number of the cell
Simulation of 2D by one:
Consider the tape configuration of the 2D shown in the diagram.
One dimensional simulation:
* * * B B B a1 B B B * B B a2 a3 a4 a5 B * a6 a7 a8 a9 B a10 B * B a11 a12 a13 B a14 a15 *

B 13 13 a16 17 B B B * * * ( * seperate from rows )
A second track may be used to indicate the position of 2D Turing machine tape head
Multi head turing machine:
A turing machine with several heads on it is said to be multihead turing machine.A k

head turing machine has some fixed number k of heads the heads are numbered 1
through k .A move of turing machine depends on the state and on the symbol scanned
by each head .In one move each head can move independently to L ,R or no move
Use of multihead turing machine can simplify the construction of the complex turing
machine drastically.
Offline turing machine:
An offline turing machine is the multitape turing machine whose input tape is read only
. The input is end marked by the ₵ on the left and $ on the right .The turing machine is
not allowed to move the input tape head of the region between ₵ and $.
Special case of multitape turing machine
Simulation of offset turing machine.
An offline turing machine can simulate any turing machine. By the using more tape
than M .The first thing is the offline turing machine does is copy its input onto extra
tape. And it then simulates M as if the extra tapes were M’s input.

Modifications OF Turing Machines

Uploaded by

Copyright:

Available Formats

Modifications OF Turing Machines

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Modifications OF Turing Machines

Uploaded by

Copyright:

Available Formats

MODIFICATIONS

the structure of multitape TM is shown below,

M = (Q,∑, Г,δ,q0, B, F) where δ is defined as

* * * B B B a1 B B B * B B a2 a3 a4 a5 B * a6 a7 a8 a9 B a10 B * B a11 a12 a13 B a14 a15 *

A turing machine with several heads on it is said to be multihead turing machine.A k

You might also like