Random Boolean networksBoolean networks exhibit a variety of properties that are characteristic of natural adaptive systems. This suggests that Boolean networksBoolean networks may provide a useful substrate for artificial systems that adapt to solve specified problems. In this chapter, I describe an investigation of the capacity of Boolean networksBoolean networks to represent solutions to computational problems and the efficacy of simple stochastic algorithms for finding problem-solving Boolean networksBoolean networks. Because prior work noted that the properties of Boolean networks depend on the set of permitted gate types, I consider here networks constructed only of programmable gates that can be configured to act as any 2-input Boolean gateBoolean gates. Networks of these gates are self-programming because the function of each gate is determined dynamically from its configuration inputs. I consider search algorithms that find self-programming networks through processes of random rewiringRandom rewiring, random gate additions, random gate deletions, and a ratchet mechanism that only permits moves in the search space that maintain or increase training case coverage. I present networks found by this algorithm and discuss the implications of these results for future work.