Information Technology Reference
In-Depth Information
Ta b l e 6 . 1 5
A Turing machine on
{
a
,
b
}
recognizing the bi-somatic language
q
0
,
a
,
B
,
q
1
,
R
q
1
,
a
,
a
,
q
1
,
R
q
1
,
b
,
b
,
q
2
,
R
q
2
,
b
,
b
,
q
2
,
R
q
2
,
B
,
B
,
q
3
,
L
q
3
,
b
,
B
,
q
4
,
L
q
4
,
a
,
a
,
q
4
,
L
q
4
,
b
,
b
,
q
4
,
L
q
4
,
R
q
0
,
B
,
B
,
q
yes
,
R
q
0
,
b
,
b
,
q
no
,
R
q
2
,
a
,
a
,
q
no
,
R
B
,
B
,
q
0
,
6.6
Decidability and Undecidability
The original Turing's paper of 1936 presents a basilar result of the theory of com-
putation: the undecidability of the general halting problem for Turing machines. As
a consequence of it, it is possible to deduce the existence of
recursive enumerable
sets which are not
decidable
. Namely, no Turing machine exists which can, in gen-
eral, establish wether a given Turing machine stops yielding a result in correspon-
dence to a given input. Therefore, we can collect in a set all the outputs provided
by a Turing machine, but there is no way to know whether a given Turing machine
(encoded by its program, which is a string) halts on not. Of course, if it halts, we
know it, but if it does not halt, we cannot exclude that a halting configuration will
be reached in the future. This means that, in general, we can decide positively the
termination if it occurs, but we cannot decide negatively when it does not occur.
A recursively enumerable language is also called
semi-decidable
. In fact we can
always correctly say yes, when a string belongs to it, but we cannot, in general, say
no when a string does not belong to it. In other words, membership can be asserted
in a finite amount of time, but non-membership cannot, in general, definitively as-
certained in a finite amount of time.
A semi-decidable language can be generated as outputs of a Turing machine,
in correspondence to all input strings over its alphabet. It is easy to show that a
language can be generated by a Turing machine iff it is also recognized by some
Turing machine. The class
RE
coincides with the class of semi-decidable languages,
while the class
REC
coincides with the class of
decidable
languages (a language is
decidable if a Turing machine exists answering “yes” for the (input) strings that
belong to the language and “no” for those that do not belong to it.
A simple result about decidability (often mentioned as Post theorem) says that if a
language
L
and its complementary
L
are both recursively enumerable, then they are
both recursive. In fact, let us start, in parallel, the enumerations of the two languages,
then any string will be generated by one of the two enumerations, therefore, in a
