together with the fact that with each possible input-output pair, there is associated a precise probability of error c.1

We can formally represent this, by attaching a binary symmetric channel (BSC) to the output of the computing device:

Of course, we need not attach a BSC, capacity CBSC = 1- H(E) 1+ Elog2E +U1-E) log2 (1-E) to the output. We could have

Furthermore, we

used any noisy binary channel, with capacity Cat the output. For simplicity, we shall consider here only the former case. shall consider only systems with two inputs (x1, x2). In general, of course, we can have any number of inputs.

a

a

The general n→ 1 computational scheme (n finite), with any noisy binary channel at the output is being considered by S. Winograd, Research Laboratory of Electronics, M. I. T., and the writer.

Z Z. Since

f is noiseless, the capacity for XX2Y is just 1 bit, while the capacity for I is CBSC And since the two channels are in series, the maximum rate for XX2 fog-Z is just

min (1, CBSc) = CBSC. That is, the maximum mutual information rate that can be obtained from the noisy computation scheme

X10X2 tog

N

Z is just the capacity of the dimensionpreserving channel specifying the noise in the scheme. We can compute this explicitly as follows: we note that

From this simple analysis, it would appear that essentially the same results that apply to the noisy computation channel apply to the noisy transmission channel, namely: up to a certain mutual information rate, Cesc, it is possible to introduce redundancy into the system, independent of rate, and achieve an arbitrarily small probability of error in the computation. The question is, of course, can we, in fact, introduce redundancy into a computing scheme, so as to realize this nonzero rate for reliable computation, and if so, what is the nature of this redundancy? Before trying to answer this question, we shall analyze the nature of the measure X1 ® X 2 ; Z] . 2

THE NATURE OF g [Z1® X2 ; Z]

For transmission, the information measure that we have used is

[X;], which we interpret as a measure of the average rate at which information about "points" in X is provided by reception of "points" in. In the case of computation, the measure that we have used is g[ =1 ® X2; {], where

Furthermore,

J [81® X2; } ] = H(Z) - H(ZIZ)

This is a consequence of the fact that H(fo X 10 X2 | X18X2) = 0 since fis noiseless.

where

Thus

9 [X1® X2; =] = H(Z) - H ( Z |×10X2)

This computation measure is thus a measure of the average rate at which information about points in foXX2 is provided by reception of "points" in f*。X10X2. But clearly, points in foX10X2 correspond to point sets in X1

X2 That is

[f; f*]

is a measure of the average rate at which information about point sets in

X1X2, specified by f, is provided by reception of points in Z. Since we are dealing with functions that are only probable, this is

reasonable.

Given a 1€ 2 we wish to compute, not what was the most likely input sequence (x1,x2)E X1 X2 but what was the

most likely input sequence subset, or equivalently, what was the most likely +(x1, x2). Furthermore, since this is all that we wish to compute, no matter where malfunctions are located, and, for example, in formal neurons they can occur as threshold fluctuations, synapse

4

errors, axon errors, as far as [fi] is concerned, these malfunctions are all effective at the output of f.

CODING FOR THE COMPUTATION CHANNEL

We now return to the question of coding for the computation channel, and our approach is based on certain implications of the noisy coding theorem for transmission channels. The whole process of introducing redundancy, encoding, decoding, and so forth, can be represented by the following set-theoretic picture:

12

bwe note in this context, that the work of Shannon and Moore, Kochen,

14

and Allanson, is concerned not with probabilistic functions, but with functions of probabilistic arguments, and is different in character from the schemes considered here.

13