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