问题总结
我需要能够为概念性的CPU +指令集生成指令。我有一个几乎可以正常工作的算法。
CPU仅具有1个始终以1开头的可变寄存器(命名为mut)，以及一定数量的不可变寄存器，其中包含值(命名为input [0..n])。该CPU的指令只是mut上的逻辑门，其中一个输入寄存器将结果存储回mut中。
我需要一种算法来生成指令，该指令将允许该CPU为来自某些定义的真值表的每个可能的输入集生成正确的答案。
例
举例来说，也许我希望这个CPU像AND门(其真值表为00=0,01=0,10=0,11=1)一样工作。我应该能够向该真值表提供算法，并使其吐出“AND[0] AND[1]”指令。如果跟随您的头，您会看到，只有INPUT [0]和INPUT [1]均为1时，MUT才会保持为1。
尝试
当前，我有一个简单的算法实现，该算法简单地对所有可能的指令集进行广度优先搜索，然后在每个真值表输入/输出对上测试每个指令，以查看其是否有效。对于我提供的算法有很多期望，它仅在几个搜索级别即可返回正确的指令集。但是，对于其他人，它将在找到结果之前消耗我整个CPU的内存，因此我只能假定它找不到结果。
问题
是否存在a)设计该算法的任何有效方法，b)证明对于特定指令集可以实现任何预期真值表的方法，或者c)对该问题的任何现有见解？
我知道卡诺图，但它们生成2D逻辑电路，而本质上是1D逻辑电路。
如果您有任何疑问，请告诉我。这是一个很难解释的问题，但我确实需要帮助。
指令系统
供引用，我有以下说明:
AND[n]: MUT = MUT & INPUT[n]
OR[n]: MUT = MUT | INPUT[n]
NOT: MUT = ~MUT
我也许可以向CPU发送更多指令，但是理想情况下，算法可以尝试解决任何给定指令集的问题。
最佳答案
我同意Martin Rosenau的观点，并且我怀疑您的CPU是否可以处理任何给定的真值表而无需额外的功能。就像您现在拥有的一样，我看不到如何实现XOR。
因此，我随意添加了一个累加器regitser ACC(它将初始化为False)和一个附加命令ACC，它可以执行以下操作:
ACC <- ACC or MUT
MUT <- True
鉴于此，下面的例程采用参数
rules，该参数是bool列表的列表，每行首先指示结果，然后指示真值表的输入寄存器0..n。例如，二元XOR是[[True, True, True], [False, False, True], [False, True, False], [True, False, False]]。希望这会产生正确的指令:
def generateCode (rules):
rules = [rule for rule in rules if rule [0] ]
if not rules: return []
opcodes = []
for rule in rules:
rule = rule [1:]
negs = [i for i, e in enumerate (rule) if not e]
poss = [i for i, e in enumerate (rule) if e]
if negs:
opcodes.append ('NOT')
for neg in negs: opcodes.append ('OR[{}]'.format (neg) )
opcodes.append ('NOT')
if poss:
for pos in poss: opcodes.append ('AND[{}]'.format (pos) )
opcodes.append ('ACC')
return opcodes
例如，从上面的示例输入中获得
['AND[0]', 'AND[1]', 'ACC', 'NOT', 'OR[0]', 'OR[1]', 'NOT', 'ACC']，这似乎是正确的。这是我测试过的CPU。我添加了一个重置按钮，结果将在执行结束时显示在ACC中。
class CPU:
def reset (self, inputs):
self.MUT = True
self.ACC = False
self.INP = inputs [:]
def __call__ (self, opcodes):
for opcode in opcodes:
if opcode == 'NOT':
self.MUT = not self.MUT
continue
if opcode == 'ACC':
self.ACC = self.ACC or self.MUT
self.MUT = True
continue
if opcode [0] == 'O':
inp = int (opcode [3:-1] )
self.MUT = self.MUT or self.INP [inp]
continue
if opcode [0] == 'A':
inp = int (opcode [4:-1] )
self.MUT = self.MUT and self.INP [inp]
continue
raise Exception ('Need more dried frog pills.')
return self.ACC
再次，很抱歉，我无法按照您指定的限制回答您的问题，但是希望我的摘要对您有所帮助。