TM Configuration
Gist:
Instan
taneous
description of
TM
What does a configuration describes?
1)
C
urrent 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
}.
a
1
p
a
2
a
i
a
n
D
…
…
…
a
1
p
a
2
a
n
D
…
D
D
D
a
i
+1
x
y
x
y
1.
2.
Configuration
x
p
y
D
8
/45