2. Boolean circuits 17

[3] 1.7. Prove that a 3-tape Turing machine working in time T(n) for in-

puts of length n can be simulated by a 2-tape machine working in time

O

(

T(n) log T(n)

)

.

[3] 1.8. Let M be a (single-tape) Turing machine that duplicates the input

string (e.g., produces “blabla” from “bla”). Let T(n) be its maximum run-

ning time when processing input strings of length n. Prove that T(n) ≥

εn2

for some ε and for all n. What can be said about T (n), the minimum

running time for inputs of length n?

[2] 1.9. Consider a programming language that includes 100 integer vari-

ables, the constant 0, increment and decrement statements, and conditions

of type “variable = 0”. One may use if-then-else and while constructs,

but recursion is not allowed. Prove that any computable function of type

Z → Z has a program in this language.

2. Boolean circuits

2.1. Definitions. Complete bases. A Boolean circuit is a representation

of a given Boolean function as a composition of other Boolean functions.

By a Boolean function of n variables we mean a function of type

Bn

→ B.

(For n = 0 we get two constants 0 and 1.) Assume that some set A of

Boolean functions (basis) is fixed. It may contain functions with different

arity (number of arguments).

A circuit C over A is a sequence of assignments. These assignments in-

volve n input variables x1,...,xn and several auxiliary variables y1,...,ym;

the j-th assignment has the form yj := fj(u1,...,ur). Here fj is some func-

tion from A, and each of the variables u1,...,ur is either an input variable

or an auxiliary variable that precedes yj. The latter requirement guarantees

that the right-hand side of the assignment is defined when we perform it (we

assume that the values of the input variables are defined at the beginning;

then we start defining y1, y2, etc.).

The value of the last auxiliary variable is the result of computation.

A circuit with n input variables x1,...,xn computes a Boolean function

F :

Bn

→ B if the result of computation is equal to F(x1,...,xn) for any

values of x1,...,xn.

If we select m auxiliary variables (instead of one) to be the output, we

get the definition of the computation of a function F :

Bn

→

Bm

by a circuit.

A circuit can also be represented by an acyclic directed graph (as in

Figure 2.1), in which vertices of in-degree 0 (inputs — we put them on top

of the figure) are labeled by input variables; all other vertices (gates) are

labeled with functions from A in such a way that the in-degree of a vertex

matches the arity of the function placed at that vertex, and each incoming