COMPUTABILITY BY PROBABILISTIC MAC HIKES
K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro
INTRODUCTION
The following question will be considered, in this paper: Is there
anything that can be done by a machine with a random element but not by a
deterministic machine?
The question as it stands is, of course, too vague to be amenable
to mathematical analysis. In what follows it must be delimited in two re
spects. A precise definition of the class of machines to be considered must
be given and an equally precise definition must be given of the tasks which
they are to perform. It is clear that the nature of our results will depend
strongly on these two choices and therefore our answer is not to be inter
preted as a complete solution of the originally posed informal question.
The reader should be especially cautioned at this point that the results we
obtain have no application outside the domain implied by these choices. In
particular our results refer to the possibility of enumeration of infinite
sets and the computation of infinite sequences. They yield no information
of the type that would be wanted if finite tasks were being considered; for
example, the relative complexity of probabilistic machines which can perform
a given finite task and their relative speeds.
This difficulty is implicit in any situation where mathematics is
to be applied to an informally stated question. The process of converting
this question into a precise mathematical form of necessity will highlight
certain aspects. Other aspects, perhaps of equal or greater importance in
another situation may be completely ignored.
The main body of the paper consists of definitions, examples, and
statements of results. The proofs are deferred to the appendix since they
consist in the most part of more or less elaborate constructions which are
not absolutely essential for an understanding of the results.
Readers acquainted with recursive function theory will readily see
that the results of this paper are actually results in that theory and can
183
EE LEEUWj MOORE, SHANNON, AND SHAPIRO
easily “be translated into its terminology. In the light of this, the proofs
of the results take on a dual aspect. They can he considered to be complete
proofs, assuming the intuitively given notion of an effective process;1 or
they can be considered to be indications of how the theorems, if they were
stated formally In the language of recursive function theory, could be proved
formally using the tools of that theory. This formalization is not carried
out in the paper since it would detract from the conceptual content of the
proofs. However, if should be clear to anyone familiar with recursive func
tion theory that the formalization can be carried out.
PROBABILISTIC MACHINES VS. DETERMINISTIC MACHINES
In this section we will first develop a precise definition of a
class of computing machines. These machines will have an input and an output.
The input will be an infinite sequence of binary digits which may be supplied
in two different ways: Either as a fixed sequence (physically we may think
of an infinite prepared tape) or as the output of a binary random device
(with probability p of producing a 1). In this latter case we have a
probabilistic machine. We will next formulate a precise class of tasks that
we wish such machines to perform, namely, the enumeration with positive proba
bility of sets of output symbols. The key result of the paper, Theorem 1,
is then applied to answer our question. The answer is given in Theorem 2.
What it states is that if the random device has a probability p, where p
is a computable real number (that Is, a real number such that there is an
effective process for finding any digit of Its binary expansion), any set
that can be enumerated by a probabilistic machine of the type considered can
oe enumerated by a deterministic machine. This does not occur if p is a
non-computable real number. Similar results are obtained if the sequential
order of the output symbols is taken into consideration. The situation is
summarized in Theorem 3.
We shall think of our machines as objects that accept as input a
tape printed with 0 • s and 1 * s and puts forth as output a tape on which
it may print using a finite or countably infinite selection of output sym
bols s1, s2, s^ ... (These symbols may be configurations formed from some
finite alphabet.) The machine shall be assumed to have some initial state
in which it is placed before any operation is started; (as, for example, a
desk calculator must be cleared before a computation). Another requirement
that we can reasonably require a machine to satisfy is the following: There
For discussion of effective processes, see [9] or [2]. The reader who is
not familiar with the notion of an effective process is advised to con
sult one of these before proceeding further. Effective processes are
also discussed in [1], [7], and [8].
COMPUTABILITY BY PROBABILISTIC MACHINES 185
is an effective procedure whereby one can determine-what the sequence of out
put symbols (s. , . .., s. ) on the output tape will be if the machine is
Jr
presented with the input sequence of 0's and 1*s (a1, ..., aR ) in its
initial state. This output sequence will be denoted by f(a1, ... a ).
Since we shall be interested only in the relationship between inuut and out
put in machines we can abstract away their interior and take this require
ment as a definition. (Even though an abstract definition is given at this
point, we shall continue to speak of machines in concrete terms.)
DEFINITION: A machine is a function that, for every n, to each n-tuple
of 01s and 1»s (a1, an ), associates some finite sequence
f(a1, a ) = (s. , ..., s. ) consisting of elements from some fixed
■ n. j -j Jp
set S such that the following two conditions are satisfied.
1. f(a1, ..., an ) is an initial segment of
f(a,, an , ..., an+m) if (a,, ah ) is
an initial segment of (a1, ..., a , ..., an+m).
2. f is a computable function, that is, there is an
o
effective process such that one can determine
f(a1, an ) if (a,, an ) is given.
This definition is extended to infinite sequences as follows:
If A = (a1, a2, a^, ...), f(A) is the sequence which has a3 initial seg
ments the f(a1, ..., an ).
The operation of the machine can be thought of Informally as follows
If It is supplied with input (a1, ..., a ), it looks at a1 and prints the
sequence of symbols f(a1) on its output, it looks at a2 and prints
symbols after f(a1 ) on the tape to obtain the sequence f(a , a2 ), ...,
it looks at an and prints symbols after f(a1, ..., an_ 1) on the tape
to obtain the sequence f(a1, ..., a ^ aR ) and then stops.
At this point several concrete examples of objects that are machines
will be given. These are to serve two purposes, to illustrate the concept
of machine introduced and to be referred to later to illustrate new concepts
that arise. The examples need not all be read at this point.
MACHINE NO. l: The output symbols of this machine are to be ordered pairs
of integers (a, r). For each input symbol a the machine prints the out
put symbol (a, r) if a was the r^*1 input symbol on the input tape. In
other words, f(a1, ..., an ) = ((a1, 1), (a2, 2), ..., (an , n)).
2
For discussion of effective processes, see [9] or [2]. The reader who is
not familiar with the notion of an effective process is advised to consult
one of these before proceeding further. Effective processes are also dis
cussed in [1], [7], and [8].
186
DE LEEUW, MOORE, SHANNON, AND SHAPIRO
MACHINE NO. 2: Let g be an integral valued function of positive integers
which is computable, that is, there is an effective process for finding
g(n) if n is given. Let the machine print the output symbol (r, g (r))
after it has scanned the r^*1 input symbol. In this case f(a^ , ..., a ) =
|(l, g( 1 )), (2, g( 2)), ... (n, g(n))j and the output is independent of the
input. This machine and Machine No. 1 are extreme cases. No. 2 is oblivious
of the input and No. 1 essentially copies the input onto the output tape.
Note that No. 2 would not be a machine according to our definition if the
function g were not computable, for in this case there would be no effective
process for determining what the output would be if the input were given.
MACHINE NO. 3: Let the machine print the symbol 0 as soon as it comes to
the first zero in the input sequence. Otherwise it is to do nothing. Then
f(a1, ..., an ) = (o) if one of the a^ is a zero. Otherwise the machine
prints nothing. This eventuality will be denoted by the "empty sequence,"
( .), and we have f (1, ..., 1 ) = ( .).
MACHINE NO. b: Let f(a1 , ..., a ) = (a^. The machine merely copies the
first input symbol onto the output tape and then prints nothing.
MACHINE NO. 5: Let the machine print the output symbol r if the maximum
length of a string of 11s that the machine has observed is r . For ex-
ample, f(l) = (i), f(i, o) = (1, 1), f(l, 0, 1) = (l, 1, 1),
f(i, o, i, i ) = (i, 1, i, 2).
MACHINE NO. 6: Let h(r, s) be a computable integral valued function whose
domain is the positive integers. The machine prints nothing until it comes
to the first 1 in the input; if this 1 is the first input symbol it never
prints anything; if this 1 has occurred after r zeroes, it prints the
symbol (1, h (r, 1)). After the next input the machine prints (2, h(r, 2)),
after the next (3, h(r, 3)) etc. Let the function hp with r fixed be
defined by h ^s) = h(r, s). Then what this machine actually does is to
compute the function h^ if it is presented with an initial string of r
zeroes followed by a 1.
MACHINE NO. 7: This machine is .given by f(a1, ..., a ) = ((1, r1 ),
(2, r2 ), ..., (q, ) where the integer rg is obtained as follows: Look
at the first 100s digits of (a-, ..., a„ ). Let po be the proportion of
th
digits that are 1*s. Let r be the s digit in the binary expansion of
s
the number p . q is the greatest s such that 100 < n. A construction
similar to this is used in the proof of part of Theorem 1.
Although the action of a machine is defined only for finite input
sequences, it Is clear what one of our machines would do if it were fed an
infinite input sequence A = (a1, a2, a^, ...) and had available an infinite
output tape on which it could print. Its action is determined by the fact
that we know what its output will be for all finite input sequences. Thus
COMPUTABILITY BY PROBABILISTIC MACHINES
187
the machine associates to each infinite input sequence an output sequence
which may op may not he infinite. For example, if Machine No . 1 is fed an
infinite tape on which only 1 ' s are printed, the output sequence will be
((1 , 1 ), (1 , 2), (1 , 3), . . . ). Machine No . 3 gives no output (the empty
sequence ( .)) and Machine N o. k the output sequence (1 ) when presented
with the same input.
We wish to consider the set of symbols that occur on the output
tape of a machine that is supplied with some infinite input sequence A.
(For example, if the output sequence is (1, 1, 1, ...) the set of symbols
consists of the symbol 1 alone while if the output sequence is
3, 5, 1 , ...) the set of symbols is the set of all odd integers.) Thus
the machine associates to each input sequence A some set of output symbols
which it enumerates. (We do not wish to consider here the order in which
the set is enumerated or whether or not it is enumerated without repetitions.
This will be done later when computation of sequences is considered.)
For example, Machine No. 1 associates to any infinite input sequence
A = (a1, ag, ... ) the set of output symbols consisting of all (an > n ) as
n runs over the positive integers. Machine No. 2 associates any input
sequence to the set of all (n, g(n)) as n runs over the positive integers.
Machine No. 3 associates to the input sequence consisting of all 1*s the
empty set. To the same input Machine No. 5 associates the set of all positive
integers.
DEFINITION: A machine supplied with the infinite input sequence
A = (a1, ag, a^, ...) will be called an A-machine. It will be said to
A-enumerate the set of output symbols that it prints. A set of symbols is
called A-enumerable if there is an A-machine that A-enumerates the set.
The sets that are A-enumerable if A is the sequence consisting
of all 1 * s are usually referred to as recursively enumerable sets. We
shall call them 1-enumerable sets and an A-machine shall be called a
1-machine if A consists entirely of 1fs.
One can associate to each infinite sequence A = (a- , aQ, ...)
th
the set of all pairs (n, an ) where an is the n element in the sequence
A and n runs over all positive integers. This set will be called A 1.
A sequence A is called computable If there is an effective process by means
of which one can determine the n term of A for every n. The following
three lemmas will be proved In the appendix, although their proofs are al
most immediate.
LEMMA 1. The sequence A is computable if and only
if the associated set A 1 is 1-enumerable.
LEMMA 2 . If A is a computable sequence, any A-enumerable
set is 1-enumerable (and conversely).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.