Information Technology Reference
In-Depth Information
Ta b l e 6 . 1 3
A Turing machine performing the sum of numbers in unary notation
q
0
,
1
,
1
,
q
0
,
R
q
0
,
B
,
1
,
q
1
,
R
q
1
,
1
,
1
,
q
1
,
R
q
1
,
B
,
B
,
q
2
,
L
q
2
,
1
,
B
,
q
3
,
L
q
3
,
1
,
B
,
q
4
,
L
A Turing machine can be used as a computing device providing an input/output
behavior, but it can be also used as a recognizing device when given an input it
starts a computation and ends in some chosen states (a class o final states has to be
defined). A Turing machine can be also viewed as generating the language of all the
strings obtained as outputs in correspondence of all possible inputs strings.
We remark that, in principle, computing functions or recognizing and generating
languages are equivalent tasks. In fact, a function
f
:
A
→
B
is univocally identified
by its graphic, that is, the set
. Therefore, generating or
recognizing the graphic of
f
is equivalent to computing
f
and vice versa.
It can be shown that the class of languages recognized by Turing machines is
equal to the class of languages generated by Turing machines, and that the languages
recognized/generated by nondeterministic Turing machines are equal to the class of
languages recognized/generated by deterministic Turing machines. This class coin-
cides with the class generated by Chomsky grammars of type 0.
{
(
x
,
f
(
x
))
∈
A
×
B
|
x
∈
A
}
Ta b l e 6 . 1 4
A non-terminating Turing machine on
{
0
,
1
}
q
0
,
1
,
1
,
q
0
,
R
q
0
,
0
,
0
,
q
0
,
R
q
0
,
B
,
B
,
q
0
,
R
The Turing machine given in Table 6.14 describes a computation that does not
ends. The Turing machine given in Table 6.15 recognizes the bi-somatic language
(stops in the state
q
yes
when the input is a bi-somatic string, while stops in the state
q
no
otherwise). It is easy to generalize the same strategy for recognizing the tri-
somatic language.
We remark that what makes Turing machines more powerful than finite state
automata is the possibility of movement in the two directions of the tape and the
possibility of reading and writing on it.
