Noisy Turing Machines: Noisy Logic Gates

Noisy Turing machines: noisy logic gates

As we consider more complex compound data types, which may always be modeled as
functions, we will see that there are many ways these types can participate
in the Bernoulli Boolean model. When a Bernoulli value is introduced into the
computational model, the entire computation outputs a final result that is
a Bernoulli type, e.g., bernoulli<pair<T1,T2>>, pair<T1,bernoulli<T2>, and so
on.

The easiest way to think about this is to just consider a Universal Turing machine
in which we build programs by composing circuits of binary logic-gates, like and,
or, and not. In general, if we replace a single input into the circuit with a
Bernoulli Boolean, the output of the circuit is a one or more Bernoulli Booleans.
Moreover, and more interestingly, we can replace some of the logic gates with
noisy logic-gates, or Bernoulli logic-gates, and the output of the circuit is
also a Bernoulli Boolean. We can always discard information about the uncertainty
in the output of the circuit, and just get Boolean, but if the uncertainty is
non-negligible, then we may want to keep track of it.

So, let's consider the set of binary functions
f : (bool, bool) -> bool.

There are 2^2 = 4 possible functions f : bool -> bool since for each possible
input, $1$ or $0$, we have two possible outputs, $1$ or $0$.

More generally, if we have f : X -> Y, then we have |Y|^|X| possible functions,
where |.| denotes the cardinality of a set. For instance, if X = (bool, bool)
and Y = bool, then we have 2^4 = 16 possible functions, since |X| = 4 and |Y| = 2.

Each of these functions has a designated name, which we can use to refer to them,
like and, xor, etc. However, we are just going to look at and.

Table 4: and : (bool, bool) -> bool

Now, let's consider

and : (bernoulli<bool,1>, bernoulli<bool,1>) -> bernoulli<bool,2>`

This is more complicated than might first seem. An error occurs if
and returns $1$ when it should return $0$, or vice versa. The input
variables represent latent values, so they do not have a definite value.

We will go row by row, and examine the probability that the output is correct for
each output.

Case 1: The Correct Output Is True

In order for the output to be true, both noisy inputs must be true, which is just
the product of the probabilities of each condition being true since they are
statistically independent outcomes.

Case 2: The Correct Output Is False Given x1 = true and x2 = false

Consider and(bernoulli<bool,1>{true}, bernoulli<bool,1>{false}).
For this to be true, the first must be a true positive and the second must be
a false postive, which is just p1 * (1-p2). Since we are interested in the probability that it correctly maps to false, that is just
1 - p1 * (1-p2) = 1 - p1 + p1 * p2.

Case 3: The Correct Output Is False Given x1 = false and x2 = true

Consider and(bernoulli<bool,1>{false}, bernoulli<bool,1>{true}).
For this to be true, the first must be a false positive and the second must
be a true positive, which is just (1-p1) * p2. Since we are interested in the
probability that it maps correctly to false, that is just
1 - (1-p1) * p2 = 1 - p2 + p1 * p2.

Case 4: The Correct Output Is False Given x1 = false and x2 = false

Consider and(bernoulli<bool,1>{false}, bernoulli<bool,1>{false}).
For this to be true, both must be false positives, which is just
(1-p1) * (1-p2). Since we are interestd in the probability that it maps correctly
to false, that is just 1 - (1-p1) * (1-p2) = p1 + p2 - p1 * p2.

Summary

Table 6: and with Bernoulli inputs

We see that and : (bernoulli<bool,1>, bernoulli<bool,1>) -> bernoulli<bool,4>
induces an output that is a fourth-order Bernoulli Boolean. How is this possible
when there are only two possible outputs? The answer is that the output is dependent
on four different combinations of inputs.

Since x1 and x2 are latent, we can only talk about the probability that
the output is correct or not. We see that when the output is 1, the probability that
the output is correct is p1 * p2. When the output is 0, the probability that it is
correct is more complicated.

We could store all of this information in the type bernoulli<bool,4>, but it is
probably more convenient to use interval arithmetic, where we store a range of
probabilities for the probabily that the Boolean value being stored is correct.
The best choice is just the minimum length interval that contains all of the
relevant probabilities for the output being correct. When the output is 1, we see
that the minimum spanning interval is just p1 * p2, and when the output is 0,
the minimum spanning interval is just the minimum span of

min_span{1 - p1 + p1 * p2, 1 - p2 + p1 * p2, p1 + p2 - p1 * p2}

As we compose more and more logic circuits together, we can keep track of the
minimum spanning intervals on outputs using interval arithmetic.

Let's come back to the idea of Bernoulli types over compound types. In particular,
let's consider applynig the Bernoulli approximation to binary functions of the
type (bool, bool) -> bool.

Now, we can apply the Bernoulli approximation

bernoulli<(bool, bool) -> bool>

which will generate functions of the type

(bool, bool) -> bernoulli<bool>

This may be thought of as a noisy binary logic-gate.
For the case of the and gate, what we observe in our model is
bernoulli<(bool, bool) -> bool>{and}, and it can generate up to 16 different
Bernoulli Boolean functions. That means that the maximum order is
$16 (16 - 1) = 240$, which isn't really important, but it's interesting to note.

Of course, if we have this noisy and function and then put in noisy inputs,
then we get a function of type

(bernoulli<bool>, bernoulli<bool>) -> bernoulli<bool>