Cryptography Reference
In-Depth Information
3. print the output character of
on the pointed cell,
4. move the tape head by one position according to the output of
δ
δ
(if it points on
the leftmost cell, it cannot move to the left).
We say that the Turing machine halts if it happens to enter into a final state. We can
define the language accepted by a Turing machine as for finite automata: accepted
words are inputs for which the Turing machine halts. Languages which are accepted by
one Turing machine are called
recursively enumerable languages
. Note that for words
that are not accepted, the Turing machine is not assumed to halt. We can only guarantee
that for input words which are accepted, the machine will eventually halt.
As an example we show how to accept the set
A
of all 0
i
1
i
, which is not a regular
language. We first describe how the Turing machine works at a high level. Here are the
different states of the Turing machine.
q
0
: if the pointed cell is blank, terminate (i.e. accept) if the pointed cell is 1, enter
into an endless loop (i.e. reject) otherwise replace the pointed cell by a blank
character, move right, and change the state to
q
1
(we have erased the first 0, looking for a 1)
q
1
: repeatedly move right until the pointed cell is not 0 if the pointed cell is blank,
enter into an endless loop (i.e. reject) otherwise move right and change the
state to
q
2
(we have found the first 1, looking for the last one)
q
2
: repeatedly move right until the pointed cell is not 1 if the pointed cell is 0, enter
into an endless loop (i.e. reject) otherwise move left and change the state to
q
3
(we have gone beyond the last 1, we move back)
q
3
: replace the pointed 1 by a blank, move left, and change the state to
q
4
(we have erased the last 1, we move back)
q
4
: repeatedly move left until the pointed cell is blank
(we are moving toward the first nonblank character) move right and change
the state to
q
0
It is then easy to define the Turing machine. We have
Q
={
q
0
,
q
1
,
q
2
,
q
3
,
q
4
,
q
F
,
q
L
}
={
q
F
}
and
F
, where
q
L
is a special state which enters into an endless loop. We
δ
,
∈
∈{
,
,
}
have to define
(
q
a
) for each
q
Q
and each
a
0
1
B
. This consists of a triplet
in
Q
×{
0
,
1
,
B
}×{
left
,
right
}
. Here is how
δ
is defined. (Places with the - character
are not used, so we do not define them.)
q
δ
(
q
,
B
)
δ
(
q
,
0)
δ
(
q
,
1)
q
0
q
F
-
-
q
1
B
right
q
L
-
-
q
1
q
L
-
-
q
1
0
right
q
2
1
right
q
2
q
3
B
left
q
L
-
-
q
2
1
right
q
3
-
-
-
-
-
-
q
4
B
left
q
4
q
0
B
right
q
4
0
left
q
4
1
left
q
F
q
F
-
-
q
F
-
-
q
F
-
-
q
L
q
L
-
-
q
L
-
-
q
L
-
-
Search WWH ::
Custom Search