TM Configuration
 Gist: Instantaneous description of TM
What does a configuration describes?
1) Current state 2) Tape Contents 3) Position of the head
…
Definition: Let M = (Q, S, G, R, s, F) be a TM.
A configuration of M is a string c = xpy, where
x Î G*, p Î Q, y Î G*(G – {D}) È {D}.
a1
p
a2
ai
an
D
…
…
…
a1
p
a2
an
D
…
D
D
D
ai+1
x
y
x
y
1.
2.
Configuration xpy
D
8/45