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
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)
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
(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 :
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 :

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
Previous Page Next Page