Information Technology Reference
In-Depth Information
finite time it will appear, and according to which enumeration will provide it, we
can decide if it belongs to
L
or not. The converse implication is obvious. In fact if
L
is decidable, then we easily can enumerate both
L
and
L
.
The existence of languages in
RE
which are not in
REC
was an important
achievement of the computation theory founded by Turing. Such a language was
defined by Turing, by using a technique resembling the diagonal argument of Can-
tor showing that natural numbers cannot be put in a bijective correspondence with
the set of real numbers. In fact, if we enumerate all the strings over an alphabet
α
1
,
α
2
,...
and all the Turing machines over the same alphabet
M
1
,
M
2
,...
(by enu-
merating strings representing their programs), then the language:
K
=
{
α
i
|
α
i
∈
L(
M
i
)
}
can be easily recognized as recursively enumerable, but its complementary
K
can-
not be recursively enumerable because no Turing machine
M
j
can recognize it. In
fact if this machine could exist, then either
, but both
possibilities lead to a contradiction. In conclusion
K
is recursively enumerable, but
K
is not recursively enumerable, therefore
K
cannot be decidable, otherwise both
K
and
K
should be decidable.
The other crucial achievement of Turing's paper was the notion of
universal Tur-
ing machine
.Infact,aTuring
M
is univocally identified by its program, and it can
be easily encoded with a string of a suitable alphabet. Turing showed that a Turing
machine
α
j
∈
L(
M
j
)
or
α
j
∈
L(
M
j
)
U
can be constructed which, taken as an input an encoding
<
M
,
α
>
of
M
with the input
, can provide a computation which corresponds univocally to the
computation of
M
with the input
α
α
. In particular, the computation of
U
with this
input stops if and only if
M
stops on
α
, and this computation yields the same output
produced by
M
with
as input.
Turing machines resulted to be
equivalent
to other formalism introduced for
defining general classes of algorithmically effective computation processes. In fact,
reasonable processes of mutual translations were found such that computations per-
formed by Turing machines were encoded by computations performed in these other
formalisms, and vice versa. Just for mentioning some of them:
α
-calculus, Post sys-
tems, Herbrand-Godel general recursive functions, Kleene-Godel partial recursive
functions, and Markov Algorithms are all
Turing-equivalent.
In 1936, Alonzo Church published a paper where was formulated the famous
Turing-Church Thesis
:
λ
Every computation can be realized, by means of some suitable encoding of
data, by means of a Turing machine.
According to Turing-Church Thesis, the informal notion of computable func-
tion, can be adequately reduced to the rigorous concept of Turing computable func-
tion. Any formalism which results to be equivalent to Turing machines is said to be
computationally universal
.
