Summary of problem
I need to be able to generate instructions for a conceptual CPU + instruction set. I have an almost-working algorithm.
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.
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.
Example
As an example, maybe I want this CPU to act like an AND gate (which has a truth table of 00=0,01=0,10=0,11=1). I should be able to feed the algorithm this truth-table and have it spit out the instructions "AND[0] AND[1]". If you follow with your head, you can see that MUT will only remain 1 if both INPUT[0] and INPUT[1] are 1.
Attempt
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.
Questions
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?
I know of Karnaugh maps, but they generate 2D logic circuits, whereas this is essentially a 1D logic circuit.
If you have any questions please let me know. It's a difficult problem to explain but I really need help on it.
Instruction Set
For reference, the instructions I have are:
AND[n]: MUT = MUT & INPUT[n]
OR[n]: MUT = MUT | INPUT[n]
NOT: MUT = ~MUT
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.