On Reliable Computation With Formal Neurons

We investigate the computing capabilities of formal McCulloch-Pitts neurons when errors are permitted in decisions. Specifically, given a random m-set of points u1, ..., u(m) is-an-element-of R(X), a corresponding m-set of decisions d1, ..., d(m) is-an-element-of { - 1, 1}, and a fractional error-tolerance O less-than-or-equal-to is-an-element-of < 1, we are interested in the following question: How large can we choose m such that a formal neuron can make assignments u-alpha --> d-alpha, with no more than epsilon-m errors? We obtain formal results for two protocols for error-tolerance-a random error protocol and an exhaustive error protocol.