propagation algorithms[@pearlprobabilistic; @linhigh; @vigodacontinuous] can only answer queries about marginal probabilities or most probable configurations, only apply to finite graphical models with discrete or binary nodes, and cannot be used to learn model parameters from data. For example, the formulation of perceptual learning we present here is based on inference in a nonparametric Bayesian model to which belief propagation does not apply. Additionally, because stochastic digital circuits produce samples rather than probabilities, their results capture the complex dependencies between variables in multi-modal probability distributions, and can also be used to solve otherwise intractable problems in decision theory by estimating expected utilities.

Stochastic Digital Gates and Stateless Stochastic Circuits {#stochastic-digital-gates-and-stateless-stochastic-circuits .unnumbered}
==========================================================

[**(Figure 1 about here)**]{} \[fig:combinational\] Digital logic circuits are based on a gate abstraction defined by Boolean functions: deterministic mappings from input bit values to output bit values[@shannonsymbolic]. For elementary gates, such as the AND gate, these are given by truth tables; see Figure 1A. Their power and flexibility comes in part from the composition laws that they support, shown in Figure 1B. The output from one gate can be connected to the input of another, yielding a circuit that samples from the composition of the Boolean functions represented 