Cryptography Reference
In-Depth Information
of interaction between two such machines. The reader may skip to Section 4.2.1.2,
which introduces some important conventions (regarding interactive machines), with
little loss (if any).
Definition 4.2.1 (An Interactive Machine):
An
interactive Turing machine
(ITM)
is a (deterministic) multi-tape Turing ma-
chine. The tapes are a read-only
input tape
, a read-only
random tape
, a read-and-
write
work tape
, a write-only
output tape
, a pair of
communication tapes
, and a
read-and-write
switch tape
consisting of a single cell. One communication tape is
read-only, and the other is write-only.
, called its
identity
. An ITM is said to
be
active
, in a configuration, if the content of its switch tape equals the machine's
identity. Otherwise the machine is said to be
idle
. While being idle, the state of the
machine, the locations of its heads on the various tapes, and the contents of the
writable tapes of the ITM are not modified.
The content of the input tape is called
input
, the content of the random tape is
called
random input
, and the content of the output tape at termination is called
output
. The content written on the write-only communication tape during a (time)
period in which the machine is active is called the
message sent
at that period.
Likewise, the content read from the read-only communication tape during an active
period is called the
message received
(at that period).
(Without loss of generality, the machine movements on both communication
tapes are in only one direction, e.g., from left to right.)
Each ITM is associated a single bit
σ
∈{
0
,
1
}
This definition, taken by itself, seems quite non-intuitive. In particular, one may say that
once being idle, the machine will never become active again. One may also wonder as to
what is the point of distinguishing the read-only communication tape from the input tape
(and respectively distinguishing the write-only communication tape from the output
tape). The point is that we are never going to consider a single interactive machine,
but rather a pair of machines combined together such that some of their tapes coincide.
Intuitively, the messages sent by one interactive machine are received by a second
machine that shares its communication tapes (so that the read-only communication
tape of one machine coincides with the write-only tape of the other machine). The
active machine may become idle by changing the content of the shared switch tape, and
when it does so, the other machine (having opposite identity) will become active. The
computation of such a pair of machines consists of the machines alternately sending
messages to one another, based on their initial (common) input, their (distinct) random
inputs, and the messages each machine has received thus far.
Definition 4.2.2 (Joint Computation of Two ITMs):
Two interactive machines are said to be
linked
if they have opposite identities, their
input tapes coincide, their switch tapes coincide, and the read-only communication
tape of one machine coincides with the write-only communication tape of the other
machine, and vice versa. We stress that the other tapes of both machines (i.e., the
random tape, the work tape, and the output tape) are distinct.
