title: Analyzing a 1-mutable-register instruction set?
body: <h1>Summary of problem</h1>
  
  <p>I need to be able to generate instructions for a conceptual CPU + instruction set. I have an almost-working algorithm.</p>
  
  <p>The CPU only has 1 mutable register (named mut) which always begins as 1, and some amount of immutable registers with values in them (named input[0..n]). The instructions for this CPU are just logical gates on mut with one of the input registers that store the result back into mut.</p>
  
  <p>I need an algorithm to generate the instructions that will allow this CPU to generate the correct answer for each possible set of inputs from some defined truth-table.</p>
  
  <h1>Example</h1>
  
  <p>As an example, maybe I want this CPU to act like an AND gate (which has a truth table of <code>00=0,01=0,10=0,11=1</code>). I should be able to feed the algorithm this truth-table and have it spit out the instructions "<code>AND[0] AND[1]</code>". If you follow with your head, you can see that MUT will only remain 1 if both INPUT[0] and INPUT[1] are 1.</p>
  
  <h1>Attempt</h1>
  
  <p>Currently, I have a naive implementation of an algorithm that simply does a breadth-first search of all possible sets of instructions, testing each them on each of the truth-table input/output pairs to see if it works. For a lot of the expectations I feed the algorithm, it returns the correct set of instructions in just a few levels of search. However, for others, it will consume my entire CPU's memory before it finds a result, so I can only assume it can't find a result.</p>
  
  <h1>Questions</h1>
  
  <p>Is there a) any efficient way to design this algorithm, b) any way to prove that, for a certain instruction set, any expected truth-table can be achieved or c) any existing insights into this problem?</p>
  
  <p>I know of Karnaugh maps, but they generate 2D logic circuits, whereas this is essentially a 1D logic circuit.</p>
  
  <p>If you have any questions please let me know. It's a difficult problem to explain but I really need help on it.</p>
  
  <h1>Instruction Set</h1>
  
  <p>For reference, the instructions I have are:</p>
  
  <pre><code>AND[n]: MUT = MUT &amp; INPUT[n]
  OR[n]: MUT = MUT | INPUT[n]
  NOT: MUT = ~MUT
  </code></pre>
  
  <p>I might be able to more instructions to the CPU, but ideally the algorithm could attempt to solve the problem with any given instruction set.</p>