<p>For effective information processing, the response to a sensory stimulus should depend on both the incoming stimulus and the history of prior stimuli. We demonstrate how a network of randomly connected inhibition-stabilized pairs of units can produce a network with multiple attractor states, whose number increases exponentially with network size. The resulting network can preserve the computational abilities of recurrent excitatory networks, while activity of active units can stabilize at arbitrarily low firing rates. Inhibitory-stabilization also plays a functional role in history-dependent computation: transient oscillations made possible by inhibitory feedback are sufficient for state-dependent responses to stimulation. We formalize the computational processing of such networks given a set of stimuli as finite state machines and demonstrate a role for a small amount of heterogeneity in boosting their performance. Such networks may underlie many cognitive tasks, suggesting a functional role for inhibition-stabilized dynamics in cortical computation.</p>