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
of all strings
over some alphabet A. Such predicates can be identified with subsets of
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
are also called languages over A.
As has been said, a predicate P is a function
{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 α
giving either 1 (“yes”) or 0 (“no”). (Note that
this machine must terminate for any α
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 :

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
Definition 1.3. A partial function f from
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
“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