12 1. Classical Computation
By a predicate we mean a function with Boolean values: 1 (“true”) or
0 (“false”). Informally, a predicate is a property that can be true or false.
Normally we consider predicates whose domain is the set
A∗
of all strings
over some alphabet A. Such predicates can be identified with subsets of
A∗:
a predicate P corresponds to the set {x : P (x)}, i.e., the set of strings x for
which P (x) is true. Subsets of
A∗
are also called languages over A.
As has been said, a predicate P is a function
A∗
{0, 1}. A predicate is
called decidable if this function is computable. In other words, a predicate
P is decidable if there exists a Turing machine that answers question “is
P (α) true?” for any α
A∗,
giving either 1 (“yes”) or 0 (“no”). (Note that
this machine must terminate for any α
A∗.)
The notions of a computable function and a decidable predicate can be
extended to functions and predicates in several variables in a natural way.
For example, we can fix some separator symbol # that does not belong to
A and consider a Turing machine M with external alphabet A ∪{#}. Then
a partial function ϕM,n :
(A∗)n

A∗
is defined as follows:
ϕM,n(α1,...,αn) = output of M for the input α1#α2# · · · #αn.
The value ϕM,n(α1,...,αn) is undefined if the computation never terminates
or the output string does not belong
A∗.
Definition 1.3. A partial function f from
(A∗)n
to
A∗
is computable if
there is a Turing machine M such that ϕM,n = f.
The definition of a decidable predicate can be given in the same way.
We say that a Turing machine works in time T(n) if it performs at most
T(n) steps for any input of size n. Analogously, a Turing machine M works
in space s(n) if it visits at most s(n) cells for any computation on inputs of
size n.
1.3. Turing’s thesis and universal machines. Obviously a TM is an
algorithm in the informal sense. The converse assertion is called the Turing
thesis:
“Any algorithm can be realized by a Turing machine.”
It is called also the Church thesis because Church gave an alternative
definition of computable functions that is formally equivalent to Turing’s
definition. Note that the Church-Turing thesis is not a mathematical theo-
rem, but rather a statement about our informal notion of algorithm, or the
physical reality this notion is based upon. Thus the Church-Turing thesis
cannot be proved, but it is supported by empirical evidence. At the early
age of mathematical computation theory (1930’s), different definitions of
Previous Page Next Page