Document Type

Conference Proceeding

Department

Mathematics (HMC)

Publication Date

1986

Abstract

This talk concerns computation by systems whose components exhibit noise (that is, errors committed at random according to certain probabilistic laws). If we aspire to construct a theory of computation in the presence of noise, we must possess at the outset a satisfactory theory of computation in the absence of noise.

A theory that has received considerable attention in this context is that of the computation of Boolean functions by networks (with perhaps the strongest competition coming from the theory of cellular automata; see [G] and [GR]). The theory of computation by networks associates with any two sets Q and R of Boolean functions a number LQ(R) (the "size" of R with respect to Q), defined as the minimum number of "gates," each computing a function from the basis Q, that can be interconnected to form a "network" that computes all of the functions in R.

Comments

First published in the Proceedings of the International Congress of Mathematicians in 1986, published by the American Mathematical Society

Rights Information

© 1986 American Mathematical Society

Download

Share

COinS