On the Expressibility of Stochastic Switching Circuits

Claude Shannon, in his Master's paper, provided the foundation of modern digital circuit design by demonstrating that Boolean algebra can be used to synthesize and simplify switching relay circuits. By replacing deterministic switches with probabilistic switches (pswitches), a new concept called stochastic switching circuit was proposed in. The study of stochastic switching circuits may enhance the understanding of natural systems and help incorporate randomness in engineering system design. A stochastic switching circuit with two terminals can be constructed by composing pswitches, where each pswitch is closed with some probability. The set of possible pswitch closure probabilities from which a circuit is constructed will be referred to as the pswitch set S.